Compression of finite-state automata through failure transitions

DOI10.1016/J.TCS.2014.09.007zbMATH Open1338.68139OpenAlexW2118877442MaRDI QIDQ300258FDOQ300258

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

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

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)

Cites Work

• Efficient string matching
• Finding optimum branchings
• Optimum branchings
• Title not available (Why is that?)
• Title not available (Why is that?)
• Three Partition Refinement Algorithms
• Bisimulation relations for weighted automata
• Fast Pattern Matching in Strings
• The tractability frontier for NFA minimization
• Minimal NFA Problems are Hard
• Title not available (Why is that?)
• A uniform (bi-)simulation-based framework for reducing tree automata

Cited In (2)

• Title not available (Why is that?)
• State-complexity of finite-state devices, state compressibility and incompressibility

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)