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.
Evgeniya Igorevna Furletova (Wed,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: