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.
2022
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

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.

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