Synchronous-asynchronous transformation of cellular algorithms

Asynchronous versus synchronous cellular computations are investigated in terms of Parallel Substitution Algorithm (a formal model of fine-grained parallel data processing). A general method for constructing asynchronous cellular computation equivalent to a given cellular algorithm execution is presented. It is shown that more than a twofold increase in cell-complexity should...

bandman.pdf6.92 MB

Investigating nondeterministic processes

Event structures have widely been proposed as a basis for constructing models of nondeterministic processes. However, not all event structures are turned out to be suitable for this purpose. One way to get around this problem is to adapt Petri's concurrency axioms (including K-density and related properties) to event structures....

virbickayte.pdf3.96 MB