Word Chain Generators for Prefix Normal Words - arXiv 2508.19619v1

Aug 25, 2026

Upload by Maeve

Prefix normal words are studied through new generators based on word chains. A binary word is prefix normal when no substring has more 1s than its prefix of the same length. The work analyzes factors causing a word to fail prefix normality, surveys key properties and open enumeration/testing problems, and introduces graph-based relationships among length-n binary words to organize them via chain generators. These constructions provide new ways to relate and generate prefix normal words for efficient study.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages18

Reading Time45 min

AccessFree to download

Introduction

Prefix normality and prefix normal form

Prefix normal equivalence classes and functions

Related work and open problems

Our contribution: factor properties and word chain generators

arXiv :2508 . 19619v1 [math .CO] 27 Aug 2025 Word Chain Generators for Prefix Normal Words Duncan Adamson 1 , Moritz Dudey2 , Pamela Fleischmann2 , and Annika Huch2 1 University of St Andrews, UK [duncan.adamson@st-andrews.ac.uk](duncan.adamson@st-andrews.ac.uk) 2 Kiel University, Germany, [stu227171@mail.uni-kiel.de](stu227171@mail.uni-kiel.de) ,{fpa,[ahu](ahu}@informatik.uni-kiel.de)[}](ahu}@informatik.uni-kiel.de)[@informatik.uni-kiel.de](ahu}@informatik.uni-kiel.de) Abstract. In 2011, Fici and Lipták 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 offactors 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. 1 Introduction A binary word is prefix normal if it contains no factor (substring) with more occurrences of the letter 1 than the prefix of the same length [11] . For example, 1101 is prefix normal, as every factor contains no more 1s than the prefix of the same length, while 100101 is not prefix normal since its factor 101 contains more 1s than the prefix of the same length, 100 . Research on prefix normal words emerged from work on binary jumbled pattern matching (BJPM) [2,13] . This is a combinatorial problem asking, given a word over the binary alphabet {0, 1} and two natural numbers x and y, whether the word contains a factor with x 0s andy 1s. Note that the order in which these letters appear is considered irrelevant (hence the name jumbled pattern matching) . The description of a word by the number of occurrences of each letter in the underlying alphabet is given by its Parikh vector [15,16] . If we look at all factors of length x + y of a word (sliding window), we can answer a BJPM query in linear time. The indexed jumbled pattern matching problem (e.g., [14]) is concerned with answering multiple such queries on the same word. One way to construct an index is by computing the maximum amount of 1s and 0s in any factor of any length. With that, we can create a new word where each prefix contains exactly the maximum number of 1sin any factor of the same length of the original word. In [11], this new word was introduced as the prefix normal form of a word with respect to 1 . For example, for 00101 we will find that the word 10100 fulfils this property. Thus, with the prefix normal form of a word this maximum can be looked up in linear time, or for multiple searches a look-up table can be computed in linear time such that the maximum can be obtained in O(1) . As shown in [7], for any number between the maximum and the minimum of 0s in a word, the word always contains a factor with that number of occurrences of 0s. That explains why prefix normal forms can be used to create an index for BJPM queries [11] . Calculating the prefix normal form of a word in such a manner requires a quadratic amount of time, and indeed provides one of the main motivations for studying prefix normal words: A more efficient way to generate prefix normal forms would lead to a faster solution for the indexed BJPM problem. As presented in [2], all BJPM queries for a word can be answered in O(1) if its prefix normal form is known. In order to obtain the prefix normal form of a word, Fici and Lipták introduced in [11] the notion of prefix normal equivalence. A word is prefix normal equivalent to another if both have the same prefix normal form. The proof that this is indeed an equivalence relation was presented by Burcsi et al. in [5] . They also showed that each equivalence class has a unique prefix normal representative. Fici and Lipták’s work [11] includes a characterization of prefix

FAQs

What makes a binary word prefix normal?

A binary word is prefix normal if it contains no factor whose number of 1s exceeds the number of 1s in the prefix of the same length.

Why are prefix normal forms useful for jumbled pattern matching?

Prefix normal forms provide fast lookups of maximal counts of 1s and 0s in factors of each length, enabling O(1) answers for indexed jumbled pattern matching queries when the prefix normal form is known.

What new concept does the work introduce?

It introduces prefix normal word chains and corresponding chain generators, using graph relationships among binary words of equal length to systematically relate and generate them.

Aug 25, 2026

Upload by Maeve