Parameterized complexity of basic decision problems for tree automata |
| |
Authors: | Witold Charatonik |
| |
Affiliation: | Institute of Computer Science , University of Wroc?aw , Joliot-Curie 15, 50-383 , Wroc?aw , Poland |
| |
Abstract: | There are many decision problems in automata theory (including membership, emptiness, inclusion and universality problems) that are NP-hard for some classes of tree automata (TA). The study of their parameterized complexity allows us to find new bounds of their nonpolynomial time algorithmic behaviours. We present results of such a study for classical TA, rigid tree automata, TA with global equality and disequality and t-DAG automata. As parameters we consider the number of states, the cardinality of the signature, the size of the term or the t-dag and the size of the automaton. |
| |
Keywords: | classical tree automata rigid tree automata tree automata with global equality and disequality t-DAG automata parameterized complexity theory |
|
|