Compression of finite-state automata through failure transitions
2014 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 557, 87-100 p.Article in journal (Refereed) Published
Several linear-time algorithms for automata-based pattern matching rely on failure transitions for efficient back-tracking. Like epsilon transitions, failure transition do not consume input symbols, but unlike them, they may only be taken when no other transition is applicable. At a semantic level, this conveniently models catch-all clauses and allows for compact language representation.
This work investigates the transition-reduction problem for deterministic finite-state automata (DFA). The input is a DFA A and an integer k. The question is whether k or more transitions can be saved by replacing regular transitions with failure transitions. We show that while the problem is NP-complete, there are approximation techniques and heuristics that mitigate the computational complexity. We conclude by demonstrating the computational difficulty of two related minimisation problems, thereby cancelling the ongoing search for efficient algorithms.
Place, publisher, year, edition, pages
Elsevier, 2014. Vol. 557, 87-100 p.
failure automata, pattern matching, automata minimisation
Research subject Computer Science
IdentifiersURN: urn:nbn:se:umu:diva-93329DOI: 10.1016/j.tcs.2014.09.007ISI: 000343784800008OAI: oai:DiVA.org:umu-93329DiVA: diva2:747628
FunderSwedish Research Council, 621-2011-6080