Reducing NFAs by invariant equivalences.

DOI10.1016/S0304-3975(03)00311-6zbMath1059.68064OpenAlexW4212834144MaRDI QIDQ1426461

Lucian Ilie, Sheng Yu

Publication date: 14 March 2004

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(03)00311-6

zbMATH Keywords

Derivatives of regular expressionsRegular expressionsAutomata minimizationInvariant equivalencesNon-deterministic finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (16)

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 ⋮ On the Inference of Finite State Automata from Positive and Negative Data ⋮ Nondeterministic automata: equivalence, bisimulations, and uniform relations ⋮ Postfix automata ⋮ Correctly Slicing Extended Finite State Machines ⋮ Further improvements of determinization methods for fuzzy finite automata ⋮ An aperiodic set of 11 Wang tiles ⋮ 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 ⋮ Improved algorithms for computing the greatest right and left invariant Boolean matrices and their application

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• From regular expressions to deterministic automata
• Partial derivatives of regular expressions and finite automaton constructions
• Regular expressions into finite automata
• From regular expressions to DFA's using compressed NFA's
• Follow automata.
• THE ABSTRACT THEORY OF AUTOMATA
• Computingϵ-Free NFA from Regular Expressions inO(nlog²(n)) Time
• Programming Techniques: Regular expression search algorithm
• Derivatives of Regular Expressions
• Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata

This page was built for publication: Reducing NFAs by invariant equivalences.