DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2021.37

Branching Automata and Pomset Automata

Authors: Nicolas Bedon

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{bedon:LIPIcs.FSTTCS.2021.37,
  author =	{Bedon, Nicolas},
  title =	{{Branching Automata and Pomset Automata}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{37:1--37:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.37},
  URN =		{urn:nbn:de:0030-drops-155486},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.37},
  annote =	{Keywords: Finite N-free Pomsets, Finite Series-Parallel Pomsets, Branching Automata, Pomset Automata, Series-Parallel Rational Languages}
}

Search Results

Documents authored by Bedon, Nicolas

Branching Automata and Pomset Automata

Abstract

Cite as

Thanks for your feedback!

Could not send message