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

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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.

Original languageEnglish
Title of host publicationProceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France
EditorsS. Ben Yahia, J. Konecny
PublisherCEUR-WS.org
Pages87-98
Number of pages12
ISBN (Print)9782954494807
Publication statusPublished - 2015
Event12th International Conference on Concept Lattices and their Applications (CLA 2015), October 13-16, 2015, Clermont-Ferrand, France - Campus des Cézeaux, Clermont-Ferrand, France
Duration: 13 Oct 201516 Oct 2015
http://cla2015.isima.fr/

Publication series

NameCEUR Workshop Proceedings
Volume1466

Conference

Conference12th International Conference on Concept Lattices and their Applications (CLA 2015), October 13-16, 2015, Clermont-Ferrand, France
Abbreviated titleCLA 2015
CountryFrance
CityClermont-Ferrand
Period13/10/1516/10/15
Internet address

Fingerprint

Finite automata

Keywords

  • Aho-Corasick algorithm
  • Failure deterministic finite automaton

Cite this

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 (Eds.), Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France (pp. 87-98). (CEUR Workshop Proceedings; Vol. 1466). CEUR-WS.org.
Nxumalo, Madoda ; Kourie, Derrick G. ; Cleophas, Loek ; Watson, Bruce W. / 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 . editor / S. Ben Yahia ; J. Konecny. CEUR-WS.org, 2015. pp. 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",

}

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 (eds), 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, pp. 87-98, 12th International Conference on Concept Lattices and their Applications (CLA 2015), October 13-16, 2015, Clermont-Ferrand, France, Clermont-Ferrand, France, 13/10/15.

An Aho-Corasick based assessment of algorithms generating failure deterministic finite automata. / Nxumalo, Madoda; Kourie, Derrick G.; Cleophas, Loek; Watson, Bruce W.

Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France . ed. / S. Ben Yahia; J. Konecny. CEUR-WS.org, 2015. p. 87-98 (CEUR Workshop Proceedings; Vol. 1466).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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

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, editors, Proceedings of the Twelfth International Conference on Concept Lattices and Their Applications, October 13-16, 2015, Clermont-Ferrand, France . CEUR-WS.org. 2015. p. 87-98. (CEUR Workshop Proceedings).