A characterization of substitutive sequences using return words (Q1377710): Difference between revisions
From MaRDI portal
Changed an Item |
Set OpenAlex properties. |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 0807.3322 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Représentation géométrique de suites de complexité $2n+1$ / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Mots sans carre et morphismes iterés / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4430300 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Suites algébriques, automates et substitutions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Uniform tag sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ergodic theory on compact spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4079524 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Power of words and recognizability of fixpoints of a substitution / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Substitution dynamical systems - spectral analysis / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3693477 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2953325968 / rank | |||
Normal rank |
Latest revision as of 11:57, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A characterization of substitutive sequences using return words |
scientific article |
Statements
A characterization of substitutive sequences using return words (English)
0 references
11 June 1998
0 references
The purpose of this paper is to give a characterisation of primitive substitutive sequences by using the notion of return word. Let \(u\) be a non-empty prefix of a minimal (or uniformly recurrent) sequence \(x\). A return word of \(u\) is a word separating two successive occurrences of the word \(u\) in \(x\) (possibly with overlap). By coding the initial sequence \(x\) with these return words, one otains a sequence called derivated sequence, defined on a finite alphabet by minimality and still uniformly recurrent. The main result of this paper is the following: a sequence is substitutive if and only if the set of derivated sequences is finite. The proof of the``only if'' part involves a precise study of primitive matrices: in particular, the lengths of the return words over \(u\) are proved to be proportional to the length of \(u\), and the number of return words of \(u\) is bounded independently of \(u\). This very nice result result is to be compared to Cobham's characterisation of substitutions of constant length [\textit{A. Cobham}, Math. Systems Theory 6, 164-192 (1972; Zbl 0253.02029)]: a sequence \(x\) is generated by a q-substitution (or in other words, is \(q\)-automatic) if and only if its q-kernel (i.e., the set of subsequences \((X_{q^kn+r})_n\), where \(0 \leq r \leq q^k-1\) and \(k \geq 0)\) is finite. Note two recent applications of the study of return words: the first one deals with numeration systems [\textit{F. Durand}, Theory Comput. Syst. 31, 169-185 (1998)]and the second one concerns dimension groups of Bratelli diagrams [\textit{F. Durand, B. Host} and \textit{C. Skau}, ``Substitutions , Bratelli diagrams and dimension groups'', to appear in Ergod. Theory Dyn. Syst.].
0 references
primitive substitutions
0 references
return words
0 references
minimal sequences
0 references