Complexity and approximation limits for compressing finite automata
Hardness and Approximation for Compressing Deterministic Finite Automata
Data Structures and Algorithms
Summary
Large state machines called deterministic finite automata (DFAs) are used to recognize patterns in systems like network security. Compressing these machines saves memory and speeds up processing, but finding the smallest possible compressed version is very hard. The paper shows it’s computationally difficult (NP-hard) to find the smallest compressed DFA with flexible default transitions, and proves that the common way of restricting these transitions to simpler structures gets close but not perfect. This helps us understand the limits of how well these machines can be compressed.
What this means in practice
- •For network engineers: Design more memory-efficient pattern matching engines for real-time packet inspection using insights on compression limits.
- •For software optimization teams: Improve heuristic algorithms for reducing DFA size by understanding approximation guarantees and complexity barriers.
A theory result. No direct application yet.
Authors
Philip Bille, Inge Li Gørtz, Christoffer Krogh, Christian Møller Mikkelstrup
Abstract
The delayed deterministic finite automaton ($\text{D}^2\text{FA}$) is a powerful tool for compressing the prohibitively large deterministic finite automata (DFAs) used in modern signature-based deep packet inspection systems. A $\text{D}^2\text{FA}$ augments a DFA with unlabeled default transitions to remove transitions that are similar. This technique works well in practice and has inspired numerous subsequent studies. However, existing approaches do not guarantee a $\text{D}^2\text{FA}$ of optimal size as they restrict the default transitions to form a forest. In this paper, we consider the problem of finding an optimal $\text{D}^2\text{FA}$. We make the key observation that cycles of default transitions can be valid and produce a smaller $\text{D}^2\text{FA}$, provided that for every character in the alphabet, at least one state in the cycle has an outgoing transition labeled by that character. This observation raises fundamental questions concerning the computational complexity of finding an optimal $\text{D}^2\text{FA}$ and the approximation guarantee of the standard (forest-restricted) approach. We answer both questions by showing that it is NP-hard to find an optimal $\text{D}^2\text{FA}$ and by proving that the standard approach provides a $3/2$-approximation to the optimum. To establish NP-hardness, we construct a reduction from set cover using a DFA with gadgets where valid default transition choices correspond to selecting sets. To prove our approximation ratio, we compare the cycles in an optimal solution to a variant where the default transitions form a forest. Finally, we demonstrate that this $3/2$ ratio is tight via a constructed family of DFAs.