### 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 language | English |
---|---|

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

Editors | S. Ben Yahia, J. Konecny |

Publisher | CEUR-WS.org |

Pages | 87-98 |

Number of pages | 12 |

ISBN (Print) | 9782954494807 |

Publication status | Published - 2015 |

Event | 12th 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 2015 → 16 Oct 2015 http://cla2015.isima.fr/ |

### Publication series

Name | CEUR Workshop Proceedings |
---|---|

Volume | 1466 |

### Conference

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

Abbreviated title | CLA 2015 |

Country | France |

City | Clermont-Ferrand |

Period | 13/10/15 → 16/10/15 |

Internet address |

### Fingerprint

### Keywords

- Aho-Corasick algorithm
- Failure deterministic finite automaton

### Cite this

*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.

}

*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.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › 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

ER -