NFA reduction algorithms by means of regular inequalities

DOI10.1016/j.tcs.2004.02.048zbMath1071.68039OpenAlexW2102066200MaRDI QIDQ703569

Fabien Coulon, Jean-Marc Champarnaud

Publication date: 11 January 2005

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

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

zbMATH Keywords

SimulationAutomataPreorderReductionNFANondeterministic automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Minimizing nfa's and regular expressions, On size reduction techniques for multitape automata, On the greatest solutions to weakly linear systems of fuzzy relation inequalities and equations, Left is Better Than Right for Reducing Nondeterminism of NFAs, Bisimulations for fuzzy automata, Nondeterministic automata: equivalence, bisimulations, and uniform relations, Further improvements of determinization methods for fuzzy finite automata, Construction of fuzzy automata from fuzzy regular expressions, A search algorithm for subshift attractors of cellular automata, Fuzzy relation equations and reduction of fuzzy automata, Reduction of fuzzy automata by means of fuzzy quasi-orders, Computation of the greatest right and left invariant fuzzy quasi-orders and fuzzy equivalences, Minimal NFA and biRFSA Languages, Improved algorithms for computing the greatest right and left invariant Boolean matrices and their application

Cites Work

• On the equivalence, containment, and covering problems for the regular and context-free languages
• Minimal NFA Problems are Hard
• Compact and fast algorithms for safe regular expression search
• Rewriting regular inequalities
• On the State Minimization of Nondeterministic Finite Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item