Hyper-minimizing minimized deterministic finite state automata

DOI10.1051/ITA:2007061MaRDI QIDQ3549289zbMATH OpenOpenAlexFDO

Authors Andrew Badr, Viliam Geffert, Ian Shipman

Publication date 22 December 2008

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=ITA_2009__43_1_69_0/, https://eudml.org/doc/92908

zbMATH Keywords

finite state automataregular languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton
• Hyper-minimisation Made Efficient
• An n n algorithm for hyper-minimizing a (minimized) deterministic automaton
• Better hyper-minimization. Not as fast, but fewer errors
• OPTIMAL HYPER-MINIMIZATION

Cites work

• An optimal lower bound for nonregular languages
• Converting two-way nondeterministic unary automata into simpler automata.
• Finite automata and unary languages
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 793950 (Why is no real title available?)
• scientific article; zbMATH DE number 3266653 (Why is no real title available?)
• Magic Numbers in the State Hierarchy of Finite Automata
• Optimal simulations between unary automata

Cited in

(31)

• A minimized automaton representation of reachable states
• HARD: A hypercube embedding algorithm for state assignment of finite state machines
• An n n algorithm for hyper-minimizing a (minimized) deterministic automaton
• Hyper-optimization for deterministic tree automata
• Building efficient and compact data structures for simplicial complexes
• Better hyper-minimization. Not as fast, but fewer errors
• On minimising automata with errors
• Closure properties of hyper-minimized automata
• Hyper-minimisation Made Efficient
• OPTIMAL HYPER-MINIMIZATION
• HYPER-MINIMIZATION IN O(n²)
• Surminimisation of automata
• Limits of exact algorithms for inference of minimum size finite state machines
• Hyper-Minimization in O(n 2)
• An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton
• The tractability frontier for NFA minimization
• scientific article; zbMATH DE number 1213009 (Why is no real title available?)
• scientific article; zbMATH DE number 1309169 (Why is no real title available?)
• Unweighted and weighted hyper-minimization
• scientific article; zbMATH DE number 7439745 (Why is no real title available?)
• Minimizing GFG Transition-Based Automata
• The big-O problem
• Minimization and canonization of GFG transition-based automata
• Optimal state reductions of automata with partially specified behaviors
• Computing all -cover automata fast
• Hyper-minimization for deterministic tree automata
• Hyper-minimisation of deterministic weighted finite automata over semifields
• Minimal and hyper-minimal biautomata
• Minimal and hyper-minimal biautomata (extended abstract)
• Optimal state reductions of automata with partially specified behaviors
• Boundary sets of regular and context-free languages

This page was built for publication: Hyper-minimizing minimized deterministic finite state automata

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