# 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.

15 questions
Filter by
Sorted by
Tagged with
156 views

### Is there any equation-based method for transforming Büchi-automata to omega-regular language?

I know there exists an equation-based method for transforming finite automata into regular language (or `regular expression'). The main idea is as follows. First we construct a set of equations ...
132 views

### Intersection of two deterministic parity automata

Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the ...
393 views

### Does a given regular language contain an infinite prefix-free subset?

A set of words over a finite alphabet is prefix-free if there are no two distinct words where one is a prefix of the other. The question is: What is the complexity of checking whether a regular ...
90 views

128 views

### When does a set of infixes determine a set of ($\omega$-) words

If a have a set of finite infixes of a specific length, which $\omega$-languages are determined by them, and furthermore, when does a set of infixes determine a $\omega$-word uniquely. For example for ...
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 ...