Hyper-Minimization for Deterministic Weighted Tree Automata
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2014-05-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1405.5610v1 |
| _version_ | 1818252898389196800 |
|---|---|
| author | Andreas Maletti Daniel Quernheim |
| author_facet | Andreas Maletti Daniel Quernheim |
| author_sort | Andreas Maletti |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-12T16:31:29Z |
| format | Article |
| id | doaj.art-28c1277472544e2f95479dfdb917acfa |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-12T16:31:29Z |
| publishDate | 2014-05-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-28c1277472544e2f95479dfdb917acfa2022-12-22T00:18:46ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802014-05-01151Proc. AFL 201431432610.4204/EPTCS.151.22:33Hyper-Minimization for Deterministic Weighted Tree AutomataAndreas Maletti0Daniel Quernheim1 Universität Leipzig Universität Stuttgart 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.http://arxiv.org/pdf/1405.5610v1 |
| spellingShingle | Andreas Maletti Daniel Quernheim Hyper-Minimization for Deterministic Weighted Tree Automata Electronic Proceedings in Theoretical Computer Science |
| title | Hyper-Minimization for Deterministic Weighted Tree Automata |
| title_full | Hyper-Minimization for Deterministic Weighted Tree Automata |
| title_fullStr | Hyper-Minimization for Deterministic Weighted Tree Automata |
| title_full_unstemmed | Hyper-Minimization for Deterministic Weighted Tree Automata |
| title_short | Hyper-Minimization for Deterministic Weighted Tree Automata |
| title_sort | hyper minimization for deterministic weighted tree automata |
| url | http://arxiv.org/pdf/1405.5610v1 |
| work_keys_str_mv | AT andreasmaletti hyperminimizationfordeterministicweightedtreeautomata AT danielquernheim hyperminimizationfordeterministicweightedtreeautomata |