Abstract
| 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 |
Fingerprint
Cite this
}
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 -