WFRF:(Björklund Johanna)
Sökning: WFRF:(Björklund Johanna) > Compression of fini...
- 5 av 137
- Föregående post
- Nästa post
- Till träfflistan
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
- Tidskriftsartikel (refereegranskat)
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
- Theoretical Computer Science (Sök värdpublikationen i LIBRIS)
Till lärosätets databas
- 5 av 137
- Föregående post
- Nästa post
- Till träfflistan
Hitta mer i SwePub
- Av författaren/redakt...
- Björklund, Henri ...
- Björklund, Johan ...
- Zechner, Niklas
- Om ämnet
-
- NATURVETENSKAP
- NATURVETENSKAP
- och Data och informa ...
- och Datavetenskap
- Artiklar i publikationen
- Theoretical Comp ...
- Av lärosätet
- Umeå universitet
Sök utanför SwePub
- Sök vidare i:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - Nationella bibliotekssystem
- LIBRIS.kb.se
