Минимизация автомата Ахо – Корасик за линейное время

Автомат Ахо – Корасик используется при поиске вхождений слов в текст. В работе предложено отношение эквивалентности $\stackrel{R}{\sim}$ на состояниях автомата Ахо – Корасик и доказана неотличимость $\stackrel{R}{\sim}$-эквивалентных состояний. Также разработан алгоритм построения $\stackrel{R}{\sim}$-минимального автомата, состояния которого — классы $\stackrel{R}{\sim}$-эквивалентности. Емкостная и временная сложности алгоритма линейны по числу состояний изначального автомата Ахо – Корасик. Рассмотрены случаи, при которых отношения $\stackrel{R}{\sim}$-эквивалентности и неотличимости состояний тождественны и, соответственно, предложенный автомат является приведенным.