On the Hopcroft's minimization technique for DFA and DFCA

DOI10.1016/j.tcs.2009.02.034zbMath1168.68028OpenAlexW1982412484MaRDI QIDQ1019723

Mihaela Păun, Andrei Păun, Alfonso Rodríguez-Patón

Publication date: 4 June 2009

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

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

zbMATH Keywords

minimizationtime complexitycover automataHopcroft's algorithm

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (7)

Sequentiality Induced by Spike Number in SNP Systems: Small Universal Machines ⋮ A graph theoretic approach to automata minimality ⋮ An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton ⋮ Unnamed Item ⋮ Hopcroft's algorithm and tree-like automata ⋮ An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton ⋮ Minimisation of automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Follow automata.
• Efficient implementation of regular languages using reversed alternating finite automata
• Re-describing an algorithm by Hopcroft
• Describing an algorithm by Hopcroft
• AN EFFICIENT ALGORITHM FOR CONSTRUCTING MINIMAL COVER AUTOMATA FOR FINITE LANGUAGES
• Implementation and Application of Automata
• A TIME AND SPACE EFFICIENT ALGORITHM FOR MINIMIZING COVER AUTOMATA FOR FINITE LANGUAGES
• Around Hopcroft’s Algorithm
• On the State Complexity of Combined Operations
• Minimal cover-automata for finite languages

This page was built for publication: On the Hopcroft's minimization technique for DFA and DFCA