Algorithms for computing small NFAs

DOI10.1007/3-540-45687-2_27MaRDI QIDQ4708581zbMATH OpenFDO

Authors Lucian Ilie, Sheng Yu

Publication date 18 June 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2420/24200328.htm

zbMATH Keywords

algorithmsfollow relationsinvariant equivalencesnondeterministic finite automatapartial derivativespositionsquotientsregular expressions

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
• scientific article; zbMATH DE number 7377986
• The Tractability Frontier for NFA Minimization
• The tractability frontier for NFA minimization
• scientific article; zbMATH DE number 939514
• Implementation and Application of Automata
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• NFA reduction algorithms by means of regular inequalities
• NFA reduction algorithms by means of regular inequalities

Cited in

(23)

• Follow automata.
• Reducing NFAs by invariant equivalences.
• Construction of fuzzy automata from fuzzy regular expressions
• Computation of the greatest right and left invariant fuzzy quasi-orders and fuzzy equivalences
• Partial derivative and position bisimilarity automata
• Efficient weighted expressions conversion
• Bisimulations for fuzzy automata
• NFA reduction algorithms by means of regular inequalities
• Constructing NFAs by optimal use of positions in regular expressions
• scientific article; zbMATH DE number 7377986 (Why is no real title available?)
• A constructing method of regular expression's smaller -NFA
• Computing the follow automaton of an expression
• Reducing the size of NFAs by using equivalences and preorders
• Improved algorithms for computing the greatest right and left invariant Boolean matrices and their application
• On NFA reductions
• Left is Better Than Right for Reducing Nondeterminism of NFAs
• On the greatest solutions to weakly linear systems of fuzzy relation inequalities and equations
• Further improvements of determinization methods for fuzzy finite automata
• NFA reduction algorithms by means of regular inequalities
• Reduction of fuzzy automata by means of fuzzy quasi-orders
• A unified algebraic construction for observer of nondeterministic finite state machines with ϵ -transitions
• Nondeterministic automata: equivalence, bisimulations, and uniform relations
• Fuzzy relation equations and reduction of fuzzy automata

This page was built for publication: Algorithms for computing small NFAs

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