Unweighted and weighted hyper-minimization

DOI10.1142/S0129054112400485MaRDI QIDQ4923276zbMATH OpenOpenAlexFDO

Authors Andreas Maletti, Daniel Quernheim

Publication date 6 June 2013

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054112400485

zbMATH Keywords

closure propertiesdeterministic finite automatonhyper-minimizationminimizationsemifieldweighted automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Hyper-minimisation of deterministic weighted finite automata over semifields
• scientific article; zbMATH DE number 7361973
• Hyper-minimizing minimized deterministic finite state automata
• An n n algorithm for hyper-minimizing a (minimized) deterministic automaton
• Better hyper-minimization. Not as fast, but fewer errors

Cites work

• A Finite-state Approach to Events in Natural Language Semantics
• A TIME AND SPACE EFFICIENT ALGORITHM FOR MINIMIZING COVER AUTOMATA FOR FINITE LANGUAGES
• An n n algorithm for hyper-minimizing a (minimized) deterministic automaton
• AN EFFICIENT ALGORITHM FOR CONSTRUCTING MINIMAL COVER AUTOMATA FOR FINITE LANGUAGES
• Depth-First Search and Linear Graph Algorithms
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Hierarchical clustering schemes
• scientific article; zbMATH DE number 1142308 (Why is no real title available?)
• HYPER-MINIMIZATION IN O(n²)
• Hyper-minimizing minimized deterministic finite state automata
• Introducing VAUCANSON
• Jewels of Stringology
• Minimal cover-automata for finite languages
• OPTIMAL HYPER-MINIMIZATION
• Similarity relations and cover automata
• State of the art in computational morphology. Workshop on systems and frameworks for computational morphology, SFCM 2009, Zurich, Switzerland, September 4, 2009. Proceedings
• The structure and construction of taxonomic hierarchies

Cited in

(7)

• Minimization of graph weighted models over circular strings
• Hyper-optimization for deterministic tree automata
• Congruence and minimization of deterministic weighted finite automata
• Minimal-determinization of weighted automaton
• Morphisms and Minimisation of Weighted Automata
• Singular value automata and approximate minimization
• Hyper-minimisation of deterministic weighted finite automata over semifields

This page was built for publication: Unweighted and weighted hyper-minimization

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