Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

A characterization of fine words over a finite alphabet

Glen, A.ORCID: 0000-0002-9434-3412 (2006) A characterization of fine words over a finite alphabet. In: International school and conference on Combinatorics, Automata and Number Theory, 8 - 9 May, Liege, Belgium

[img]
Preview
PDF (Presentation) - Other
Download (1MB)

Abstract

To any infinite word t over a finite alphabet A we can associate two infinite words min (t) and max (t) such that any prefix of min (t) (resp. max (t)) is the lexicographically smallest (resp. greatest) amongst the factors of t of the same length. We say that an infinite word t over A is fine if there exists an infinite word s such that, for any lexicographic order, min (t) = a s where a = min (A). In this paper, we characterize fine words; specifically, we prove that an infinite word t is fine if and only if t is either a strict episturmian word or a strict "skew episturmian word". This characterization generalizes a recent result of G. Pirillo, who proved that a fine word over a 2-letter alphabet is either an (aperiodic) Sturmian word, or an ultimately periodic (but not periodic) infinite word, all of whose factors are (finite) Sturmian.

Item Type: Conference Paper
Conference Website: http://www.cant.ulg.ac.be/cant2006/
Notes: See journal article at http://researchrepository.murdoch.edu.au/3878/
URI: http://researchrepository.murdoch.edu.au/id/eprint/3891
Item Control Page Item Control Page

Downloads

Downloads per month over past year