Skip to content
printicon
Show report in:

UMINF 13.11

Compact representation of finite automata with failure transitions

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. Recent work demonstrates that failure transitions allow for compact representation of finite-automata in general. For devices with rich alphabets and dense transition functions in particular, the potential savings are great. In this paper, we prove that three important problems related to the introduction of failure transitions are NP-complete, but that efficient approximation is possible for at least one of them.

Keywords

approximation, computational complexity, deterministic finite automata, failure automata, failure transition

Authors

Henrik Björklund , Johanna Björklund and Niklas Zechner

Back Edit this report
Entry responsible: Johanna Bjorklund

Page Responsible: Frank Drewes
2022-09-30