4
$\begingroup$

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 the set $W = \{ 0, 1 \}$ all words in $X^* \setminus \{ 0^\omega, 1^{\omega} \}$ have it as infixes, and if I have $V = \{ 011, 110, 101 \}$ it determines the three words $$ 011011011011\ldots, \quad 110110110110\ldots, \quad 101101101101\ldots. $$ What could be said about the relations about infix-sets and $\omega$-languages, are there any results or articles on this topic?

$\endgroup$
  • 1
    $\begingroup$ You may want to clarify that you are looking for strings where all substrings of a particular length belong to the set. $\endgroup$ – Kaveh Sep 26 '13 at 21:39
8
$\begingroup$

There are several interesting subquestions in your question:

  1. Which $\omega$-languages are determined by a set of finite infixes of a specific length?
  2. When does a set of infixes determine a $\omega$-word uniquely?
  3. What could be said about the relations about infix-sets and $\omega$-languages?
  4. Are there any results or articles on this topic?

Let $A$ be a finite alphabet, let $n$ be a positive integer and let $F$ be a subset of $A^n$. Given an $\omega$-word $u$, let $F_n(u)$ be the set of its factors (= infixes) of length $n$.

Question 1. It can be restated as follows: What is the $\omega$-language $$ L(F) = \{ u \in A^\omega \mid F_n(u) = F \}? $$ The answer is $$ L(F) = \bigcap_{x \in F}A^*xA^\omega \setminus \bigcup_{x \in A^n \setminus F}A^*xA^\omega $$ which shows that $L(F)$ is $\omega$-regular (it actually belongs to a much smaller class of $\omega$-languages than the regular ones, see below).

Question 2. I only have a weak answer to this question. Given $F$, one can effectively compute $L(F)$ (say, by a finite Büchi automaton) and then one can effectively decide whether $L(F)$ contains a single $\omega$-word (which has to be ultimately periodic). I also tried the other way around: given an ultimately periodic word $uv^\omega$, is the language $\{uv^\omega\}$ of the form $L(F)$ for some $F$? This question is again decidable, but they might be some simple combinatorial characterization on the pair $(u, v)$. Unfortunately, I only got some partial results in this direction.

Question 3. I know of several topics in which infix-sets and $\omega$-languages are related.

  1. Locally testable $\omega$-languages (the notion of locally testable languages was originally introduced for finite words and later extended to infinite words [2]). The language $L(F)$ is an example.
  2. Factors of biinfinite words [1].
  3. First order logic of one successor [3].
  4. Sophic shifts and subshifts of finite type in symbolic dynamics [4].

Question 4. A few references:

[1] D. Beauquier and M. Nivat, About rational sets of factors of a bi-infinite word, LNCS 194, (1985) 33-42.
[2] J.P. Pécuchet Étude syntaxique des parties reconnaissables de mots infinis, Theoret. Comput. Sci. 56 (1988) 231-248.
[3] The expressive power of existential first order sentences of Büchi's sequential calculus.
[4] M.P. Béal and D. Perrin, Symbolic Dynamics and Finite Automata.

$\endgroup$
  • $\begingroup$ thx for this excellent answer, but regarding your answer to the first question, could $L(F)$ be easier written as $L(F) = A^\omega \setminus \bigcup_{x \in A^n\setminus F} A^*xA^{\omega} = A^\omega \setminus A^* (A^n\setminus F) A^{\omega}$? $\endgroup$ – StefanH Sep 27 '13 at 15:48
  • 1
    $\begingroup$ @Stefan If you take $n = 2$ and $F = \{00, 11\}$, then $L(F) = \emptyset \not= A^\omega \setminus A^*(A^n \setminus F)A^\omega$. On the other hand, you're right, the equality $\bigcup_{x\in A^n \setminus F}A^*xA^\omega = A^*(A^n \setminus F)A^\omega$ always holds. $\endgroup$ – J.-E. Pin Sep 28 '13 at 6:32

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.