Failure deterministic finite automata

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

Failure deterministic finite automata

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

10 Citations (Scopus)

283 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 language	English
Title of host publication	Proceedings of the Prague Stringology Conference 2012 (PSC 2012, Prague, Czech Republic, August 27-28, 2012)
Editors	J. Holub, J. Zdarek
Place of Publication	Prague
Publisher	Czech Technical University in Prague
Pages	28-41
ISBN (Print)	978-80-01-05095-8
Publication status	Published - 2012

Access to Document

publishers versionFinal published version, 209 KB

Fingerprint Dive into the research topics of 'Failure deterministic finite automata'. Together they form a unique fingerprint.

Cite this

@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{\textquoteright}s transition diagram has fewer arcs than that of the DFA. A small modification to the classical DFA{\textquoteright}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",

}

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 proceeding › Conference contribution › Academic › peer-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 -