New results on Nyldon words and Nyldon-like sets

DOI10.1016/J.AAM.2021.102249MaRDI QIDQ820920zbMATH OpenOpenAlexFDO

Publication date 29 September 2021

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

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

Permutations, words, matrices (05A05) Word problems (aspects of algebraic structures) (08A50) Free semigroups, generators and relations, word problems (20M05) Combinatorics on words (68R15)

Abstract: Grinberg defined Nyldon words as those words which cannot be factorized into a sequence of lexicographically nondecreasing smaller Nyldon words. He was inspired by Lyndon words, defined the same way except with "nondecreasing" replaced by "nonincreasing." Charlier, Philibert, and Stipulanti proved that, like Lyndon words, any word has a unique nondecreasing factorization into Nyldon words. They also show that the Nyldon words form a right Lazard set, and equivalently, a right Hall set. In this paper, we provide a new proof of unique factorization into Nyldon words related to Hall set theory and resolve several questions of Charlier et al. In particular, we prove that Nyldon words of a fixed length form a circular code, we prove a result on factorizing powers of words into Nyldon words, and we investigate the Lazard procedure for generating Nyldon words. We show that these results generalize to a new class of Hall sets, of which Nyldon words are an example, that we name "Nyldon-like sets."

Recommendations

Cites work

Cited in

(2)

This page was built for publication: New results on Nyldon words and Nyldon-like sets

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