Remarks on Parikh-Recognizable Omega-languages

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 U-i UiViw for Parikh recognizable languages U-i, V-i, but blind counter machines fall short of characterizing this class of epsilon-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 w-language of the form U-i UiViw 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 Buchi's classical theorem. We study the effect of epsilon-transitions in all variants of Parikh automata and show that almost all of them admit epsilon-elimination. Finally we study the classical decision problems with applications to model checking.