Grobler, MarioMarioGroblerSabellek, LeifLeifSabellekSiebertz, SebastianSebastianSiebertz2025-09-032025-09-032024https://media.suub.uni-bremen.de/handle/elib/22347https://doi.org/10.26092/elib/4289Several 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.enhttps://creativecommons.org/licenses/by/4.0/Parikh automatablind counter machinesinfinite wordsBüchi’s theorem000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, SystemeText::Konferenzveröffentlichung::Tagungsband::Konferenzbeitrag10.26092/elib/4289urn:nbn:de:gbv:46-elib223475