LiveZilla Live Chat Software

Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

On generalized pseudostandard words over binary alphabets

Blondin Massé Alexandre, Paquin Geneviève, Tremblay Hugo et Vuillon Laurent. (2013). On generalized pseudostandard words over binary alphabets. Journal of Integer Sequences, 16,

[img]
Prévisualisation
PDF - Version publiée
376kB

URL officielle: https://cs.uwaterloo.ca/journals/JIS/VOL16/Blondin...

Résumé

In this paper, we study generalized pseudostandard words over a two-letter alpha- bet, which extend the classes of standard Sturmian, standard episturmian and pseu- dostandard words, allowing different involutory antimorphisms instead of the usual palindromic closure or a fixed involutory antimorphism. We first discuss about pseu- doperiods, 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.

Type de document:Article publié dans une revue avec comité d'évaluation
Volume:16
Version évaluée par les pairs:Oui
Date:2013
Sujets:Sciences naturelles et génie > Sciences mathématiques
Département, module, service et unité de recherche:Départements et modules > Département d'informatique et de mathématique
Mots-clés:informatique, palindrome, pseudopalindrome, iterated pseudopalindromic closure, generalized pseudostandard word, normalization, directive bi-sequence, Justin’s formula, Fine and Wilftheorem
Informations complémentaires:Article 13.2.11
Déposé le:18 nov. 2020 20:39
Dernière modification:18 nov. 2020 20:39
Afficher les statistiques de telechargements

Éditer le document (administrateurs uniquement)

Creative Commons LicenseSauf indication contraire, les documents archivés dans Constellation sont rendus disponibles selon les termes de la licence Creative Commons "Paternité, pas d'utilisation commerciale, pas de modification" 2.5 Canada.

Bibliothèque Paul-Émile-Boulet, UQAC
555, boulevard de l'Université
Chicoutimi (Québec)  CANADA G7H 2B1
418 545-5011, poste 5630