Deconstructing Subset Construction

John W. Nicol, Markus Frohme · 2025

Read Deconstructing Subset Construction by John W. Nicol, Markus Frohme (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-10319.txt.

Introduction

John Nicol and Markus Frohme revisit a classic task in computing: turning a machine with many possible paths into one with a single clear path. That change can blow up in size, so tools seek ways to shrink the machine as they go. Their approach adds small shrinking steps during the change itself.

A key tool is a registry that tracks which states act the same and merges them early. That merge also opens room for extra cuts. The method can sit inside the classic change process or inside a second known route. Tests on made-up cases and on real sequence data showed the biggest gains in the worst cases, and the code is open.

Catalog record

CREATORJohn W. Nicol, Markus Frohme
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-10319

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Deconstructing Subset Construction John W. Nicol, Markus Frohme Abstract We present a novel perspective on the NFA canonization problem, which introduces intermediate minimization steps to reduce the exploration space on-the-fly. Essential to our approach are so-called equivalence registries which manage information about equivalent states and allow for incorporating further optimization techniques such as convexity closures or simulation to boost performance. Due to the generality of our approach, these concepts can be embedded in classic subset construction or [ 7 ] ’s approach. We evaluate our approach on a set of real-world examples from automatic sequences and observe that we are able to improve especially worst-case scenarios. We implement our approach in an open-source library for users to experiment with. \DeclareSourcemap \maps [datatype=bibtex] \map \step [fieldsource=doi,final] \step [fieldset=url,null] \step [fieldset=isbn,null] \step [fieldset=issn,null] \map \step [fieldsource=eprint,final] \step [fieldset=url,null] Reducing While Determinizing 1 Introduction Finite state machines are foundational models of computation in computer science, where their simplicity and expressive power make them of both theoretical and practical interest. Among the most prominent types are deterministic finite automata (DFAs) and non-deterministic finite automata (NFAs), which are extensively studied for their applications in various domains. DFAs are often preferred over NFAs due to their efficiency in operations such as language equivalence and inclusion, universality, complementation, and other closure properties [ 24 , 22 ] , trace inclusion [ 19 ] , and string matching [ 2 , 19 ] . \Citeauthor RabinS59 [ 33 ] have shown that DFAs and NFAs are equally expressive by transforming NFAs into language-equivalent DFAs via subset (or powerset ) construction . The resulting DFAs may be of exponential size compared to the original NFAs and may not be minimal. The latter can be easily addressed via an additional minimization step [ 23 ] which is often required if the resulting DFAs need to be processed further. A minimal DFA is called canonical since a minimal DFA is unique up to isomorphism [ 24 ] . Constructing the canonical DFA for a given NFA is called the canonization problem [ 44 , 19 ] . The exponential blowup of canonization can be a challenge in practice. However, many NFAs exhibit a notable compression ratio , i.e., the ratio between the size of the determinized (via subset construction) DFA and its minimized version. Real-world cases report compression ratios ranging from 30 ( [ 14 ] ), to 2,500 ( [ 43 ] ), to 5 million ( [ 36 , 38 ] , and addenda for [ 32 ] ). In such situations, materializing the full DFA is often the bottleneck of the canonization process. For certain (NFA-related) problems there exists extensive research on limiting the impact of state blowup, e.g., by using antichains for testing universality and language inclusion [ 47 , 13 ] or bisimulation up to congruence for testing language equivalence [ 5 ] . See [ 10 , 17 ] for surveys on the current state of this work. For the canonization problem, however, the construction of the full DFA is necessary. In this paper, we present OTF – an on-the-fly approach for canonizing NFAs. Instead of treating determinization and minimization as distinct phases of the canonization process, OTF interleaves these concepts by repeatedly minimizing the (partially) constructed DFA of subset construction. Insights about equivalent states of the tentative DFA are then fed back to subset construction in order to reduce the state space requiring exploration. This form of communication is formalized via equivalence registries with which the process can be parameterized, giving OTF a framework character. We present two exemplary implementations of equivalence registries. In our evaluation, we show that OTF is able to improve the performance of canonization for complex real-world NFAs, while remaining competitive for simple systems. We implement these concepts in a public tool 1 1 1 https://github.com/jn1z/OTF for users to experiment with. The idea of exploiting equivalencies to reduce state space appears in various automaton-related fields of research such as linear integer arithmetic [ 21 ] and WS1S formulae [ 15 ] . However, these approaches typically exploit some domain-specific knowledge of their use-cases. In contrast, OTF processes generic NFAs, allowing for a flexible application. Additionally, by processing NFAs directly, OTF is compatible with other directions of NFA minimization including (bi-) simulation reduction, transition pruning, and transition saturation [ 26 , 9 , 25 , 11 ] . A noteworthy alternative to classical NFA canonization is [ 7 ] ’s algorithm [ 7 ] which first determinizes (e.g., via subset construction) the reversed NFA, then reverses the constructed DFA, and finally determinizes it again. This method canonizes the original NFA without requiring an additional minimization step and can outperform classic subset construction in some cases. Since it relies only on determinization, it is compatible with OTF and is included in our evaluation. Finally, [ 19 ] considers the potential of compression ratio by generalizing subset construction although its performance is not compelling. Outline Section 2 introduces preliminary notation and results used throughout the paper. In Section 3 , we discuss the general OTF framework for which Section 4 presents two exemplary equivalence registries. In Section 5 , we evaluate the performance of OTF and compare our approach with the alternatives. Section 6 concludes the paper and gives an outlook on future research. Appendix 0.A provides additional benchmark results. 2 Preliminaries This section introduces basic notations and concepts used throughout the paper. 2.1 Finite Automata Let \Sigma denote a finite, non-empty set of input symbols and \Sigma^{*} denote the set of finite words over \Sigma with \varepsilon denoting the empty word . Definition 1 (Finite State Acceptor) A finite state acceptor (FSA) is a tuple {A=(S,\Sigma,\delta,S_{0},F)} such that • S denotes a finite, non-empty set of states, • \Sigma denotes a finite, non-empty set of input symbols, • \delta\subseteq S\times\Sigma\times S denotes a labeled transition relation, • S_{0}\subseteq S denotes a set of initial states, • and F\subseteq S denotes a set of final or accepting states. Let 2^{X} denote the set of subsets of a set X . By abuse of notation, we may interpret \delta as a function S\times\Sigma\mapsto 2^{S} such that \delta(s,i)=\{t\in S\mid(s,i,t)\in\delta\} . We generalize this view to sets of states and words such that {\delta(Q,i)=\bigcup_{q\in Q}\delta(q,i)} and {\delta(s,\varepsilon)=s,\delta(s,iw)=\delta(\delta(s,i),w)} for {Q\subseteq S,s\in S,i\in\Sigma,w\in\Sigma^{*}} . In the following, we may refer to a set of states Q as a metastate . A word w is accepted by a state {s\in S} iff {\delta(s,w)\cap F\neq\emptyset} . The language of a state s\in S , L(s) , is defined as set of accepted words of s . The language of a metastate Q is defined as {L(Q)=\bigcup_{q\in Q}L(q)} . The language of an FSA A is defined as {L(A)=L(S_{0})} . Two FSAs, A and B , are said to be language equivalent iff {L(A)=L(B)} . We define the reversed automaton of A as the FSA {A^{R}=(S,\Sigma,\delta^{-1},F,S_{0})} where \delta^{-1} denotes the inverse transition relation. 2 2 2 While typically defined on binary relations, the inverse can be easily generalized to higher dimensional tuples: {(a,b,c)^{-1}=(c,b,a)} . The reversed language L(A^{R}) is the language accepted by the reversed automaton A^{R} . We call A a deterministic finite state acc‘ eptor (DFA) if and only

Read the complete text