# Tag Info

13

This question generated a lot of literature in the 80's, partly due to a bad approach to the problem. This is a rather long story that I will try to summarize in this answer. 1. The case of finite words One can find two definitions of a minimal DFA in the literature. The first one is to define the minimal DFA of a regular language as the complete DFA ...

12

In general, $\omega$-regular languages may not have a unique minimal DBW. For example, the language "infinitely many a's and infinitely many b's" has two 3-state DBWs (in the picture replace $\neg a$ by $b$): As you can see, they are not topologically equivalent. Hence, the minimization problem is harder than the finite case, and in fact, it is NP-complete....

9

There are several interesting subquestions in your question: Which $\omega$-languages are determined by a set of finite infixes of a specific length? When does a set of infixes determine a $\omega$-word uniquely? What could be said about the relations about infix-sets and $\omega$-languages? Are there any results or articles on this topic? Let $A$ be ...

7

Your problem can be solved in polynomial time. To begin, convert the given NFA to an equivalent NFA with the following additional properties: There are no epsilon transitions All states are reachable from the start state Helpful subroutine Suppose we have an NFA $N$, a state $q$, and a nonempty string $s$. The following subroutine will let us evaluate ...

6

On infinite words, automata are much more convenient than Wilke algebra (playing the role of monoids) to characterize safety. Indeed, it just corresponds to being accepted by an automaton where all runs are accepting. This is because automata are designed to append new content to the right, while in Wilke Algebra you can more naturally append to the left. If ...

6

Sure. In fact, the translation from Büchi automata to $\omega$-regular expressions is only a small extension of the one for finite-word languages. Recall that an $\omega$-regular expression is of the form $s_1\cdot t_1^\omega+\ldots+s_k \cdot t_k^\omega$, where all the $s_i$ and $t_i$ are regular expressions. The translation of an NBW $A$ to such an ...

6

Take an alphabet $A=\{0,1,2\}$, and $U=0^*+2A^*$. Then, $U^\omega$ is not deterministic Büchi recognizable. To see this, imagine it is recognized by a deterministic Büchi automaton $\mathcal A$ with $n$ states. Then, look at the run of $\mathcal A$ on the word $w=2(0^{n+1}1)^\omega$. Any inside loop of $0$ must contain a Büchi state, because otherwise ...

5

For each $n \geq 0$, the word $aaba^nb^{n+1}$ is in $D$, therefore $aaba^\omega$ is in $Adh(D)$.

4

Once you have the bound $2^{2n^2}$ on the number of classes, you can note that each state in the complement automaton corresponds to an $\omega$-regular language of the form $L_{f}L_{g}^\omega$, with $L_f$ and $L_g$ being functions from $Q$ to $2^Q\times 2^Q$. Each such language is determined by $L_f$ and $L_g$, and there are $2^{2n^2}$ options for these ...

4

The following paper: http://www.faculty.idc.ac.il/udiboker/files/AutomataTypes.pdf shows that the intersection (and union) of deterministic parity automata may involve an exponential blowup. Thus, you cannot do much better than converting to nondeterministic Buchi automata, and taking the intersection there (and determinizing back to parity).

3

Denis's excellent answer mentions that aperiodicity is orthogonal to safety, so as long as this is allowed, one can also take a topological view instead of a purely algebraic: Safety languages can be characterized as the closed sets in a natural topology over infinite words (https://link.springer.com/content/pdf/10.1007%2F978-3-642-58041-3_5.pdf) Thus, the ...

3

Yes. The automata in question are often called "Looping" automata (so you have a keyword to start from). A possible starting point is the following paper: https://faculty.idc.ac.il/udiboker/files/MullerAutomata.pdf A looping automaton can be described as $\left<Q,\Sigma,\delta,Q_0\right>$ where the components are states, alphabet, transition ...

2

Definitions Definition 1: Let $S$ be a set of words. We say that $S$ is nicely infinite prefix-free (made up name for the purpose of this answer) if there are words $u_0,\dots,u_n,\dots$ and $v_1,\dots,v_n,\dots$ such that: For each $n\ge 1$, $u_n$ and $v_n$ are non-empty and start with distinct letters; $S=\{u_0v_1,\dots,u_0\dots u_n v_{n+1},\dots\}$. ...

2

Your construction for bad prefixes is not correct on NBA's. For instance take the NBA on alphabet $A=\{a,b\}$ with two initial states $q_a$ and $q_b$ where for both $x\in A$, $q_x$ goes to an accepting sink if the first letter is $x$ and to a rejecting sink if the first letter is not $x$. Then the language recognized is $A^\omega$, but the set of "bad ...

2

The conjecture does not hold: Let $L$ be the set of prefixes of $(c^*ac^*b)^*$. Then $L'=(c^*ac^*b)^\omega+ (c^*ac^*b)^*c^\omega+(c^*ac^*b)^*c^*ac^\omega$. Take the word $\eta=(c^1ac^1b)(c^2ac^2b)(c^3ac^3b)\dots \in L'$. For all $k\in\mathbb N$, we can show that $PF_k(\eta)\not\subseteq L'$, as witnessed by u_k=(c^1ac^1b)(c^2ac^2b)\dots (c^kac^kb)c^kb c^\...

Only top voted, non community-wiki answers of a minimum length are eligible