Compression of finite-state automata through failure transitions

DOI10.1016/J.TCS.2014.09.007MaRDI QIDQ300258zbMATH OpenOpenAlexFDO

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

Publication date 27 June 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.09.007

zbMATH Keywords

pattern matchingautomata minimisationfailure automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 2040922
• Minimizing finite automata is computationally hard
• On the Transition Reduction Problem for Finite Automata
• scientific article; zbMATH DE number 176769
• AN EFFICIENT ALGORITHM FOR CONSTRUCTING MINIMAL COVER AUTOMATA FOR FINITE LANGUAGES

Cites work

• scientific article; zbMATH DE number 1045407 (Why is no real title available?)
• scientific article; zbMATH DE number 3285076 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A uniform (bi-)simulation-based framework for reducing tree automata
• Bisimulation relations for weighted automata
• Efficient string matching
• Fast Pattern Matching in Strings
• Finding optimum branchings
• Minimal NFA Problems are Hard
• Optimum branchings
• The tractability frontier for NFA minimization
• Three Partition Refinement Algorithms

Cited in

(2)

• State-complexity of finite-state devices, state compressibility and incompressibility
• scientific article; zbMATH DE number 1775629 (Why is no real title available?)

This page was built for publication: Compression of finite-state automata through failure transitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q300258)