Transfinite Lyndon words

DOI10.1007/978-3-319-21500-6_14MaRDI QIDQ3451100zbMATH OpenOpenAlexFDO

Authors Luc Boasson, Olivier Carton

Publication date 10 November 2015

Published in Developments in Language Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: In this paper, we extend the notion of Lyndon word to transfinite words. We prove two main results. We first show that, given a transfinite word, there exists a unique factorization in Lyndon words that are densely non-increasing, a relaxation of the condition used in the case of finite words. In the annex, we prove that the factorization of a rational word has a special form and that it can be computed from a rational expression describing the word.

Recommendations

• Transfinite Lyndon words
• Lyndon factorization of infinite words
• -Lyndon words
• Infinite Lyndon words

Cites work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3693557 (Why is no real title available?)
• scientific article; zbMATH DE number 3767656 (Why is no real title available?)
• scientific article; zbMATH DE number 3329919 (Why is no real title available?)
• Infinite Lyndon words
• Lyndon factorization of infinite words
• On Burnside's Problem
• On Burnside's Problem. II
• Periodicity and roots of transfinite strings
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• Viennot factorization of infinite words

Cited in

(16)

• Lyndon trees
• Infinite Lyndon words
• Lyndon word decompositions and pseudo orbits on q-nary graphs
• Reprint of: ``\(\omega\)-Lyndon words
• Reprint of: ``Generalized Lyndon factorizations of infinite words
• -Lyndon words
• Nyldon words
• On generalized Lyndon words
• Generalized Lyndon words
• Periodicity and roots of transfinite strings
• scientific article; zbMATH DE number 4002102 (Why is no real title available?)
• scientific article; zbMATH DE number 1375570 (Why is no real title available?)
• Primitive words and Lyndon words in automatic and linearly recurrent sequences
• Transfinite Lyndon words
• Lyndon words versus inverse Lyndon words: queries on suffixes and bordered words
• Lyndon words formalized in Isabelle/HOL

This page was built for publication: Transfinite Lyndon words

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