Lodaya, K.; Weil, P. 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]. Cited in 15 Documents MSC: 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) Keywords:bounded width; branching automaton PDFBibTeX XMLCite \textit{K. Lodaya} and \textit{P. Weil}, Lect. Notes Comput. Sci. 1373, 555--565 (1998; Zbl 0892.68041)