18 citations · 84 across the 20 of their papers we have counts for
Showing 2014 · cs.FLShow all
2 papers · 2 filters
cs.FL2014
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…
cs.FL2014
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…