##
**
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 2*n*,
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**