An assessment of algorithms for deriving failure deterministic finite automata

M. Nxumalo, D.G. Kourie, L.G.W.A. Cleophas, B.W. Watson

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
50 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)43-68
Number of pages26
JournalSouth African Computer Journal
Volume29
Issue number1
DOIs
Publication statusPublished - 2017

Fingerprint

Finite automata
language
Formal languages
performance

Keywords

  • Failure deterministic finite automata
  • Random automata

Cite this

@article{bbfa6118b7524cca96b0efe7fee4d0ec,
title = "An assessment of algorithms for deriving failure deterministic finite 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.",
keywords = "Failure deterministic finite automata, Random automata",
author = "M. Nxumalo and D.G. Kourie and L.G.W.A. Cleophas and B.W. Watson",
year = "2017",
doi = "10.18489/sacj.v29i1.456",
language = "English",
volume = "29",
pages = "43--68",
journal = "South African Computer Journal",
issn = "1015-7999",
publisher = "South African Institute of Computer Scientists and Information Technologists",
number = "1",

}

An assessment of algorithms for deriving failure deterministic finite automata. / Nxumalo, M.; Kourie, D.G.; Cleophas, L.G.W.A.; Watson, B.W.

In: South African Computer Journal, Vol. 29, No. 1, 2017, p. 43-68.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - An assessment of algorithms for deriving failure deterministic finite automata

AU - Nxumalo, M.

AU - Kourie, D.G.

AU - Cleophas, L.G.W.A.

AU - Watson, B.W.

PY - 2017

Y1 - 2017

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

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

KW - Failure deterministic finite automata

KW - Random automata

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

U2 - 10.18489/sacj.v29i1.456

DO - 10.18489/sacj.v29i1.456

M3 - Article

AN - SCOPUS:85022022804

VL - 29

SP - 43

EP - 68

JO - South African Computer Journal

JF - South African Computer Journal

SN - 1015-7999

IS - 1

ER -