Currently displaying 1 – 8 of 8

Showing per page

Order by Relevance | Title | Year of publication

Some algorithms to compute the conjugates of episturmian morphisms

Gwenael Richomme — 2003

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Episturmian morphisms generalize sturmian morphisms. They are defined as compositions of exchange morphisms and two particular morphisms L , 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 f over exchange morphisms and { L , 𝔻 } , we consider two problems: how to compute a decomposition of one conjugate of f ; how to compute a list of decompositions...

Foreword

Gwénaël Richomme — 2006

RAIRO - Theoretical Informatics and Applications

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...

Some algorithms to compute the conjugates of Episturmian morphisms

Gwenael Richomme — 2010

RAIRO - Theoretical Informatics and Applications

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...

Directive words of episturmian words : equivalences and normalization

Amy GlenFlorence LevéGwénaël Richomme — 2009

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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...

Directive words of episturmian words: equivalences and normalization

Amy GlenFlorence LevéGwénaël Richomme — 2008

RAIRO - Theoretical Informatics and Applications

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...

Standard factors of Sturmian words

Gwénaël RichommeKalle SaariLuca Q. Zamboni — 2010

RAIRO - Theoretical Informatics and Applications

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.

Page 1

Download Results (CSV)