Remarks on Parikh-recognizable omega-languages
Abstract
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 $\omega$-language recognized by a blind counter machine is of the form $\bigcup_iU_iV_i^\omega$ for Parikh recognizable languages $U_i, V_i$, but blind counter machines fall short of characterizing this class of $\omega$-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 $\omega$-language of the form $\bigcup_iU_iV_i^\omega$ 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 $\varepsilon$-transitions in all variants of Parikh automata and show that almost all of them admit $\varepsilon$-elimination. Finally we study the classical decision problems with applications to model checking.
- Publication:
-
arXiv e-prints
- Pub Date:
- July 2023
- DOI:
- 10.48550/arXiv.2307.07238
- arXiv:
- arXiv:2307.07238
- Bibcode:
- 2023arXiv230707238G
- Keywords:
-
- Computer Science - Formal Languages and Automata Theory
- E-Print:
- arXiv admin note: text overlap with arXiv:2302.04087, arXiv:2301.08969