An Assessment of Algorithms for Deriving Failure Deterministic Finite Automata

Authors

  • Madoda Nxumalo University of Pretoria
  • Derrick G Kourie University of Stellenbosch,
  • Loek Cleophas University of Stellenbosch
  • Bruce W Watson University of Stellenbosch

DOI:

https://doi.org/10.18489/sacj.v29i1.456

Keywords:

Failure deterministic finite automata, random automata

Abstract

Failure deterministic finite automata (FDFAs) represent regular languages more compactly than deterministic finite automata (DFAs). Four algorithms that convert arbitrary DFAs to language-equivalent FDFAs are empirically investigated. Three are concrete variants of a previously published abstract algorithm, the DFA-Homomorphic Algorithm (DHA). The fourth builds a maximal spanning tree from the DFA to derive what it calls a delayed input DFA. A first suite of test data consists of DFAs that recognise randomised sets of finite length keywords. Since the classical Aho-Corasick algorithm builds an optimal FDFA from such a set (and only from such a set), it provides benchmark FDFAs against which the performance of the general algorithms can be compared. A second suite of test data consists of random DFAs generated by a specially designed algorithm that also builds language-equivalent FDFAs, some of which may have non-divergent cycles. These random FDFAs provide (not necessarily tight) lower bounds for assessing the effectiveness of the four general FDFA generating algorithms.

Author Biographies

Madoda Nxumalo, University of Pretoria

FASTAR Research Group Department of Computer Science

Derrick G Kourie, University of Stellenbosch,

FASTAR Research Group Department of Information Science, Centre for Artificial Intelligence Research, CSIR

Loek Cleophas, University of Stellenbosch

FASTAR Research Group Department of Information Science, Software Engineering Technology group, Department of Mathematics and Computer Science, Eindhoven University of Technology

Bruce W Watson, University of Stellenbosch

FASTAR Research Group Department of Information Science, Centre for Artificial Intelligence Research, CSIR

Downloads

Additional Files

Published

2017-07-08

Issue

Vol. 29 No. 1 (2017)

Section

Research Papers (general)

License

Copyright of all work published here subsists in the authors. While SACJ retains right of first publication, subsequent re-publication is expressly permitted provided the original SACJ publication is acknowledged and cited, according to the terms detailed below. If plagiarism is detected during review, a paper may be summarily rejected and will not be accepted unless even minor infringements are corrected. Should plagiarism be detected after a paper is published, the Editor reserves the right to withdraw a paper from publication. We expect authors to be honest in representing work as their own, and to respect the time and effort our reviewers put in without an undue burden of policing plagiarism, and hence take violations seriously. SACJ applies the Creative Commons Attribution NonCommercial 4.0 License (CC BY-NC 4.0) to all papers published in this journal. Authors who publish with SACJ agree to the following:
  1. Authors retain copyright and grant SACJ right of first publication. The work is additionally licensed under a Creative Commons Attribution Non-Commercial License that requires others who share the work to acknowledge the work’s authorship and initial publication in SACJ. Should anyone else wish to make commercial use of the work, SACJ cedes the right to the author to negotiate terms and does not expect to be paid any royalties.
  2. Authors may enter into additional arrangements for non-exclusive distribution of the SACJ-published version of the work (e.g., post it to a repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  3. Authors are required to refrain from posting their work online prior to completion of reviews so as not to compromise double-blind reviewing or confuse plagiarism checks.