An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata

Madoda Nxumalo; Derrick G. Kourie; Loek Cleophas; Bruce W. Watson

An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata

Madoda Nxumalo, Derrick G. Kourie, Loek Cleophas, Bruce W. Watson

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

Samenvatting

The Aho-Corasick algorithm derives a failure deterministic finite automaton for finding matches of a finite set of keywords in a text. It has the minimum number of transitions needed for this task. The DFA-Homomorphic Algorithm (DHA) algorithm is more general, deriving from an arbitrary complete deterministic finite automaton a language-equivalent failure deterministic finite automaton. DHA takes formal concepts of a lattice as input. This lattice is built from a state/outtransition formal context that is derived from the complete deterministic finite automaton. In this paper, three general variants of the abstract DHA are benchmarked against the specialised Aho-Corasick algorithm. It is shown that when heuristics for these variants are suitably chosen, the minimality attained by the Aho-Corasick algorithm can be closely approximated. A published non-lattice-based algorithm is also shown to perform well in experiments.

Originele taal-2	Engels
Titel	Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France
Redacteuren	S. Ben Yahia, J. Konecny
Uitgeverij	CEUR-WS.org
Pagina's	87-98
Aantal pagina's	12
ISBN van geprinte versie	9782954494807
Status	Gepubliceerd - 2015
Evenement	12th International Conference on Concept Lattices and their Applications (CLA 2015), October 13-16, 2015, Clermont-Ferrand, France - Campus des Cézeaux, Clermont-Ferrand, Frankrijk Duur: 13 okt. 2015 → 16 okt. 2015 http://cla2015.isima.fr/

Publicatie series

Naam	CEUR Workshop Proceedings
Volume	1466

Congres

Congres	12th International Conference on Concept Lattices and their Applications (CLA 2015), October 13-16, 2015, Clermont-Ferrand, France
Verkorte titel	CLA 2015
Land/Regio	Frankrijk
Stad	Clermont-Ferrand
Periode	13/10/15 → 16/10/15
Internet adres	http://cla2015.isima.fr/

Andere bestanden en links

Link to publication in Scopus

Citeer dit

Nxumalo, M., Kourie, D. G., Cleophas, L., & Watson, B. W. (2015). An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata. In S. Ben Yahia, & J. Konecny (editors), Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France (blz. 87-98). (CEUR Workshop Proceedings; Vol. 1466). CEUR-WS.org.

Nxumalo, Madoda ; Kourie, Derrick G. ; Cleophas, Loek et al. / An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata. Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France . redacteur / S. Ben Yahia ; J. Konecny. CEUR-WS.org, 2015. blz. 87-98 (CEUR Workshop Proceedings).

@inproceedings{a61fefe6d9eb49439bc9cf64bd6b77c7,

title = "An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata",

abstract = "The Aho-Corasick algorithm derives a failure deterministic finite automaton for finding matches of a finite set of keywords in a text. It has the minimum number of transitions needed for this task. The DFA-Homomorphic Algorithm (DHA) algorithm is more general, deriving from an arbitrary complete deterministic finite automaton a language-equivalent failure deterministic finite automaton. DHA takes formal concepts of a lattice as input. This lattice is built from a state/outtransition formal context that is derived from the complete deterministic finite automaton. In this paper, three general variants of the abstract DHA are benchmarked against the specialised Aho-Corasick algorithm. It is shown that when heuristics for these variants are suitably chosen, the minimality attained by the Aho-Corasick algorithm can be closely approximated. A published non-lattice-based algorithm is also shown to perform well in experiments.",

keywords = "Aho-Corasick algorithm, Failure deterministic finite automaton",

author = "Madoda Nxumalo and Kourie, {Derrick G.} and Loek Cleophas and Watson, {Bruce W.}",

year = "2015",

language = "English",

isbn = "9782954494807",

series = "CEUR Workshop Proceedings",

publisher = "CEUR-WS.org",

pages = "87--98",

editor = "{Ben Yahia}, S. and J. Konecny",

booktitle = "Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France",

note = "12th International Conference on Concept Lattices and their Applications (CLA 2015), October 13-16, 2015, Clermont-Ferrand, France, CLA 2015 ; Conference date: 13-10-2015 Through 16-10-2015",

url = "http://cla2015.isima.fr/",

}

