I am wondering if $\omega$-automata with the following acceptance condition are valid.

An input string is accepted iff one of the final states occurs at least once.

This differs from Buchi automata in that the final state only has to occur once, not infinitely often.

Does this kind of automata have a name? Is it interesting or important?


Yes, it was studied before. In one of the early papers on accepting infinitary languages Landweber introduced five acceptance types that included those of Büchi and Muller. On the lowest level where two types that referred to the set of states entered, and the other three levels considered the more classic set of states entered infinitely often.

Your type is called 1-acceptance (if I recall right) and a string is accepted if a state from an accepting set $D$ is entered at least once. The dual 1'-acceptance required that the states entered are always within $D$. One level up one requires that a state from $D$ is entered infinitely often (Büchi), respectively that from some moment on the states are within $D$.

These definitions can be considered not only for finite state automata, but also for automata with external storage, like pushdown automata. One common fact for all such automata is that the 1-acceptance (your type) is of low "topological" complexity. Those $\omega$-languages are of the form $L\cdot \Sigma^\omega$, where $L$ is an ordinary language of the type of automata. This means one cannot accept $(a^*b)^\omega$.

In general there is a clear link between topological complexity of the $\omega$-language and the acceptance type.

L.H. Landweber, Decision problems for $\omega$-automata, Math. Systems Theory 3 (1969) 376-384.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.