1 Search Results for "Bedon, Nicolas"

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-dev.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}
}
  • Refine by Author
  • 1 Bedon, Nicolas

  • Refine by Classification
  • 1 Theory of computation → Regular languages

  • Refine by Keyword
  • 1 Branching Automata
  • 1 Finite N-free Pomsets
  • 1 Finite Series-Parallel Pomsets
  • 1 Pomset Automata
  • 1 Series-Parallel Rational Languages

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact