Failure deterministic finite automata

D.G. Kourie, B.W. Watson, L.G.W.A. Cleophas, F. Venter

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

9 Citations (Scopus)
201 Downloads (Pure)

Abstract

Inspired by failure functions found in classical pattern matching algorithms, a failure deterministic finite automaton (FDFA) is defined as a formalism to recognise a regular language. An algorithm, based on formal concept analysis, is proposed for deriving from a given deterministic finite automaton (DFA) a language-equivalent FDFA. The FDFA’s transition diagram has fewer arcs than that of the DFA. A small modification to the classical DFA’s algorithm for recognising language elements yields a corresponding algorithm for an FDFA.
Original languageEnglish
Title of host publicationProceedings of the Prague Stringology Conference 2012 (PSC 2012, Prague, Czech Republic, August 27-28, 2012)
EditorsJ. Holub, J. Zdarek
Place of PublicationPrague
PublisherCzech Technical University in Prague
Pages28-41
ISBN (Print)978-80-01-05095-8
Publication statusPublished - 2012

Fingerprint

Finite automata
Formal concept analysis
Formal languages
Pattern matching

Cite this

Kourie, D. G., Watson, B. W., Cleophas, L. G. W. A., & Venter, F. (2012). Failure deterministic finite automata. In J. Holub, & J. Zdarek (Eds.), Proceedings of the Prague Stringology Conference 2012 (PSC 2012, Prague, Czech Republic, August 27-28, 2012) (pp. 28-41). Prague: Czech Technical University in Prague.
Kourie, D.G. ; Watson, B.W. ; Cleophas, L.G.W.A. ; Venter, F. / Failure deterministic finite automata. Proceedings of the Prague Stringology Conference 2012 (PSC 2012, Prague, Czech Republic, August 27-28, 2012). editor / J. Holub ; J. Zdarek. Prague : Czech Technical University in Prague, 2012. pp. 28-41
@inproceedings{84cc0cee773643c28ec19833305fc5b1,
title = "Failure deterministic finite automata",
abstract = "Inspired by failure functions found in classical pattern matching algorithms, a failure deterministic finite automaton (FDFA) is defined as a formalism to recognise a regular language. An algorithm, based on formal concept analysis, is proposed for deriving from a given deterministic finite automaton (DFA) a language-equivalent FDFA. The FDFA’s transition diagram has fewer arcs than that of the DFA. A small modification to the classical DFA’s algorithm for recognising language elements yields a corresponding algorithm for an FDFA.",
author = "D.G. Kourie and B.W. Watson and L.G.W.A. Cleophas and F. Venter",
year = "2012",
language = "English",
isbn = "978-80-01-05095-8",
pages = "28--41",
editor = "J. Holub and J. Zdarek",
booktitle = "Proceedings of the Prague Stringology Conference 2012 (PSC 2012, Prague, Czech Republic, August 27-28, 2012)",
publisher = "Czech Technical University in Prague",
address = "Czech Republic",

}

Kourie, DG, Watson, BW, Cleophas, LGWA & Venter, F 2012, Failure deterministic finite automata. in J Holub & J Zdarek (eds), Proceedings of the Prague Stringology Conference 2012 (PSC 2012, Prague, Czech Republic, August 27-28, 2012). Czech Technical University in Prague, Prague, pp. 28-41.

Failure deterministic finite automata. / Kourie, D.G.; Watson, B.W.; Cleophas, L.G.W.A.; Venter, F.

Proceedings of the Prague Stringology Conference 2012 (PSC 2012, Prague, Czech Republic, August 27-28, 2012). ed. / J. Holub; J. Zdarek. Prague : Czech Technical University in Prague, 2012. p. 28-41.

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

TY - GEN

T1 - Failure deterministic finite automata

AU - Kourie, D.G.

AU - Watson, B.W.

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

AU - Venter, F.

PY - 2012

Y1 - 2012

N2 - Inspired by failure functions found in classical pattern matching algorithms, a failure deterministic finite automaton (FDFA) is defined as a formalism to recognise a regular language. An algorithm, based on formal concept analysis, is proposed for deriving from a given deterministic finite automaton (DFA) a language-equivalent FDFA. The FDFA’s transition diagram has fewer arcs than that of the DFA. A small modification to the classical DFA’s algorithm for recognising language elements yields a corresponding algorithm for an FDFA.

AB - Inspired by failure functions found in classical pattern matching algorithms, a failure deterministic finite automaton (FDFA) is defined as a formalism to recognise a regular language. An algorithm, based on formal concept analysis, is proposed for deriving from a given deterministic finite automaton (DFA) a language-equivalent FDFA. The FDFA’s transition diagram has fewer arcs than that of the DFA. A small modification to the classical DFA’s algorithm for recognising language elements yields a corresponding algorithm for an FDFA.

M3 - Conference contribution

SN - 978-80-01-05095-8

SP - 28

EP - 41

BT - Proceedings of the Prague Stringology Conference 2012 (PSC 2012, Prague, Czech Republic, August 27-28, 2012)

A2 - Holub, J.

A2 - Zdarek, J.

PB - Czech Technical University in Prague

CY - Prague

ER -

Kourie DG, Watson BW, Cleophas LGWA, Venter F. Failure deterministic finite automata. In Holub J, Zdarek J, editors, Proceedings of the Prague Stringology Conference 2012 (PSC 2012, Prague, Czech Republic, August 27-28, 2012). Prague: Czech Technical University in Prague. 2012. p. 28-41