A generalized palindromization map in free monoids

DOI10.1016/J.TCS.2012.01.029zbMATH Open1262.68096arXiv1111.1823OpenAlexW2017398076MaRDI QIDQ714817FDOQ714817

Authors: Alessandro De Luca, Aldo De Luca 

Publication date: 11 October 2012

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

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^{*}$ 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.

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

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

zbMATH Keywords

Arnoux-Rauzy wordspseudopalindromespalindromic closureEpisturmian wordsgeneralized palindromization map

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Sturmian words: structure, combinatorics, and their arithmetics
• Episturmian words and some constructions of de Luca and Rauzy
• Représentation géométrique de suites de complexité $2n+1$
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Episturmian words and episturmian morphisms
• On different generalizations of episturmian words
• Pseudopalindrome closure operators in free monoids
• Title not available (Why is that?)
• A palindromization map for the free group
• A palindromization map on free monoids
• Episturmian morphisms and a Galois theorem on continued fractions
• On the combinatorics of finite words
• On some problems related to palindrome closure
• Characteristic morphisms of generalized episturmian words

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)