Search

This paper exhibits an example of a \(\mathbf {\Sigma }^{1}_{1}\)-complete \(\omega \)-language that can be recognised by a Buchi automaton with one partially blind counter (or equivalently a Buchi VASS with only one place). It follows as a corollary that there is no equivalent model of deterministic automata, even if we allow much richer data structures than just counters. The same holds for weaker forms of determinism, like for unambiguous or countably-unambiguous machines. This shows that even in the one counter case, non-determinism of Buchi VASS is inherent.

This work is about studying reasons for (un)decidability of variants of Monadic Second-order (mso) logic over infinite structures. Thus, it focuses on connecting the fact that a given theory is (un)decidable with certain measures of complexity of that theory.

We consider probabilistic automata over finite words. Such an automaton defines the language consisting of the set of words accepted with probability greater than a given threshold. We show the existence of a universally non-regular probabilistic automaton, i.e. an automaton such that the language it defines is non-regular for every threshold. As a corollary, we obtain an alternative and very simple proof of the undecidability of determining whether such a language is regular.