This Special Issue of RAIRO, Theoretical Informatics and Applications
is devoted to full versions of selected papers from the workshop Word
Avoidability, Complexity and Morphisms which took place in Turku
(Finland) on July 2004, as a satellite event of the conference
ICALP'2004.
The topics of this one day workshop concern particular aspects of
Combinatorics on Words: string pattern avoidability, complexities of
finite or infinite words, and free monoids morphims.
The scientific
program of the worshop...

Episturmian morphisms generalize Sturmian morphisms. They are defined
as compositions of exchange morphisms and two particular morphisms
, and . Epistandard morphisms are the morphisms obtained without
considering . In [14], a general study of these morphims
and of conjugacy of morphisms is given.
Here, given a decomposition of
an Episturmian morphism
over exchange morphisms and ,
we consider two problems: how to compute
a decomposition of one conjugate of ;
how to compute a list
of...

Episturmian morphisms generalize sturmian morphisms. They are defined as compositions of exchange morphisms and two particular morphisms $L$, and $\mathbb{D}$. Epistandard morphisms are the morphisms obtained without considering $\mathbb{D}$. In [14], a general study of these morphims and of conjugacy of morphisms is given. Here, given a decomposition of an Episturmian morphism $f$ over exchange morphisms and $\{L,\mathbb{D}\}$, we consider two problems: how to compute a decomposition of one conjugate of $f$; how to compute a list of decompositions...

Episturmian morphisms constitute a powerful tool to study episturmian words. Indeed, any episturmian word can be infinitely decomposed over the set of pure episturmian morphisms. Thus, an episturmian word can be defined by one of its morphic decompositions or, equivalently, by a certain directive word. Here we characterize pairs of words directing the same episturmian word. We also propose a way to uniquely define any episturmian word through a normalization of its directive words. As a consequence...

Episturmian morphisms constitute a powerful tool to study episturmian words. Indeed, any episturmian word can be infinitely decomposed over the set of pure episturmian morphisms. Thus, an episturmian word can be defined by one of its morphic decompositions or, equivalently, by a certain directive word. Here we characterize pairs of words directing the same episturmian word. We also propose a way to uniquely define any episturmian word through a normalization of its directive words. As a consequence...

Among the various ways to construct a characteristic Sturmian word, one of the most used consists in defining an infinite sequence of prefixes that are standard. Nevertheless in any characteristic word , some standard words occur that are not prefixes of . We characterize all standard words occurring in any characteristic word (and so in any Sturmian word) using firstly morphisms, then standard prefixes and finally palindromes.

Download Results (CSV)