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

## Keywords

- Aho-Corasick algorithm
- Failure deterministic finite automaton