Questions tagged [omega-language]
Questions about ω-languages, i.e. about sets of infinite-length sequences of symbols. Typical examples include ω-regular languages or languages accepted by deterministic Büchi automata. The tag can also be used for questions about languates over ω-trees.
4
questions with no upvoted or accepted answers
6
votes
0
answers
200
views
Separation of the states of a deterministic omega-automaton by looping words taken from a regular language of non-empty words
Consider a deterministic transition structure having states in set $X$ and transition function $\rightarrow$, and an initial state $x \in X$. This structure is intended to be part of an automaton ...
- 363
3
votes
0
answers
97
views
A question on the introduction of the Wagner hierarchy from K. Wagner's original paper
My question is related to the seminal paper On $\omega$-regular sets by K. Wagner, which introduced a hierarchy which is now know as the Wagner- (or Wadge-) hierarchy of $\omega$-regular sets.
In ...
- 1,987
2
votes
0
answers
96
views
Necessary and sufficient condition for an infinite tree to be context-free
A Buchi automaton is non-empty iff it accepts an infinite word of the form $uv^\omega$ (here $u,v$ are finite words). In other words, if $\{w\}$ is an $\omega$-regular language, then it is of that ...
- 193
2
votes
0
answers
215
views
Complexity of DBA-recognizable Omega-Languages
Given an $\omega$-regular expression $r$, how difficult is it to decide if $L(r)$ is recognizable by some deterministic Büchi automaton? I know it is solvable in EXPTIME by converting the regular ...
- 153