Episturmian words: extremal properties and quasiperiodicity

Glen, A.ORCID: 0000-0002-9434-3412 (2007) Episturmian words: extremal properties and quasiperiodicity. In: Algebra and Geometry Research Group Seminar, Matematiska Institutionen, Uppsala Universitet, 25 September, Uppsala, Sweden.

Abstract

"Combinatorics on words" plays a fundamental role in various fields of mathematics, computer science, physics, and biology. Most renowned among its branches is the theory of infinite binary sequences called Sturmian words, which are fascinating in many respects, having been studied from combinatorial, algebraic, and geometric points of view. This well-known family of infinite words has numerous applications in areas such as symbolic dynamics, the study of continued fraction expansion, and also in some domains of physics (quasicrystal modelling) and theoretical computer science (pattern recognition, digital straightness).

Sturmian words admit several equivalent definitions and have many characterizations, which lead to natural generalizations on finite alphabets. One particular extension -- the family of so-called 'episturmian words', introduced by Droubay, Justin, and Pirillo in 2001 -- shares many beautiful properties with Sturmian words; as such, the study of these words has enjoyed a great deal of popularity in recent times.

In this talk, I will first survey previous joint work with Jacques Justin (France) and Giuseppe Pirillo (Italy) concerning extremal properties of Sturmian and episturmian words; in particular, I will describe characterizations of these words via lexicographic orderings. Building upon this work, I will then speak about my recent results on Lyndon and quasiperiodic episturmian words. Specifically, I will show that the aforementioned extremal properties easily yield a characterization of 'strict' episturmian words that are 'infinite Lyndon words', i.e., those that are lexicographically smaller than all of their proper suffixes. In connection with my results on episturmian Lyndon words, Levé and Richomme (2007) have characterized the non-quasiperiodic Sturmian words, proving that a Sturmian word is not quasiperiodic if and only if it is an infinite Lyndon word. Extending this work to episturmian words, I have proved that an episturmian word is not quasiperiodic if it is directed by a 'regular wavy' word. This property reveals that there is a much wider class of episturmian words that are not quasiperiodic, besides those that are infinite Lyndon words. These results and others lead to a characterization of the (non)-quasiperiodic episturmian words with respect to their 'directive
words'.

Item Type:	Conference Item
URI:	http://researchrepository.murdoch.edu.au/id/eprint/19316

Item Control Page

Downloads