Name
Abstract | ||
|---|---|---|
To any infinite word t over a finite alphabet A we can associate two infinite words min(t) and max(t) such that any prefix of min(t) (resp. max(t)) is the lexicographically smallest (resp. greatest) amongst the factors of t of the same length. We say that an infinite word t over A is fine if there exists an infinite word s such that, for any lexicographic order, min(t)=as where a=min(A). In this paper, we characterize fine words; specifically, we prove that an infinite word t is fine if and only if t is either a strict episturmian word or a strict ''skew episturmian word''. This characterization generalizes a recent result of G. Pirillo, who proved that a fine word over a 2-letter alphabet is either an (aperiodic) Sturmian word, or an ultimately periodic (but not periodic) infinite word, all of whose factors are (finite) Sturmian. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.tcs.2007.10.029 | Theoretical Computer Science |
Keywords | Field | DocType |
episturmian word,combinatorics on words,infinite word,fine word,skew episturmian word,lexicographic order,arnoux–rauzy sequence,2-letter alphabet,g. pirillo,skew word,finite alphabet,sturmian word,strict episturmian word,infinite words min,arnoux-rauzy sequence,skew word. | Combinatorics,Sturmian word,Existential quantification,Arithmetic,Prefix,Partial word,Skew,Lexicographical order,Aperiodic graph,Periodic graph (geometry),Mathematics | Journal |
Volume | Issue | ISSN |
391 | 1-2 | Theoretical Computer Science |
Citations | PageRank | References |
7 | 0.51 | 10 |
Authors | ||
1 | ||