×

Series-parallel posets: Algebra, automata and languages. (English) Zbl 0892.68041

Morvan, Michel (ed.) et al., STACS 98. 15th annual symposium on Theoretical aspects of computer science. Paris, France, February 25–27, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1373, 555-565 (1998).
Summary: In order to model concurrency, we extend automata theory from the usual word languages (sets of labelled linear orders) to sets of labelled series-paralle posets – or, equivalently, to sets of terms in an algebra with two product operations: sequential and parallel. First we consider languages of posets having bounded width, and characterize them using depth-nilpotent algebras. Next, we introduce series-rational expressions, a natural generalization of the usual rational expressions, as well as a notion of branching automaton. We show both a Myhill-Nerode theorem and a Kleene theorem. We also look at generalizations.
For the entire collection see [Zbl 0885.68008].

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDFBibTeX XMLCite