Automata and concurrency

AbstractThe purpose of this paper is twofold: to give a precise notion of a realization for simulation of one concurrent system by another, and to study the relations of modular concurrent systems and non-persistent (i.e. with conflicts) concurrent systems in an automatatheoretical style.We will introduce a conception of realization that obeys three requirements: - it allows for proper hierarchies in certain classes of concurrent systems, - it allows for normal-form theorems, and the standard constructions of the literature remain realizations in our formal concept, - it clarifies some counter-intuitive examples.Further, although our realization conception is developed to translate the computational aspects of concurrent systems, it also gives a formal tool for the handling of synchronization problems.The investigated concept of APA-nets (asynchronous, parallel automata nets) is by definition a modular system of networks of (finite state) machines and seems to be quite reasonable for modelling asynchronous, distributed systems. This modular approach is in some contrast to the non-persistency of Petri-nets, as in APA-nets conflicts may arise only as some non-determinism within components of the nets but not in the structure of the nets. As a bv-product we also investigate the relation of conflicts and non-determinism in concurrent systems