Hyper-optimization for deterministic tree automata

Hyper-minimization is a lossy minimization technique that allows a finite number of errors. It was already demonstrated that hyper-minimization can be performed efficiently for deterministic string automata and (bottom-up) deterministic tree automata (DTAs). The asymptotically fastest DTA hyper-minimization algorithms run in time O ( m ⋅ log ⁡ n ), where m is the size of the DTA and n is the number of its states. In this contribution, the committed errors are investigated. First, the structure of all hyper-minimal DTAs for a given tree language is characterized, which also yields a formula for the number of such hyper-minimal DTAs. Second, an algorithm is developed that computes the number of errors that a given hyper-minimal DTA commits when compared to a given reference DTA. Third, it is shown that optimal hyper-minimization (i. e. , computing a hyper-minimal DTA that commits the least number of errors of all hyper-minimal DTAs) can be achieved in time O ( m ⋅ n ). Finally, a discussion of various other error measures (besides only their number) is provided.

Authors

• Andreas Maletti

Keywords

• Hyper-minimization
• Deterministic tree automaton
• Lossy compression
• Error analysis
• Error optimization