150 citations · 496 across the 43 of their papers we have counts for
5 papers · 1 filter
A Taxonomy of Morphic Sequences
Jean-Paul Allouche, Julien Cassaigne, Jeffrey Shallit +1
In this note we classify sequences according to whether they are morphic, pure morphic, uniform morphic, pure uniform morphic, primitive morphic, or pure primitive morphic, and for…
Abelian bordered factors and periodicity
Emilie Charlier, Tero Harju, Svetlana Puzynina +1
A finite word u is said to be bordered if u has a proper prefix which is also a suffix of u, and unbordered otherwise. Ehrenfeucht and Silberger proved that an infinite word is pur…
Subword complexity and decomposition of the set of factors
J. Cassaigne, A. E. Frid, S. Puzynina +1
In this paper we explore a new hierarchy of classes of languages and infinite words and its connection with complexity classes. Namely, we say that a language belongs to the class…
Cyclic Complexity of Words
Julien Cassaigne, Gabriele Fici, Marinella Sciortino +1
We introduce and study a complexity function on words called \emph{cyclic complexity}, which counts the number of conjugacy classes of factors of length of an infinit…
Abelian returns in Sturmian words
Svetlana Puzynina, Luca Q. Zamboni
In this paper we study an abelian version of the notion of return word. Our main result is a new characterization of Sturmian words via abelian returns. Namely, we prove that a wor…