6
$\begingroup$

Let $X$ be an alphabet and denote by $X^{\omega}$ the set of all infinite sequences (i.e. words) in $X$. A subset $L \subseteq X^{\omega}$ is called $\omega$-regular if it is acceptable by some Büchi-Automaton, equivalently if it is of the form $$ L = \bigcup_i^n U_i V_i^{\omega} $$ for regular languages $U_i, V_i$ in the usual sense, also $L$ is regular iff it is acceptable by a Müller-Automata (see Wikipedia).

Let $\xi \in X^{\omega}$ be some infinite word, denote by $A(\xi)$ the set of its prefixes, these are finite words and so $A(\xi) \subseteq X^*$, likewise define $F(\xi)$ to be the set of factors of $\xi$.

Now define the following language operator (called adherence) on $X^{\omega}$: $$ \mbox{Adh}(L) := \{ \xi \in X^{\omega} : A(\xi) \subseteq A(L) \}. $$ It is $\xi \in \mbox{Adh}(L)$ iff every prefix of $\xi$ is the prefix of some word from $L$. Now if $L$ is $\omega$-regular, $A(\xi)$ is $\omega$ regular too, if given a Büchi-Automata for $L$ just declare every state on an acceptance path (i.e. a path having an infinite number of final states) a final state too, the automata with the usual acceptance condition for finite words accepts $A(\xi)$. Now $\mbox{Adh}(L)$ is accepted by this automaton according to the Büchi-condition.

I want to generalise this, define the operator $$ \mbox{Adh}_F(L) = \{ \xi \in X^{\omega} : F(\xi) \subseteq F(L). $$ It is $\xi \in \mbox{Adh}_F(L)$ iff every factor of $\xi$ is a factor of some word from $L$. Now I want to know

If $L$ is $\omega$-regular, is $\mbox{Adh}_F(L)$ also $\omega$-regular?

I conjecture that in general not to be true, because to test an infinite word $\xi$ for this condition, if the automaton would read the $n$-te symbol, it need to trace back to to all the position $1,2,\ldots, n$ of $\xi$ and test from them if the factor starting at this position and ending at the $n$-th position is contained in $F(L)$, but in general a finite automata can not save the last $n$-th positions for abitrary $n$.

On the other side I am not able to represent some known non-regular languages as $\mbox{Adh}_F(L)$, and furthermore for a regular set $L$ the set $F(L)$ is regular too (given an automata for $L$ on every path which is final, i.e. leads to a final state, put an $\varepsilon$-transition from the start state to that state). So maybe I have overlooked some property of factor sets which make $\mbox{Adh}_F$ regular...

$\endgroup$

1 Answer 1

4
$\begingroup$

Then answer is yes. Since $F(L)$ is a regular language, it suffices to prove the following result:

If $K$ is a regular language, then $R(K) = \{u \in A^\omega \mid F(u) \subseteq K \}$ is $\omega$-regular.

Since regular languages are closed under complement, it suffices to show that $R(K^c)$ is $\omega$-regular. Observing that $R(K^c) = \{u \in A^\omega \mid F(u) \subseteq K^c \}$, we get $$ (R(K^c))^c = \{u \in A^\omega \mid F(u) \cap K \not= \emptyset \} = A^*KA^\omega $$ Thus $(R(K^c))^c$ is $\omega$-regular, and since $\omega$-regular languages are closed under complement, $R(K^c)$ is $\omega$-regular.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .