What question did this study set out to answer?

The aim is to establish an equivalence relation on the Aho-Corasick automaton states and minimize them efficiently.

January 24, 2026

Linear-time minimization of Aho–Corasick automaton

Key Points

The aim is to establish an equivalence relation on the Aho-Corasick automaton states and minimize them efficiently.
Defined an equivalence relation on automaton states.
Proved indistinguishability of states under this relation.
Developed an algorithm to construct a minimal automaton based on the equivalence classes.
Analyzed the time and space complexity of the algorithm.
The proposed algorithm operates in linear time relative to the number of states.
Achieved a minimal automaton from the original Aho-Corasick automaton states.
Identified cases where equivalence and indistinguishability coincide for minimality.

Abstract

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 R on states of Aho–Corasick automaton and prove indistinguishability of ∼ R R -equivalent states. We also propose an algorithm for construction of a ∼ R R -minimal automaton whose states are ∼ R R -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 R -equivalence and indistinguishability are identical, and thus the proposed automaton is minimal.

Mark Helpful

Bookmark

Relay