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

cover automatafinite automatahyper-minimisationminimisation

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

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

Cited in

(23)

• An n n algorithm for hyper-minimizing a (minimized) deterministic automaton
• Hyper-optimization for deterministic tree automata
• Beyond hyper-minimisation -- minimising DBAs and DPAs is NP-complete
• Better hyper-minimization. Not as fast, but fewer errors
• On minimising automata with errors
• OPTIMAL HYPER-MINIMIZATION
• Minification processes and their transformations
• Surminimisation of automata
• 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
• scientific article; zbMATH DE number 3896211 (Why is no real title available?)
• The tractability frontier for NFA minimization
• Sliding windows over context-free languages
• Computing all -cover automata fast
• Efficient minimal preference change
• Hyper-optimization for deterministic tree automata
• Notes on hyper-minimization
• Minimal and hyper-minimal biautomata
• Minimal and hyper-minimal biautomata (extended abstract)
• \textsf{tHyENA}: making \textsf{HyENA} even smaller
• Regular languages in the sliding window model
• Minimization of deterministic finite automata modulo the edit distance

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)