Bell and Shallit recently introduced the Lie complexity of an infinite word s as the function counting for each length the number of conjugacy classes of words whose elements are all factors of s. They proved, using algebraic techniques, that the Lie complexity is bounded above by the first difference of the factor complexity plus one; hence, it is uniformly bounded for words with linear factor complexity, and, in particular, it is at most 2 for Sturmian words, which are precisely the words with factor complexity n+1 for every n. In this note, we provide an elementary combinatorial proof of the result of Bell and Shallit and give an exact formula for the Lie complexity of Sturmian words.

De Luca A., Fici G. (2022). On the Lie complexity of Sturmian words. THEORETICAL COMPUTER SCIENCE, 938, 81-85 [10.1016/j.tcs.2022.10.009].

On the Lie complexity of Sturmian words

Fici G.
2022-01-01

Abstract

Bell and Shallit recently introduced the Lie complexity of an infinite word s as the function counting for each length the number of conjugacy classes of words whose elements are all factors of s. They proved, using algebraic techniques, that the Lie complexity is bounded above by the first difference of the factor complexity plus one; hence, it is uniformly bounded for words with linear factor complexity, and, in particular, it is at most 2 for Sturmian words, which are precisely the words with factor complexity n+1 for every n. In this note, we provide an elementary combinatorial proof of the result of Bell and Shallit and give an exact formula for the Lie complexity of Sturmian words.
2022
Settore INF/01 - Informatica
https://dl.acm.org/doi/10.1016/j.tcs.2022.10.009
De Luca A., Fici G. (2022). On the Lie complexity of Sturmian words. THEORETICAL COMPUTER SCIENCE, 938, 81-85 [10.1016/j.tcs.2022.10.009].
File in questo prodotto:
File Dimensione Formato  
On the Lie complexity of Sturmian words.pdf

Solo gestori archvio

Tipologia: Versione Editoriale
Dimensione 221.97 kB
Formato Adobe PDF
221.97 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
2206.00995.pdf

accesso aperto

Tipologia: Pre-print
Dimensione 122.52 kB
Formato Adobe PDF
122.52 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/573067
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact