Sökning: onr:"swepub:oai:DiVA.org:umu-93329" >
Compression of fini...
Compression of finite-state automata through failure transitions
-
- Björklund, Henrik (författare)
- Umeå universitet,Institutionen för datavetenskap
-
- Björklund, Johanna (författare)
- Umeå universitet,Institutionen för datavetenskap
-
- Zechner, Niklas (författare)
- Umeå universitet,Institutionen för datavetenskap
-
(creator_code:org_t)
- Elsevier, 2014
- 2014
- Engelska.
-
Ingår i: Theoretical Computer Science. - : Elsevier. - 0304-3975 .- 1879-2294. ; 557, s. 87-100
- Relaterad länk:
-
https://umu.diva-por... (primary) (Raw object)
-
visa fler...
-
https://doi.org/10.1...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- failure automata
- pattern matching
- automata minimisation
- Computer Science
- datalogi
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas