Hyper-minimisation Made Efficient

DOI10.1007/978-3-642-03816-7_31MaRDI QIDQ3182939zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• An n n algorithm for hyper-minimizing a (minimized) deterministic automaton
• Hyper-minimizing minimized deterministic finite state automata
• An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton
• On minimising automata with errors
• Better hyper-minimization. Not as fast, but fewer errors

Cites work

• scientific article; zbMATH DE number 1962773 (Why is no real title available?)
• An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton
• Cuckoo hashing
• Describing an algorithm by Hopcroft
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Dynamic ordered sets with exponential search trees
• Efficient minimization of DFAs with partial transition
• Hopcroft’s Algorithm and Cyclic Automata
• Hyper-Minimization in O(n 2)
• Hyper-minimizing minimized deterministic finite state automata
• Minimal cover-automata for finite languages

Cited in

(21)

• Minification processes and their transformations
• Hyper-optimization for deterministic tree automata
• Computing all \(\ell \)-cover automata fast
• Hyper-optimization for deterministic tree automata
• \textsf{tHyENA}: making \textsf{HyENA} even smaller
• The tractability frontier for NFA minimization
• Minimal and hyper-minimal biautomata
• Efficient minimal preference change
• An n n algorithm for hyper-minimizing a (minimized) deterministic automaton
• OPTIMAL HYPER-MINIMIZATION
• scientific article; zbMATH DE number 3896211 (Why is no real title available?)
• Beyond hyper-minimisation -- minimising DBAs and DPAs is NP-complete
• An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton
• Surminimisation of automata
• On minimising automata with errors
• Minimal and hyper-minimal biautomata (extended abstract)
• Sliding windows over context-free languages
• Hyper-minimizing minimized deterministic finite state automata
• Better hyper-minimization. Not as fast, but fewer errors
• Hyper-Minimization in O(n 2)
• Notes on hyper-minimization

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

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