2026-07-20T05:27:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15548 2024-03-06T10:55:34Z ddc:004 open_access

Branching Automata and Pomset Automata Bedon, Nicolas Finite N-free Pomsets Finite Series-Parallel Pomsets Branching Automata Pomset Automata Series-Parallel Rational Languages 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicolas Bedon 2021 Is Part Of LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2021.37 urn:nbn:de:0030-drops-155486 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.37 eng https://creativecommons.org/licenses/by/4.0/legalcode