Catalog Home Page

A characterization of fine words over a finite alphabet

Glen, A. (2008) A characterization of fine words over a finite alphabet. Theoretical Computer Science, 391 (1-2). pp. 51-60.

[img]
Preview
PDF - Authors' Version
Download (161kB) | Preview
    Link to Published Version: http://dx.doi.org/10.1016/j.tcs.2007.10.029
    *Open access, no subscription required

    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.

    Publication Type: Journal Article
    Publisher: Elsevier BV
    Copyright: © 2007 Elsevier Ltd.
    URI: http://researchrepository.murdoch.edu.au/id/eprint/3878
    Item Control Page

    Downloads

    Downloads per month over past year