16 citations · 18 across the 6 of their papers we have counts for
6 papers
Word of low complexity without uniform frequencies
Julien Cassaigne, Idrissa Kaboré
In this paper, we construct a uniformely recurrent infinite word of low complexity without uniform frequencies of letters. This shows the optimality of a bound of Boshernitzan, whi…
Cost and dimension of words of zero topological entropy
Julien Cassaigne, Anna E. Frid, Svetlana Puzynina +1
Let denote the free monoid generated by a finite nonempty set In this paper we introduce a new measure of complexity of languages defined in terms of th…
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…
Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More
Julien Cassaigne, Vesa Halava, Tero Harju +1
We study the decidability of three well-known problems related to integer matrix multiplication: Mortality (M), Zero in the Left-Upper Corner (Z), and Zero in the Right-Upper Corne…
Avoiding Abelian powers in binary words with bounded Abelian complexity
Julien Cassaigne, Gwénaël Richomme, Kalle Saari +1
The notion of Abelian complexity of infinite words was recently used by the three last authors to investigate various Abelian properties of words. In particular, using van der Waer…
On possible growth of Toeplitz languages
Julien Cassaigne, Anna Frid, Fedor Petrov
We consider a new family of factorial languages whose subword complexity grows as , where is the root of some transcendent equation. Analytical methods and in particula…