On Generalized Pseudostandard Words Over Binary Alphabets
Alexandre Blondin Massé
Laboratoire d'informatique formelle
Université du Québec à Chicoutimi
Chicoutimi, QC, G7H 2B1
Canada
Geneviève Paquin
Département de mathématiques
Cégep de Saint-Jérôme
Saint-Jérôme, QC J7Z 4V2
Canada
Hugo Tremblay
Laboratoire de combinatoire et d'informatique mathématique
Université du Québec à Montréal
Montréal, QC H3C 3P8
Canada
Laurent Vuillon
Laboratoire de mathématiques
Université de Savoie
Le-Bourget-du-Lac 73376
France
Abstract:
In this paper, we study generalized pseudostandard words over a
two-letter alphabet, which extend the classes of standard Sturmian,
standard episturmian and pseudostandard words, allowing different
involutory antimorphisms instead of the usual palindromic closure or a
fixed involutory antimorphism. We first discuss
pseudoperiods, a useful tool for describing words obtained by
iterated pseudopalindromic closure. Then, we introduce the concept of
normalized directive bi-sequence (Θ, w) of a generalized
pseudostandard word, that is the one that exactly describes all the
pseudopalindromic prefixes of it. We show that a directive bi-sequence
is normalized if and only if its set of factors does not intersect a
finite set of forbidden ones. Moreover, we provide a construction to
normalize any directive bi-sequence. Next, we present an explicit
formula, generalizing the one for the standard episturmian words
introduced by Justin, that computes recursively the next prefix of a
generalized pseudostandard word in term of the previous one. Finally,
we focus on generalized pseudostandard words having complexity 2n,
also called Rote words. More precisely, we prove that the
normalized bi-sequences describing Rote words are completely
characterized by their factors of length 2.
Full version: pdf,
dvi,
ps,
latex
Received July 4 2012;
revised version received January 1 2013.
Published in Journal of Integer Sequences, March 2 2013.
Return to
Journal of Integer Sequences home page