Branching Automata and Pomset Automata

Bedon, Nicolas

doi:10.4230/LIPIcs.FSTTCS.2021.37

File

LIPIcs.FSTTCS.2021.37.pdf

Filesize: 0.64 MB
13 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2021.37
URN: urn:nbn:de:0030-drops-155486

Author Details

Nicolas Bedon

LITIS (EA 4108), University of Rouen, France

Acknowledgements

The author would like to thank the anonymous referees of this paper, whose comments helped in improving its quality.

Cite AsGet BibTex

Nicolas Bedon. Branching Automata and Pomset Automata. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.37

Abstract

We compare, in terms of expressive power, two notions of automata recognizing finite N-free pomsets: branching automata by Lodaya and Weil [Lodaya and Weil, 1998; Lodaya and Weil, 1998; Lodaya and Weil, 2000; Lodaya and Weil, 2001] and pomset automata by Kappé, Brunet, Luttik, Silva and Zanasi [Kappé et al., 2018]. In the general case, they are equivalent. We also consider sub-classes of both kind of automata that we prove equivalent.

Subject Classification

ACM Subject Classification

Theory of computation → Regular languages

Keywords

Finite N-free Pomsets
Finite Series-Parallel Pomsets
Branching Automata
Pomset Automata
Series-Parallel Rational Languages

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Nicolas Bedon. Logic and branching automata. Logical Methods in Computer Sciences, 11(4:2):1-38, October 2015.
Jay L. Gischer. The equational theory of pomsets. Theoret. Comput. Sci., 61(2):199-224, 1988. URL: https://doi.org/10.1016/0304-3975(88)90124-7.
Jan Grabowski. On partial languages. Fundam. Inform., 4(1):427-498, 1981.
Tobias Kappé, Paul Brunet, Bas Luttik, Alexandra Silva, and Fabio Zanasi. Brzozowski goes concurrent - A Kleene theorem for pomset languages. In Proc. CONCUR 2017: 28th International Conference on Concurrency Theory, volume 28, pages 21:1-21:15, January 2017.
Tobias Kappé, Paul Brunet, Bas Luttik, Alexandra Silva, and Fabio Zanasi. On series-parallel pomset languages: Rationality, context-freeness and automata. Journal of Logical and Algebraic Methods in Programming, 103, December 2018. URL: https://doi.org/10.1016/j.jlamp.2018.12.001.
Stephen C. Kleene. Representation of events in nerve nets and finite automata. In Shannon and McCarthy, editors, Automata studies, pages 3-41, Princeton, New Jersey, 1956. Princeton University Press.
Kamal Lodaya and Pascal Weil. A Kleene iteration for parallelism. In V. Arvind and R. Ramanujam, editors, Foundations of Software Technology and Theoretical Computer Science, volume 1530 of Lect. Notes in Comput. Sci., pages 355-367. Springer-Verlag, 1998.
Kamal Lodaya and Pascal Weil. Series-parallel posets: algebra, automata and languages. In M. Morvan, Ch. Meinel, and D. Krob, editors, STACS'98, volume 1373 of Lect. Notes in Comput. Sci., pages 555-565. Springer-Verlag, 1998.
Kamal Lodaya and Pascal Weil. Series-parallel languages and the bounded-width property. Theoret. Comput. Sci., 237(1-2):347-380, 2000.
Kamal Lodaya and Pascal Weil. Rationality in algebras with a series operation. Inform. Comput., 171:269-293, 2001.
Jacobo Valdes. Parsing flowcharts and series-parallel graphs. Technical Report STAN-CS-78-682, Computer science departement of the Stanford University, Standford, Ca., 1978.
Jacobo Valdes, Robert E. Tarjan, and Eugene L. Lawler. The recognition of series parallel digraphs. SIAM J. Comput., 11:298-313, 1982. URL: https://doi.org/10.1137/0211023.
Józef Winkowski. An algebraic approach to concurrence. In MFCS'79, volume 74 of Lect. Notes in Comput. Sci., pages 523-532. Springer Verlag, 1979.