2014/05/21 by Andreas Maletti, Daniel Quernheim
Computer Science · Mathematics · #Algorithm #Automata theory #Automaton #Combinatorics #Commutative property #Computer science #DFA minimization #Deterministic automaton #Deterministic finite automaton #Discrete mathematics #Finite-state machine #Formal Methods in Verification #Mathematical optimization #Mathematics #Minification #Natural Language Processing Techniques #Quantum finite automata #Reduction (mathematics) #Search algorithm #Search tree #Theoretical computer science #Tree (set theory) #Tree automaton #cs.CC #cs.DS #cs.FL #semigroups and automata theory
paper · pdf · doi:10.4204/eptcs.151.22
published in Electronic Proceedings in Theoretical Computer Science 151, 314-326 (Open Publishing Association) · In Proceedings AFL 2014, arXiv:1405.5272
openalex publication_date 2014/05/21 · arxiv created 2014/05/22 · arxiv updated 2014/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Hyper-minimization is a state reduction technique that allows a finite change in the semantics. The theory for hyper-minimization of deterministic weighted tree automata is provided. The presence of weights slightly complicates the situation in comparison to the unweighted case. In addition, the first hyper-minimization algorithm for deterministic weighted tree automata, weighted over commutative semifields, is provided together with some implementation remarks that enable an efficient implementation. In fact, the same run-time O(m log n) as in the unweighted case is obtained, where m is the size of the deterministic weighted tree automaton and n is its number of states.