Markov word patterns and a relation on α-words

We prove that all suffixes of a two-way infinite extension of an irrational characteristic word can be represented as Markov word patterns (MWPs) of type 1 and under some conditions, as MWPs of type 2. For each of these MWPs, the pairs of seed words are identified and are described in several differ...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2016-12, Vol.214, p.63-87
Main Authors: Chuan, Wai-Fong, Liao, Fang-Yi, Yu, Fei
Format: Article
Language:English
Subjects:
Adjacent [formula omitted]-word
Irrational characteristic word
Markov word pattern
Seed word
Simple Sturmian word
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We prove that all suffixes of a two-way infinite extension of an irrational characteristic word can be represented as Markov word patterns (MWPs) of type 1 and under some conditions, as MWPs of type 2. For each of these MWPs, the pairs of seed words are identified and are described in several different ways. We prove that the simple Sturmian words are the only Sturmian words that are representable as MWPs, each pair of seed words of which is either a pair of adjacent α-words or adjacent α-words with reverse order.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2016.05.032