On Computational Complexity of Basic Decision Problems of Finite Tree Automata

Margus Veanes

January 1997

This report focuses on the following basic decision problems of finite tree automata: nonemptiness and intersection nonemptiness. There is a comprehensive proof of EXPTIMEcompleteness of the intersection nonemptiness problem, and it is shown that the nonemptiness problem is Pcomplete. 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.

Publication type | TechReport |

Number | 133 |

Series | UPMAIL Technical Report |

Institution | Uppsala University, Computing Science Department |

- High-level Executable Specification of the Universal Plug and Play Architecture
- Model-Based Testing with AsmL .NET
- Symbolic Transducers

> Publications > On Computational Complexity of Basic Decision Problems of Finite Tree Automata