5
$\begingroup$

Let $\xi$ be an ultimately periodic sequence, i.e. there exists finite sequences $p, q \in X^*$ such that $\xi = pq^{\omega}$. Does there exists a $n > 0$ such that the prefix of length $n$ and all infixes of length $n$ determine $\xi$ uniquely, meaning it is the only word with this prefix and infixes.

Some context: I am currently searching for conditions under which a prefix and a set of infixes (or factors) determine a word uniquely. I guess this problem should be solvable for ultimately periodic words. If $\xi$ is just periodic, i.e. $\xi= q^{\omega}$ then this is easy, because choose $q$ minimal, meaning such that it is not a power of some other finite word (such words are called primitive), then the factors of length $n := |q|$ determine $\xi$ unique. For suppose $\eta$ is another word with the same prefix and factors of length $n$, then $\eta = q\tau$, now look at the word $\eta[2...n+1] = q[2...n] x$. Because $\eta$ has the same factors as $\xi$, and all factors of $\xi$ are conjugates (i.e. cyclic permutations) of $q$, there must be $i$ such that $q[2...n] x = q[i+1...n] q[1...i]$. As $q$ was choosen primitive it must have exactly $n$ different conjugate words (this is a well known fact about primitive words) so that $i = 1$ follows (otherwise there would be fewer then $n$ conjugates) which implies $x = q[1..1] = q_1$. Proceeding inductively in this way we see that $\eta = q^{\omega}$. But I am unable to extends this to ultimately periodic sequences, because the prefix $p$ could be anything. So any suggestions or help?

Some remarks on notation: If $w$ is a finite sequence, by $w[i...j]$ I denote the subsequence from the $i$-th up to the $j$ position $w[i...j] = w_i w_{i+1} \cdots w_{j}$.

$\endgroup$
  • 2
    $\begingroup$ choose $n=R+1$, where $R$ is the shortest length for which you have no right special factor (i.e., no factor $w$ such that $wa,wb$ are factors for letters $a\neq b$). Note that $R$ is finite iff $\xi$ is ultimately periodic. $\endgroup$ – Ale De Luca Nov 30 '13 at 0:17
  • $\begingroup$ When you say "a set of infixes" do you literally mean a set, e.g. not only is no order information given but you also don't count multiplicities? $\endgroup$ – Qiaochu Yuan Nov 30 '13 at 20:03
2
$\begingroup$

This is a more detailed version of Alessandro's comment. By a classical theorem of Morse-Hedlund, one has that an infinite word $\eta$ is ultimately periodic iff there exists $m\geq 0$ so that $\eta$ has the same number of factors of length $m$ and $m+1$. Moreover, if $M$ is the number of subwords of length $m$, then the period of $\eta$ is bounded by $M$.

Given $\xi=pq^{\omega}$ with $q$ primitive, we can compute $m$. I guess $m=|p|+|q|+1$ works (probably I don't need the $+1$). Also one can prove $M\leq |p|+|q|$. (This can be found in Combinatorics, Automata and Number Theory handbook edited by Berthe and Rigo.) Now surely $n=2|p|+2|q|+1$ is more than safe enough. If $\eta$ has the same factors and prefixes of length $n$ as $\xi$, then it will have the same number of factors of length $m$ and $m+1$ so be ultimately periodic with period bounded by the same $M=|p|+|q|$. Hopefully you can work out the details from here.

$\endgroup$

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.