Linear-time minimization of Aho–Corasick automaton
Evgeniya Igorevna Furletova · Discrete Mathematics and Applications · 2025
Abstract Aho-Corasick automaton is widely used to find occurrences of words from a given set in a text. In our paper we introduce an equivalence relation ∼ R $\stackrel{R}{\sim}$ on states of Aho–Corasick automaton and prove indistinguishability of ∼ R $\stackrel{R}{\sim}$ -equivalent states. We also propose an algorithm for construction of a ∼ R $\stackrel{R}{\sim}$ -minimal automaton whose states are ∼ R $\stackrel{R}{\sim}$ -equivalence classes. Time and space complexity of this algorithm are linear in the number of states of the original Aho–Corasick automaton. Finally we consider cases in which the relations of ∼ R $\stackrel{R}{\sim}$ -equivalence and indistinguishability are identical, and thus the proposed automaton is minimal.