On prefix normal words
From MaRDI portal
Abstract: We present a new class of binary words: the prefix normal words. They are defined by the property that for any given length , no factor of length has more 's than the prefix of the same length. These words arise in the context of indexing for jumbled pattern matching (a.k.a. permutation matching or Parikh vector matching), where the aim is to decide whether a string has a factor with a given multiplicity of characters, i.e., with a given Parikh vector. Using prefix normal words, we give the first non-trivial characterization of binary words having the same set of Parikh vectors of factors. We prove that the language of prefix normal words is not context-free and is strictly contained in the language of pre-necklaces, which are prefixes of powers of Lyndon words. We discuss further properties and state open problems.
Recommendations
Cited in
(14)- Weighted prefix normal words: mind the gap
- Bubble-flip -- a new generation algorithm for prefix normal words
- Binary jumbled string matching for highly run-length compressible texts
- Abelian antipowers in infinite words
- Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
- Leaf realization problem, caterpillar graphs and prefix normal words
- On prefix normal words and prefix normal forms
- On collapsing prefix normal words
- On infinite prefix normal words
- On infinite prefix normal words
- On combinatorial generation of prefix normal words
- Weighted prefix normal words
- String reconstruction from substring compositions
- The asymptotic number of prefix normal words
This page was built for publication: On prefix normal words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5199967)
