2026-08-16T06:39:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7497 2024-03-06T10:40:31Z ddc:004 open_access

Regular Separability of Parikh Automata Clemente, Lorenzo Czerwinski, Wojciech Lasota, Slawomir Paperman, Charles Regular separability problem Parikh automata integer vector addition systems visible one counter automata decidability undecidability We investigate a subclass of languages recognized by vector addition systems, namely languages of nondeterministic Parikh automata. While the regularity problem (is the language of a given automaton regular?) is undecidable for this model, we surprisingly show decidability of the regular separability problem: given two Parikh automata, is there a regular language that contains one of them and is disjoint from the other? We supplement this result by proving undecidability of the same problem already for languages of visibly one counter automata. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lorenzo Clemente and Wojciech Czerwinski and Slawomir Lasota and Charles Paperman 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.117 urn:nbn:de:0030-drops-74971 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.117 eng https://creativecommons.org/licenses/by/3.0/legalcode