Word chain generators for prefix normal words

Duncan Adamson; Moritz Dudey; Pamela Fleischmann; Annika Huch

doi:10.1007/978-3-032-09524-4_5

Word chain generators for prefix normal words

Duncan Adamson, Moritz Dudey, Pamela Fleischmann^*, Annika Huch

^*Corresponding author for this work

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English
Title of host publication	Reachability problems
Subtitle of host publication	19th international conference, RP 2025, proceedings
Editors	Pierre Ganty, Alessio Mansutti
Place of Publication	Cham
Publisher	Springer Nature Switzerland AG
Pages	68-82
Number of pages	15
ISBN (Electronic)	9783032095244
ISBN (Print)	9783032095237
DOIs	https://doi.org/10.1007/978-3-032-09524-4_5
Publication status	Published - 6 Nov 2025
Event	19th International Conference on Reachability Problems - IMDEA Software Institute, Madrid, Spain Duration: 1 Oct 2025 → 3 Oct 2025 https://rp25.software.imdea.org/

Publication series

Name	Lecture notes in computer science
Publisher	Springer
Volume	16230
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	19th International Conference on Reachability Problems
Abbreviated title	RP 2025
Country/Territory	Spain
City	Madrid
Period	1/10/25 → 3/10/25
Internet address	https://rp25.software.imdea.org/

Access to Document

10.1007/978-3-032-09524-4_5

Adamson_2025_RP_Word-chain-generators_AAM_CCBY
Copyright © 2025 the Authors. This work has been made available online in accordance with the University of St Andrews Open Access policy. This accepted manuscript is distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. The final published version of this work is available at https://doi.org/10.1007/978-3-032-09524-4_5
Accepted author manuscript, 581 KBLicence: CC BY

Cite this

@inproceedings{6c70dab1778c465998794fa5ea04a00f,

title = "Word chain generators for prefix normal words",

abstract = "In 2011, Fici and Lipt{\'a}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.",

author = "Duncan Adamson and Moritz Dudey and Pamela Fleischmann and Annika Huch",

year = "2025",

month = nov,

day = "6",

doi = "10.1007/978-3-032-09524-4\_5",

language = "English",

isbn = "9783032095237",

series = "Lecture notes in computer science",

publisher = "Springer Nature Switzerland AG",

pages = "68--82",

editor = "Pierre Ganty and Alessio Mansutti",

booktitle = "Reachability problems",

address = "Switzerland",

note = "19th International Conference on Reachability Problems, RP 2025 ; Conference date: 01-10-2025 Through 03-10-2025",

url = "https://rp25.software.imdea.org/",

}

Adamson, D, Dudey, M, Fleischmann, P & Huch, A 2025, Word chain generators for prefix normal words. in P Ganty & A Mansutti (eds), Reachability problems: 19th international conference, RP 2025, proceedings. Lecture notes in computer science, vol. 16230, Springer Nature Switzerland AG, Cham, pp. 68-82, 19th International Conference on Reachability Problems, Madrid, Spain, 1/10/25. https://doi.org/10.1007/978-3-032-09524-4_5

Word chain generators for prefix normal words. / Adamson, Duncan; Dudey, Moritz; Fleischmann, Pamela et al.
Reachability problems: 19th international conference, RP 2025, proceedings. ed. / Pierre Ganty; Alessio Mansutti. Cham: Springer Nature Switzerland AG, 2025. p. 68-82 (Lecture notes in computer science; Vol. 16230).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Word chain generators for prefix normal words

AU - Adamson, Duncan

AU - Dudey, Moritz

AU - Fleischmann, Pamela

AU - Huch, Annika

PY - 2025/11/6

Y1 - 2025/11/6

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

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

UR - https://www.scopus.com/pages/publications/105022143753

U2 - 10.1007/978-3-032-09524-4_5

DO - 10.1007/978-3-032-09524-4_5

M3 - Conference contribution

AN - SCOPUS:105022143753

SN - 9783032095237

T3 - Lecture notes in computer science

SP - 68

EP - 82

BT - Reachability problems

A2 - Ganty, Pierre

A2 - Mansutti, Alessio

PB - Springer Nature Switzerland AG

CY - Cham

T2 - 19th International Conference on Reachability Problems

Y2 - 1 October 2025 through 3 October 2025

ER -