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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

12 Citaten (Scopus)

643 Downloads (Pure)

Samenvatting

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.

Originele taal-2	Engels
Titel	Proceedings of the Prague Stringology Conference 2012 (PSC 2012, Prague, Czech Republic, August 27-28, 2012)
Redacteuren	J. Holub, J. Zdarek
Plaats van productie	Prague
Uitgeverij	Czech Technical University in Prague
Pagina's	28-41
ISBN van geprinte versie	978-80-01-05095-8
Status	Gepubliceerd - 2012

Toegang tot document

publishers versionDefinitieve gepubliceerde versie, 209 KB

Citeer dit

@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. et al.
Proceedings of the Prague Stringology Conference 2012 (PSC 2012, Prague, Czech Republic, August 27-28, 2012). uitgave / J. Holub; J. Zdarek. Prague: Czech Technical University in Prague, 2012. blz. 28-41.

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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 -

Failure deterministic finite automata

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit