The palindromization map

DOI10.1016/J.DAM.2023.07.008MaRDI QIDQ6048431zbMATH OpenFDO

Authors Dominique Perrin, Christophe Reutenauer

Publication date 14 September 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

compact automatapalindromesprofinite distanceSturmian sequencessuffix automata

Mathematics Subject Classification ID

Free nonabelian groups (20E05) Formal languages and automata (68Q45) Combinatorics on words (68R15)

Abstract: The palindromization map has been defined initially by Aldo de Luca in the context of Sturmian words. It was extended to the free group of rank $2$ by Kassel and the second autho We extend their construction to arbitrary alphabets. We also investigate the suffix automaton and compact suffix automaton of the words obtained by palindromization.

Recommendations

• A palindromization map on free monoids
• A generalized palindromization map in free monoids
• A palindromization map for the free group
• Pseudopalindrome closure operators in free monoids
• Palindromes and Sturmian words

Cites work

• A characterization of infinite LSP words
• A noncommutative extension of Mahler's interpolation theorem
• A palindromization map for the free group
• A topology for free groups and related groups
• Average sizes of suffix trees and DAWGs
• Combinatorial pattern matching. 8th annual symposium, CPM '97, Aarhus, Denmark, June 30 -- July 2, 1997. Proceedings
• Complete inverted files for efficient text retrieval and analysis
• Deterministic generalized automata
• Dimension groups and dynamical systems. Substitutions, Bratteli diagrams and Cantor systems
• Elements of automata theory. Translated from the French by Reuben Thomas
• Episturmian morphisms and a Galois theorem on continued fractions
• Episturmian words and some constructions of de Luca and Rauzy
• From Christoffel Words to Markoff Numbers
• scientific article; zbMATH DE number 1577999 (Why is no real title available?)
• scientific article; zbMATH DE number 3991618 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• On Sturmian graphs
• On-line construction of compact directed acyclic word graphs
• Profinite groups.
• Profinite semigroups and applications.
• Profinite semigroups and symbolic dynamics
• Représentation géométrique de suites de complexité 2n+1
• Special factors and the combinatorics of suffix and factor automata
• Sturmian graphs and integer representations over numeration systems
• Sturmian numeration systems and decompositions to palindromes
• Sturmian words: structure, combinatorics, and their arithmetics
• Suffix Automata and Standard Sturmian Words
• The smallest automaton recognizing the subwords of a text

Cited in

(1)

• Obstructions to return preservation for episturmian morphisms

This page was built for publication: The palindromization map

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