pipette
ESEspañol

Every Regular Language Has a Bipartite Cactus Automaton

Mario Grobler, Till Koziel, Sebastian Siebertz

Preprint with a published version

In the authors' words

Thompson's classical construction turns every regular expression into an equivalent epsilon-NFA whose transition graph is series-parallel. The construction uses epsilon-transitions, and eliminating them by the usual shortcut construction need not preserve planarity or the bound of two on the treewidth of the transition graph. Book and Chandra proved that every regular language nevertheless has an epsilon-free NFA with a planar transition graph. We show that the transition graph can in fact be chosen to be a bipartite cactus: every cycle is even, and any two cycles have at most one vertex in common. In particular, it is outerplanar and has treewidth at most two. This is a considerably more simple structure than the general series-parallel guarantee supplied by Thompson's construction. The proof is a direct induction on parity-typed regular expressions and uses only elementary closure properties of cactus graphs.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 9. arXiv. Preprint with a published version.

DOI: 10.4204/EPTCS.454.9

Published version: EPTCS 454, 2026, pp. 117-129

Authors' comment: In Proceedings GandALF 2026, arXiv:2610.08898