Abstract
In order to model concurrency, we extend automata theory from the usual word languages (sets of labelled linear orders) to sets of labelled series-parallel posets - or, equivalently, to sets of terms in an algebra with two product operations: sequential and parallel. We first 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.
Part of this work was done while the second author was visiting the Institute of Mathematical Sciences, in Chennai.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
L. Aceto. Full abstraction for series-parallel pomsets, in Proc. TAPSOFT 91, LNCS 493, Springer (1991) 1–40.
G. Boudol and I. Castellani. Concurrency and atomicity, TCS 59 (1988) 25–84.
S. Bloom and Z. Ésik. Free shuffle algebras in language varieties, TCS 163 (1996) 55–98.
J.R. Büchi. Finite automata, their algebras and grammars: Towards a theory of formal expressions (D. Siefkes, ed.), Springer (1989).
B. Courcelle. Graph rewriting: an algebraic and logical approach, in Handbook of Theoretical Computer Science B (J. van Leeuwen, ed.), Elsevier (1990) 193–242.
V. Diekert and G. Rozenberg. The book of traces, World Scientific (1995).
J.L. Gischer. The equational theory of pomsets, TCS 61 (1988) 199–224.
J. Grabowski. On partial languages, Fund. Inform. IV (1981) 427–498.
R. Milner. A complete inference system for a class of regular behaviours, JCSS 28 (1984) 439–466.
J.-E. Pin. Syntactic semigroups, in Handbook of Formal Language Theory 1 (G. Rozenberg and A. Salomaa, eds.), Springer (1997) 679–746.
V. Pratt. Modelling concurrency with partial orders, IJPP 15(1) (1986) 33–71.
W. Reisig. Petri nets, an introduction, Springer (1985).
J.W. Thatcher and J.B. Wright. Generalized finite automata with an application to a decision problem of second order logic, Math. Syst. Theory 2 (1968) 57–82.
J. Valdes, R.E. Tarjan and E.L. Lawler. The recognition of series-parallel digraphs, SIAM J. Comput. 11(2) (1981) 298–313.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag
About this paper
Cite this paper
Lodaya, K., Weil, P. (1998). Series-parallel posets: Algebra, automata and languages. In: Morvan, M., Meinel, C., Krob, D. (eds) STACS 98. STACS 1998. Lecture Notes in Computer Science, vol 1373. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0028590
Download citation
DOI: https://doi.org/10.1007/BFb0028590
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64230-5
Online ISBN: 978-3-540-69705-3
eBook Packages: Springer Book Archive