On a fast decomposition method in some models of concurrent computations

AbstractA concurrent automaton (c.a.) A = (I, O, S, →) consists of sets of input- (I) and output-lines (O), states (S), and transitions of the type M, s → N, s′ for M ⊆ I, N⊆ O, s,s′ ϵ S. M, s → 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. forms 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 NA of the given type s.t. (i) NA A, (ii) NA consists only of components of the given basis B, (iii) NA consists of O((i + o + s) × t) components (of B), and (iv) NA needs O(lg(t + i + o)) (micro-) steps to simulate one (macro-) transition of A