Word Chain Generators for Prefix Normal Words

Duncan Adamson, Moritz Dudey, Pamela Fleischmann, Annika Huch
8/27/2025
math.COcs.CL

No confident code implementation found for this paper. 1 possible match can be shown below.

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 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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. 1 weaker match is hidden by default — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

α-β-Factorization and the Binary Case of Simon's Congruence

74% match2023

The Morphemic Origin of Zipf's Law: A Factorized Combinatorial Framework

70% match2025

On the Emergence of Linear Analogies in Word Embeddings

70% match1 repo42025

Common TF-IDF variants arise as key components in the test statistic of a penalized likelihood-ratio test for word burstiness

70% match1 repo22026

A Latent Variable Model Approach to PMI-based Word Embeddings

70% match1 repo552015

Correlation Does Not Imply Compensation: Complexity and Irregularity in the Lexicon

69% match2024

Cite this paper

@article{adamson2025word,
  title  = {Word Chain Generators for Prefix Normal Words},
  author = {Duncan Adamson and Moritz Dudey and Pamela Fleischmann and Annika Huch},
  year   = {2025},
  eprint = {2508.19619},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2508.19619v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2508.19619.svg)](https://codeofpaper.com/paper/2508.19619)

Discussion