Word Chain Generators for Prefix Normal Words
By: Duncan Adamson , Moritz Dudey , Pamela Fleischmann and more
Potential Business Impact:
Finds patterns in computer code to make it better.
In 2011, Fici and Lipt\'ak introduced prefix normal words. A binary word is prefix normal if it has no factor (substring) that contains more occurrences of the letter 1 than the prefix of the same length. Among the open problems regarding this topic are the enumeration of prefix normal words and efficient testing methods. We show a range of characteristics of prefix normal words. These include properties of factors that are responsible for a word not being prefix normal. With word chains and generators, we introduce new ways of relating words of the same length to each other.
Similar Papers
The Morphemic Origin of Zipf's Law: A Factorized Combinatorial Framework
Methodology
Explains how word parts make words and their patterns.
Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform
Combinatorics
Creates secret codes for super-secure math.
Random Text, Zipf's Law, Critical Length,and Implications for Large Language Models
Computation and Language
Explains why words appear often or rarely.