Defining Parallel Automata and their Conflicts
H.G. Mendelbaum, Tirza Hirst, Aryeh Teitelbaum, Simon Bloch · 2003
We define and classify a family of parallel automata (for Real-Time and Telecommunication modeling) in the context of a synchronous execution. First, an abstract form of Parallel automata is proposed as a generalization of various Extended-Finite-states- Machines found in the literature. Then, two implementable forms of Parallel Automata are presented : A global Parallel automaton with private states and sets of Synchronous and Hierarchic Parallel automata with local states. An example of application is presented with these two formalism. We also define and classify various types of possible conflicts that can occur in Parallel automata. An example shows an application with various kinds of conflicts and their possible correction. In a companion paper (17), we have shown that a-priori detection of actual conflicts for parallel automata is P- space hard. In view of this, an approach for a-priori potential conflict detection is developed. The complexity of detecting potential conflicts is shown to be possible in polynomial time, if all automata conditions are conjunctions.