Generalised Nyldon words

DOI10.1016/J.TCS.2025.115320MaRDI QIDQ6971740zbMATH OpenFDO

Authors Pamela Fleischmann, Annika Huch, Dirk Nowotka

Publication date 13 June 2025

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

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115320

zbMATH Keywords

generalized lexicographic orderNyldon words

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Review text

Nyldon words are a variant of Lyndon words defined by the nonexistence of a factorization into a non-decreasing sequence of Nyldon words. Their properties are, in general, more complicated than those of Lyndon words.\N\NThe generalized lexicographic order compares finite and infinite words by a prefix relation or by the first mismatch, using an order on letters that depends on the position of the mismatch.\N\NThis paper studies Nyldon words defined by two modifications of the original definition: 1. A generalized lexicographic order is used. 2. The words in the factorization are compared via their infinite powers. The main result is that a word is Nyldon in the just defined sense if and only if it is its own maximal suffix w.r.t. the generalized order. An algorithm for finding the generalized Nyldon conjugate is also given.

Cites work

• A problem in arrangements.
• Combinatorics of Hall trees and Hall words
• Factorizing words over an ordered alphabet
• Free differential calculus. IV: The quotient groups of the lower central series
• Generalized Lyndon factorizations of infinite words
• Generalized Lyndon words
• scientific article; zbMATH DE number 417855 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 812874 (Why is no real title available?)
• scientific article; zbMATH DE number 3082632 (Why is no real title available?)
• Inverse Lyndon words and inverse Lyndon factorizations of words
• Linear work suffix array construction
• Lyndon Words, Free Algebras and Shuffles
• Lyndon words, permutations and trees.
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• New results on Nyldon words and Nyldon-like sets
• Numeration and enumeration
• Nyldon words
• On Burnside's Problem
• Some variations on Lyndon words (invited talk)

This page was built for publication: Generalised Nyldon words

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