On a fast decomposition method in some models of concurrent computations (Q1083211)

A concurrent automaton (c.a.) \(A=(I,O,S,\to)\) consists of sets of input- (I) and output-lines (O), states (S), and transitions of the type M,s\(\to N,s'\) for \(M\subseteq I\), \(N\subseteq O\), s,s'\(\in S\). M,s\(\to N,s'\) means that A in state s may take off signals on input-lines M and send off signals on the output-lines N switching into state s' without involving a clock. The c.a. form a quite general model for concurrent, parallel computations just as sequential machines do in the sequential case. We prove the following: For most network-type models of concurrent computations (such as Petri nets, speed-independent modules of the MIT or Keller, e.g., data flow machines, asynchronous control modules, etc.) with a finite set B of basic components s.t. any c.a. can be simulated by a net with components only from the basic set B there holds: for any such set B of basic components, for any c.a. A with i input-lines, o output- lines, s states, and t transitions there exists a net \(N_ A\) of the given type s.t. (i) \(N_ A\) simulates A, (ii) \(N_ A\) consists only of components of the given basis B, (iii) \(N_ A\) consists of \(O((i+o+s)\times t)\) components (of B), and (iv) \(N_ A\) needs \(O(lg(t+i+o))\) (micro-) steps to simulate one (macro-) transition of A.