Home // ICCGI 2014, The Ninth International Multi-Conference on Computing in the Global Information Technology // View article

Four Scenarios of Effective Computations on Sum-like Graphs

Authors:
Elena Ravve
Zeev Volkovich

Keywords: Sum-like graphs; Translation schemes; (Weighted) Monadic Second Order Logic ; First Order Logic; Repetitive and hierarchical structures; Incremental computations; Parallel and distributed computations.

Abstract:
In this paper, we consider computations on sum-like graphs, which we introduced in our previous works. For such graphs, we proposed a method that allows us to reduce the solution of a Monadic Second Order or First Order definable problem on the graphs to the solution of effectively derivable Monadic Second Order or First Order definable problems on their components, respectively. Now, we describe in great details four particular scenarios, where this method may be applied, and explain how it may improve the complexity of the solution. This lead us to a generalized formulation of Amdahl’s style laws for each scenario. Moreover, we consider applications of our method to the fields of repetitive and hierarchical structures, widely used in hardware and software design, as well as parallel and distributed computations.

Pages: 1 to 8

Copyright: Copyright (c) IARIA, 2014

Publication date: June 22, 2014

Published in: conference

ISSN: 2308-4529

ISBN: 978-1-61208-346-9

Location: Seville, Spain

Dates: from June 22, 2014 to June 26, 2014