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 αβγ, where α,β,γ 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.
Fici G., Shallit J. (2022). Properties of a class of Toeplitz words. THEORETICAL COMPUTER SCIENCE, 922, 1-12 [10.1016/j.tcs.2022.04.006].
Properties of a class of Toeplitz words
Fici G.;
2022-01-01
Abstract
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 αβγ, where α,β,γ 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.
| File | Dimensione | Formato | |
|---|---|---|---|
|
Properties of a class of Toeplitz words.pdf
Solo gestori archvio
Tipologia:
Versione Editoriale
Dimensione
356.64 kB
Formato
Adobe PDF
|
356.64 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
|
2112.12125.pdf
accesso aperto
Tipologia:
Pre-print
Dimensione
478.32 kB
Formato
Adobe PDF
|
478.32 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
