6533b854fe1ef96bd12ae12a

RESEARCH PRODUCT

Properties of a Class of Toeplitz Words

Gabriele FiciJeffrey Shallit

subject

FOS: Computer and information sciencesDecision procedureSubword complexityDiscrete Mathematics (cs.DM)Combinatorics on wordsSettore INF/01 - InformaticaGeneral Computer ScienceFormal Languages and Automata Theory (cs.FL)Computer Science - Formal Languages and Automata TheoryToeplitz wordTheoretical Computer ScienceComputer Science::Discrete MathematicsPattern avoidanceFOS: MathematicsAutomatic sequenceMathematics - CombinatoricsCombinatorics (math.CO)Computer Science::Formal Languages and Automata TheoryComputer Science - Discrete Mathematics

description

We study the properties of the uncountable set of Stewart words. These are Toeplitz words specified by infinite sequences of Toeplitz patterns of the form $\alpha\beta\gamma$, where $\alpha,\beta,\gamma$ is any permutation of the symbols 0,1,?. We determine the critical exponent of the Stewart words, prove that they avoid the pattern $xxyyxx$, find all factors that are palindromes, and determine their subword complexity. An interesting aspect of our work is that we use automata-theoretic methods and a decision procedure for automata to carry out the proofs.

yearjournalcountryeditionlanguage
2021-12-22
http://arxiv.org/abs/2112.12125