Nxumalo, M, Kourie, DG, Cleophas, L & Watson, BW 2015, An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata. in S Ben Yahia & J Konecny (uitgave), Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France . CEUR Workshop Proceedings, vol. 1466, CEUR-WS.org, blz. 87-98, 12th International Conference on Concept Lattices and their Applications (CLA 2015), October 13-16, 2015, Clermont-Ferrand, France, Clermont-Ferrand, Frankrijk, 13/10/15.

An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata. / Nxumalo, Madoda; Kourie, Derrick G.; Cleophas, Loek et al.
Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France . uitgave / S. Ben Yahia; J. Konecny. CEUR-WS.org, 2015. blz. 87-98 (CEUR Workshop Proceedings; Vol. 1466).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

TY - GEN

T1 - An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata

AU - Nxumalo, Madoda

AU - Kourie, Derrick G.

AU - Cleophas, Loek

AU - Watson, Bruce W.

PY - 2015

Y1 - 2015

N2 - The Aho-Corasick algorithm derives a failure deterministic finite automaton for finding matches of a finite set of keywords in a text. It has the minimum number of transitions needed for this task. The DFA-Homomorphic Algorithm (DHA) algorithm is more general, deriving from an arbitrary complete deterministic finite automaton a language-equivalent failure deterministic finite automaton. DHA takes formal concepts of a lattice as input. This lattice is built from a state/outtransition formal context that is derived from the complete deterministic finite automaton. In this paper, three general variants of the abstract DHA are benchmarked against the specialised Aho-Corasick algorithm. It is shown that when heuristics for these variants are suitably chosen, the minimality attained by the Aho-Corasick algorithm can be closely approximated. A published non-lattice-based algorithm is also shown to perform well in experiments.

AB - The Aho-Corasick algorithm derives a failure deterministic finite automaton for finding matches of a finite set of keywords in a text. It has the minimum number of transitions needed for this task. The DFA-Homomorphic Algorithm (DHA) algorithm is more general, deriving from an arbitrary complete deterministic finite automaton a language-equivalent failure deterministic finite automaton. DHA takes formal concepts of a lattice as input. This lattice is built from a state/outtransition formal context that is derived from the complete deterministic finite automaton. In this paper, three general variants of the abstract DHA are benchmarked against the specialised Aho-Corasick algorithm. It is shown that when heuristics for these variants are suitably chosen, the minimality attained by the Aho-Corasick algorithm can be closely approximated. A published non-lattice-based algorithm is also shown to perform well in experiments.

KW - Aho-Corasick algorithm

KW - Failure deterministic finite automaton

UR - http://www.scopus.com/inward/record.url?scp=84950144069&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84950144069

SN - 9782954494807

T3 - CEUR Workshop Proceedings

SP - 87

EP - 98

BT - Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France

A2 - Ben Yahia, S.

A2 - Konecny, J.

PB - CEUR-WS.org

T2 - 12th International Conference on Concept Lattices and their Applications (CLA 2015), October 13-16, 2015, Clermont-Ferrand, France

Y2 - 13 October 2015 through 16 October 2015

ER -

Nxumalo M, Kourie DG, Cleophas L, Watson BW. An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata. In Ben Yahia S, Konecny J, redacteurs, Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France . CEUR-WS.org. 2015. blz. 87-98. (CEUR Workshop Proceedings).

An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata

Samenvatting

Publicatie series

Congres

Andere bestanden en links

Vingerafdruk

Citeer dit