Geodesic
Linear-time minimization of Aho-Corasick automaton
Diskretnaya Matematika, Tome 35 (2023) no. 2, pp. 125-142.

Voir la notice de l'article provenant de la source Math-Net.Ru

@article{DM_2023_35_2_a7,
     author = {E. I. Furletova},
     title = {Linear-time minimization of {Aho-Corasick} automaton},
     journal = {Diskretnaya Matematika},
     pages = {125--142},
     publisher = {mathdoc},
     volume = {35},
     number = {2},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2023_35_2_a7/}
}
TY  - JOUR
AU  - E. I. Furletova
TI  - Linear-time minimization of Aho-Corasick automaton
JO  - Diskretnaya Matematika
PY  - 2023
SP  - 125
EP  - 142
VL  - 35
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2023_35_2_a7/
LA  - ru
ID  - DM_2023_35_2_a7
ER  - 
%0 Journal Article
%A E. I. Furletova
%T Linear-time minimization of Aho-Corasick automaton
%J Diskretnaya Matematika
%D 2023
%P 125-142
%V 35
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2023_35_2_a7/
%G ru
%F DM_2023_35_2_a7
E. I. Furletova. Linear-time minimization of Aho-Corasick automaton. Diskretnaya Matematika, Tome 35 (2023) no. 2, pp. 125-142. http://geodesic.mathdoc.fr/item/DM_2023_35_2_a7/

[1] Hasib S., Motwani M., Saxena A., “Importance of Aho – Corasick string matching algorithm in real world applications”, Int. J. Comput. Sci. Inf. Technol., 4:3 (2013), 467–469

[2] Aho A. V., Corasick M. J., “Efficient string matching: an aid to bibliographic search”, Commun. ACM, 18:6 (1975), 333–340 | DOI | MR | Zbl

[3] Furletova E., Holub J., Regnier M., Minimized compact automaton for clumps over degenerate patterns, 2019 https://hal.inria.fr/hal-01940837

[4] Hopcroft J., “An $n \log n$ algorithm for minimizing states in a finite automaton”, Proc. Int. Symp. Theory of Machines and Comput. (Haifa, Israel), 1971, 189–196 | DOI | MR

[5] AitMous O., Bassino F., Nicaud C., “Building the minimal automaton of $A*X$ in linear time, when $X$ is of bounded cardinality”, Proc. 21st Annu. Symp. Comb. Pattern Matching (New York, USA), 2010, 275–287 | DOI | MR | Zbl

[6] AitMous O., Bassino F., Nicaud C., “An efficient linear pseudo-minimization algorithm for Aho – Corasick automata”, Proc. 23rd Annu. Symp. Comb. Pattern Matching (Helsinki, Finland), Lect. Notes Comput. Sci., 7353, 2012, 110–123 | DOI | MR

[7] Bubenzer J., “Minimization of acyclic DFAs”, Proc. Prague stringology conf. (Prague, Czech Republic), 2011, 132–146

[8] Fleck A. C., “A simplified view of Nerode equivalence”, Computing Letters, 1:3 (2000), 93–96 | DOI

[9] Stormo G. D., “DNA binding sites: representation and discovery”, Bioinformatics, 16:1 (2000), 16–23 | DOI

[10] Regnier M., Furletova E., Yakovlev V., Roytberg M., “Analysis of pattern overlaps and exact computation of P-values of pattern occurrences numbers: case of Hidden Markov Models”, Algorithms Mol Biol, 9:25 (2014)

[11] Glushkov V. M., “Abstraktnaya teoriya avtomatov”, Uspekhi matematicheskikh nauk, 16:5 (1961), 3–62 | MR