|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc040304,
author = {Duval, Jean-Pierre and Mouchard, Laurent},
title = {Sequences Obtained from a Series of Permutations of
Borders and Ultimately Periodic Words},
journal = jalc,
year = 1999,
volume = 4,
number = 3,
pages = {205--211},
keywords = {periodicity, permutation of border, ultimately periodic
word},
abstract = {A word of \emph{length} $n$ over an alphabet $A$ is a
sequence $x=a_{1}\ldots a_{n}$ of letters of~$A$. A ``long
enough'' or one-sided word over $A$ is an infinite right
word, that is an infinite sequence $a_{1}\ldots a_{i}\ldots$
of elements of~$A$. An integer $p$ is a \emph{period} of the
word in the interval $[j\mathinner{\cdotp\cdotp}k]$ if we
have $a_{i}=a_{i+p}$ for those indices $i$ and $i+p$ in the
considered interval. An infinite word is \emph{ultimately
periodic} with period $p$ if for a given integer $j$ the
word $a_j\ldots$ has period $p$. A word $u$ is a
\emph{border} of a word $w$ if $u$ is both prefix and suffix
of this word, that is $w=u\cdot x=y\cdot u$ for two words $x$
and $y$. The word $w'=x\cdot u$ is obtained from the word
$w=u\cdot x=y\cdot u$ by the \emph{permutation of
border}~$u$.\par
The question of interest here is to know if a sequence
constructed from an initial word $w$ by iterating permutation
of border is constant from a certain rank. The results
exposed here are an unpublished answer we offered to
{\sc M.\,P.~Sch\"{u}tzenberger} to a question concerning the
characterization of the period of an ultimately periodic
word.}
}