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 |