Hyper-minimisation Made Efficient

DOI10.1007/978-3-642-03816-7_31zbMath1250.68156OpenAlexW1876458857MaRDI QIDQ3182939

Paweł Gawrychowski, Artur Jeż

Publication date: 16 October 2009

Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03816-7_31

zbMATH Keywords

finite automataminimisationcover automatahyper-minimisation

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

The tractability frontier for NFA minimization ⋮ Unnamed Item ⋮ An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton ⋮ Computing All ℓ-Cover Automata Fast ⋮ Better Hyper-minimization ⋮ Hyper-optimization for deterministic tree automata

Cites Work

• Unnamed Item
• Describing an algorithm by Hopcroft
• Hopcroft’s Algorithm and Cyclic Automata
• Dynamic ordered sets with exponential search trees
• Hyper-minimizing minimized deterministic finite state automata
• Hyper-Minimization in O(n 2)
• An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Cuckoo hashing
• Efficient Minimization of DFAs with Partial Transition Functions
• Minimal cover-automata for finite languages

This page was built for publication: Hyper-minimisation Made Efficient