On Computational Complexity of Basic Decision Problems of Finite Tree Automata

This report focuses on the following basic decision problems of finite tree automata: nonemptiness and intersection nonemptiness. There is a comprehensive proof of EXPTIME-completeness of the intersection nonemptiness problem, and it is shown that the nonemptiness problem is P-complete. A notion of succinctness is considered with respect to which the intersection nonemptiness problem is in fact a succinct version of the nonemptiness problem. The report includes a short survey of closely related problems which shows that there is a rule of thumb: if a decision problem for (deterministic) finite automata is complete for a certain space complexity then the same decision problem for (deterministic) finite tree automata is complete for the corresponding alternating space complexity, but alternating space is precisely deterministic time, only one exponential higher. 1 Introduction Finite tree automata [14, 51] is a natural generalization of classical finite automata to automata that acce..