A generalized palindromization map in free monoids

DOI10.1016/J.TCS.2012.01.029MaRDI QIDQ714817zbMATH OpenOpenAlexFDO

Authors Alessandro De Luca, Aldo De Luca

Publication date 11 October 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.1823

zbMATH Keywords

Arnoux-Rauzy wordspseudopalindromespalindromic closureEpisturmian wordsgeneralized palindromization map

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15)

Abstract: The palindromization map $psi$ in a free monoid $A^{\ast }$ was introduced in 1997 by the first author in the case of a binary alphabet $A$, and later extended by other authors to arbitrary alphabets. Acting on infinite words, $psi$ generates the class of standard episturmian words, including standard Arnoux-Rauzy words. In this paper we generalize the palindromization map, starting with a given code $X$ over $A$. The new map $ps{i}_X$ maps $X^{\ast }$ to the set $PAL$ of palindromes of $A^{\ast }$. In this way some properties of $psi$ are lost and some are saved in a weak form. When $X$ has a finite deciphering delay one can extend $ps{i}_X$ to $X^{omega}$, generating a class of infinite words much wider than standard episturmian words. For a finite and maximal code $X$ over $A$, we give a suitable generalization of standard Arnoux-Rauzy words, called $X$-AR words. We prove that any $X$-AR word is a morphic image of a standard Arnoux-Rauzy word and we determine some suitable linear lower and upper bounds to its factor complexity. For any code $X$ we say that $ps{i}_X$ is conservative when $ps{i}_X(X^{\ast })subseteq{X}^{\ast }$. We study conservative maps $ps{i}_X$ and conditions on $X$ assuring that $ps{i}_X$ is conservative. We also investigate the special case of morphic-conservative maps $ps{i}_X$, i.e., maps such that $phicircpsi=ps{i}_{X}circphi$ for an injective morphism $phi$. Finally, we generalize $ps{i}_X$ by replacing palindromic closure with $heta$-palindromic closure, where $heta$ is any involutory antimorphism of $A^{\ast }$. This yields an extension of the class of $heta$-standard words introduced by the authors in 2006.

Recommendations

• A palindromization map on free monoids
• Pseudopalindrome closure operators in free monoids
• On different generalizations of episturmian words
• Infinite words rich and almost rich in generalized palindromes
• Characteristic morphisms of generalized episturmian words

Cites work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3991618 (Why is no real title available?)
• scientific article; zbMATH DE number 1259068 (Why is no real title available?)
• scientific article; zbMATH DE number 1988973 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• A palindromization map for the free group
• A palindromization map on free monoids
• Characteristic morphisms of generalized episturmian words
• Episturmian morphisms and a Galois theorem on continued fractions
• Episturmian words and episturmian morphisms
• Episturmian words and some constructions of de Luca and Rauzy
• On different generalizations of episturmian words
• On some problems related to palindrome closure
• On the combinatorics of finite words
• Pseudopalindrome closure operators in free monoids
• Représentation géométrique de suites de complexité $2n+1$
• Sturmian words: structure, combinatorics, and their arithmetics

Cited in

(5)

• The palindromization map
• Sturmian words and the Stern sequence
• Bijective sequential mappings of a free monoid onto another
• A palindromization map on free monoids
• Some extremal properties of the Fibonacci word

This page was built for publication: A generalized palindromization map in free monoids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714817)