Catalog Home Page

Characterizations of finite and infinite episturmian words via lexicographic orderings

Glen, A., Justin, J. and Pirillo, G. (2008) Characterizations of finite and infinite episturmian words via lexicographic orderings. European Journal of Combinatorics, 29 (1). pp. 45-58.

[img]
PDF - Authors' Version
Download (214kB)
    Link to Published Version: http://dx.doi.org/10.1016/j.ejc.2007.01.002
    *Open access, no subscription required

    Abstract

    In this paper, we characterize by lexicographic order all finite Sturmian and episturmian words, i.e., all (finite) factors of such infinite words. Consequently, we obtain a characterization of infinite episturmian words in a wide sense (episturmian and episkew infinite words). That is, we characterize the set of all infinite words whose factors are (finite) episturmian. Similarly, we characterize by lexicographic order all balanced infinite words over a 2-letter alphabet; in other words, all Sturmian and skew infinite words, the factors of which are (finite) Sturmian.

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

    Downloads

    Downloads per month over past year