6533b82bfe1ef96bd128e149
RESEARCH PRODUCT
On Prefix Normal Words
Gabriele FiciZsuzsanna LiptákGiancarlo MauriAlberto Leporatisubject
permutation matchingcontext-free languagesSearch engine indexingpre-necklacesBinary numberParikh vectorsComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Lyndon wordsnon- standard pattern matchingLyndon wordsCombinatoricsPrefixjumbled pattern matchingPattern matchingParikh vectors; pre-necklaces; Lyndon words; context-free languages; jumbled pattern matching; permutation matching; non- standard pattern matching; indexingComputer Science::Formal Languages and Automata TheoryParikh vectors pre-necklaces Lyndon words context-free languages jumbled pattern matching permutation matching non-standard pattern matching indexingMathematicsindexingdescription
We present a new class of binary words: the prefix normal words. They are defined by the property that for any given length $k$, no factor of length $k$ has more $a$'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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2011-01-01 |