NFA reduction algorithms by means of regular inequalities

DOI10.1016/J.TCS.2004.02.048MaRDI QIDQ703569zbMATH OpenOpenAlexFDO

Authors Jean-Marc Champarnaud, Fabien Coulon

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

PreorderSimulationAutomataReductionNFANondeterministic automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 2040906
• Theory Is Forever
• Combinatorial Pattern Matching
• A non-deterministic finite automata minimization method based on the preorder relation
• Left is Better Than Right for Reducing Nondeterminism of NFAs

Cites work

• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 2053215 (Why is no real title available?)
• scientific article; zbMATH DE number 2081039 (Why is no real title available?)
• scientific article; zbMATH DE number 1929949 (Why is no real title available?)
• scientific article; zbMATH DE number 3189697 (Why is no real title available?)
• Compact and fast algorithms for safe regular expression search
• Minimal NFA Problems are Hard
• On the State Minimization of Nondeterministic Finite Automata
• On the equivalence, containment, and covering problems for the regular and context-free languages
• Rewriting regular inequalities

Cited in

(21)

• Left is better than right for reducing nondeterminism of NFAs
• scientific article; zbMATH DE number 2040906 (Why is no real title available?)
• Bisimulations for fuzzy automata
• A non-deterministic finite automata minimization method based on the preorder relation
• Fuzzy relation equations and reduction of fuzzy automata
• Further improvements of determinization methods for fuzzy finite automata
• Improved algorithms for computing the greatest right and left invariant Boolean matrices and their application
• Reduction of fuzzy automata by means of fuzzy quasi-orders
• Left is Better Than Right for Reducing Nondeterminism of NFAs
• Theory Is Forever
• On size reduction techniques for multitape automata
• scientific article; zbMATH DE number 1929949 (Why is no real title available?)
• Minimal NFA and biRFSA Languages
• A search algorithm for subshift attractors of cellular automata
• Combinatorial Pattern Matching
• On the greatest solutions to weakly linear systems of fuzzy relation inequalities and equations
• Nondeterministic automata: equivalence, bisimulations, and uniform relations
• Computation of the greatest right and left invariant fuzzy quasi-orders and fuzzy equivalences
• The best nondeterministic representations of finite orderings.
• Construction of fuzzy automata from fuzzy regular expressions
• Minimizing nfa's and regular expressions

This page was built for publication: NFA reduction algorithms by means of regular inequalities

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