2026-08-06T13:46:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19674 2024-03-06T11:04:37Z ddc:004 open_access

Remarks on Parikh-Recognizable Omega-languages Grobler, Mario Sabellek, Leif Siebertz, Sebastian Parikh automata blind counter machines infinite words Büchi’s theorem Several variants of Parikh automata on infinite words were recently introduced by Guha et al. [FSTTCS, 2022]. We show that one of these variants coincides with blind counter machine as introduced by Fernau and Stiebe [Fundamenta Informaticae, 2008]. Fernau and Stiebe showed that every ω-language recognized by a blind counter machine is of the form ⋃_iU_iV_i^ω for Parikh recognizable languages U_i, V_i, but blind counter machines fall short of characterizing this class of ω-languages. They posed as an open problem to find a suitable automata-based characterization. We introduce several additional variants of Parikh automata on infinite words that yield automata characterizations of classes of ω-language of the form ⋃_iU_iV_i^ω for all combinations of languages U_i, V_i being regular or Parikh-recognizable. When both U_i and V_i are regular, this coincides with Büchi’s classical theorem. We study the effect of ε-transitions in all variants of Parikh automata and show that almost all of them admit ε-elimination. Finally we study the classical decision problems with applications to model checking. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mario Grobler and Leif Sabellek and Sebastian Siebertz 2024 Is Part Of LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2024.31 urn:nbn:de:0030-drops-196743 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.31 eng https://creativecommons.org/licenses/by/4.0/legalcode