Seese, Detlef Interpretability and tree automata: A simple way to solve algorithmic problems on graphs closely related to trees. (English) Zbl 0798.68059 Nivat, Maurice (ed.) et al., Tree automata and languages. Amsterdam etc.: North-Holland. Stud. Comput. Sci. Artif. Intell. 10, 83-114 (1992). The main goal of this article is to point out the strong connection between recent results in complexity theory and results on decidability of monadic second-order theories. Both sets of results employ the following three concepts: tiling problems, in order to deduce high complexity or undecidability; tree automata, in order to deduce polynomial time complexity or decidability; the interpretability method, in order to transfer complexity or decidability results from trees to other structures.This article constitutes an attempt to explain why high complexity and undecidability correlate with the fact that the considered structures ‘contain’ large grids, and why polynomial or linear time complexity and decidability correlate with the fact that the structures ‘resemble’ trees.For the entire collection see [Zbl 0781.00007]. Cited in 1 ReviewCited in 6 Documents MSC: 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68R10 Graph theory (including graph drawing) in computer science 03B25 Decidability of theories and sets of sentences 68Q25 Analysis of algorithms and problem complexity 05B45 Combinatorial aspects of tessellation and tiling problems 05C05 Trees 03D15 Complexity of computation (including implicit computational complexity) 05C85 Graph algorithms (graph-theoretic aspects) Keywords:complexity theory; decidability of monadic second-order theories; tree automata PDFBibTeX XMLCite \textit{D. Seese}, Stud. Comput. Sci. Artif. Intell. 10, 83--114 (1992; Zbl 0798.68059)