The paper contains a series of results on infinite prefix normal words. In the finite version, prefix normal words were defined by \textit{G. Fici} and \textit{Z. Lipták} [Lect. Notes Comput. Sci. 6795, 228--238 (2011; Zbl 1221.68128)] as binary words with the property that no factor has more \(1\)s than the prefix of the same length. In particular, a Sturmian word is prefix normal if and only if it is \(1c_\alpha\), where \(c_\alpha\) is the characteristic word of slope \(\alpha\). Then the authors define two prefix normal forms of a given infinite word. This nice notion gives a link to abelian complexity and lexicographic order, and allows one to study prefix normal words related to the paperfolding word, the Thue-Morse word and other known examples.
- A Lower Bound for Jumbled Indexing
- Abelian complexity and frequencies of letters in infinite words
- Abelian complexity function of the Tribonacci word
- Abelian complexity of minimal subshifts
- Abelian complexity of Thue-Morse word over a ternary alphabet
- Algorithms for jumbled pattern matching in strings
- Binary bubble languages and cool-lex order
- Binary jumbled pattern matching on trees and tree-like structures
- Bubble-flip -- a new generation algorithm for prefix normal words
- Clustered Integer 3SUM via Additive Combinatorics
- Computing abelian complexity of binary uniform morphic words
- Efficient oracles for generating binary bubble languages
- Fast and simple jumbled indexing for binary run-length encoded strings
- Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
- Generating necklaces
- scientific article; zbMATH DE number 2024859 (Why is no real title available?)
- scientific article; zbMATH DE number 1737190 (Why is no real title available?)
- scientific article; zbMATH DE number 7428929 (Why is no real title available?)
- Inequalities characterizing standard Sturmian and episturmian words
- Infinite Lyndon words
- Leaf realization problem, caterpillar graphs and prefix normal words
- New algorithms for binary jumbled pattern matching
- On approximate jumbled pattern matching in strings
- On collapsing prefix normal words
- On combinatorial generation of prefix normal words
- On hardness of jumbled indexing
- On infinite prefix normal words
- On prefix normal words
- On prefix normal words and prefix normal forms
- On the asymptotic abelian complexity of morphic words
- Sub-quadratic time and linear space data structures for permutation matching in binary strings
- The abelian complexity of the paperfolding word
- The asymptotic number of prefix normal words
- The asymptotic number of prefix normal words
- On prefix normal words
- Bubble-flip -- a new generation algorithm for prefix normal words
- On infinite prefix normal words
- Bubble-flip -- a new generation algorithm for prefix normal words
- Weighted prefix normal words
- Word chain generators for prefix normal words
- On prefix normal words and prefix normal forms
- On collapsing prefix normal words
- Weighted prefix normal words: mind the gap
This page was built for publication: On infinite prefix normal words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5919082)
