The Maximal Complexity of Quasiperiodic Infinite Words
A quasiperiod of a finite or infinite string is a word whose occurrences cover every part of the string. An infinite string is referred to as quasiperiodic if it has a quasiperiod. We present a characterisation of the set of infinite strings having a certain word <i>q</i> as quasiperiod...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-11-01
|
| Series: | Axioms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2075-1680/10/4/306 |
| Summary: | A quasiperiod of a finite or infinite string is a word whose occurrences cover every part of the string. An infinite string is referred to as quasiperiodic if it has a quasiperiod. We present a characterisation of the set of infinite strings having a certain word <i>q</i> as quasiperiod via a finite language <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>P</mi><mi>q</mi></msub></semantics></math></inline-formula> consisting of prefixes of the quasiperiod <i>q</i>. It turns out its star root <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mroot><msub><mi>P</mi><mi>q</mi></msub><mrow><mstyle scriptlevel="0" displaystyle="false"><mo>*</mo></mstyle><mspace width="0.166667em"></mspace></mrow></mroot></semantics></math></inline-formula> is a suffix code having a bounded delay of decipherability. This allows us to calculate the maximal subword (or factor) complexity of quasiperiodic infinite strings having quasiperiod <i>q</i> and further to derive that maximally complex quasiperiodic infinite strings have quasiperiods <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>a</mi><mi>b</mi><mi>a</mi></mrow></semantics></math></inline-formula> or <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>a</mi><mi>a</mi><mi>b</mi><mi>a</mi><mi>a</mi></mrow></semantics></math></inline-formula>. It is shown that, for every length <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>l</mi><mo>≥</mo><mn>3</mn></mrow></semantics></math></inline-formula>, a word of the form <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>a</mi><mi>n</mi></msup><mi>b</mi><msup><mi>a</mi><mi>n</mi></msup></mrow></semantics></math></inline-formula> (or <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mi>a</mi><mi>n</mi></msup><mi>b</mi><mi>b</mi><msup><mi>a</mi><mi>n</mi></msup></mrow></semantics></math></inline-formula> if <i>l</i> is even) generates the most complex infinite string having this word as quasiperiod. We give the exact ordering of the lengths <i>l</i> with respect to the achievable complexity among all words of length <i>l</i>. |
|---|---|
| ISSN: | 2075-1680 |