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) 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) O ( m ? n ) . Finally, a discussion of various other error measures (besides only their number) is provided.
hyper-minimization deterministic tree automaton lossy compression error analysis error optimization