6533b86efe1ef96bd12cc851
RESEARCH PRODUCT
Normal, Abby Normal, Prefix Normal
Zsuzsanna LiptákGabriele FiciJoe SawadaPéter BurcsiFrank Ruskeysubject
binary jumbled pattern matchingEfficient algorithmmembership testBinary numberContext (language use)Prefix Normal Word AlgorithmData_CODINGANDINFORMATIONTHEORYprefix normal wordsOmegaSubstringenumerationCombinatoricsPrefixprefix normal words; binary jumbled pattern matching; normal forms; enumeration; membership test; binary languagesEnumerationnormal formsbinary languagesWord (group theory)Mathematicsdescription
A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. This class of words is important in the context of binary jumbled pattern matching. In this paper we present results about the number \(\textit{pnw}(n)\) of prefix normal words of length n, showing that \(\textit{pnw}(n) =\Omega\left(2^{n - c\sqrt{n\ln n}}\right)\) for some c and \(\textit{pnw}(n) = O \left(\frac{2^n (\ln n)^2}{n}\right)\). We introduce efficient algorithms for testing the prefix normal property and a “mechanical algorithm” for computing prefix normal forms. We also include games which can be played with prefix normal words. In these games Alice wishes to stay normal but Bob wants to drive her “abnormal” – we discuss which parameter settings allow Alice to succeed.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2014-01-01 |