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

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.
Settore INF/01 - Informatica
https://www.sciencedirect.com/science/article/pii/S0304397522002109?via=ihub
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].
File in questo prodotto:
File Dimensione Formato  
Properties of a class of Toeplitz words.pdf

non disponibili

Tipologia: Versione Editoriale
Dimensione 356.64 kB
Formato Adobe PDF
356.64 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10447/565537
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact