×

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].

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)
PDFBibTeX XMLCite