The structure of the models of decidable monadic theories of graphs. (English) Zbl 0733.03026

Seese, D.

Ann. Pure Appl. Logic 53, No. 2, 169-195 (1991).

The author devotes the bulk of this paper to a proof of the following undecidability result. If K is a class of graphs such that for each planar graph H there is a planar graph \(G\in K\) with H isomorphic to a minor of G, then both the second-order monadic and weak second-order monadic theories of K are undecidable. This generalizes an earlier theorem of the author.
The author then quickly deduces that if the (weak) monadic theory of a class K of planar graphs is decidable then the tree-width of the graphs in K is universally bounded and there is a class T of trees such that the (weak) monadic theory of K is interpretable in the (weak) monadic theory of T. The paper ends with three open problems.

Reviewer: J.M.Plotkin (East Lansing)

MSC:

03C65	Models of other mathematical theories
03B25	Decidability of theories and sets of sentences
05C99	Graph theory
05C05	Trees
05C10	Planar graphs; geometric and topological aspects of graph theory

Keywords:

undecidability; planar graph; second-order monadic theories; tree-width

References:

[1]	Arnborg, S.; Lagergren, J.; Seese, D., Problems easy for tree-decomposable graphs, extended abstract, (), 38-51, Proc. 15th Int. Colloq. Automata, Languages and Programming (Tampere, Finland, 1988)
[2]	Baudisch, A.; Seese, D.; Tuschik, H.-P.; Weese, M., Decidability and generalized quantifiers, (1980), Akademie Verlag Berlin · Zbl 0442.03011
[3]	Berger, R., The undecidability of the domino problem mem. amer. math. soc., 66, 72, (1966)
[4]	Bollobás, B., Extremal graph theory, (1978), Academic Press London · Zbl 0419.05031
[5]	Börger, E., Spectral problem and completeness of logical decision problems, (), 333-356
[6]	Büchi, J.R., Using determinacy of games to eliminate quantifiers, (), 367-378
[7]	Büchi, J.R.; Siefkes, D., The monadic second order theory of all countable ordinals, Lecture notes in math., 328, (1973), Springer Berlin · Zbl 0298.02050
[8]	Courcelle, B., Recognizability and second-order definability for sets of finite graphs, Preprint no. I-8634, (January 1987), Université de Bordeaux
[9]	Ebbinghaus, H.D.; Flum, J.; Thomas, W., Mathematical logic, Undergraduate texts in math., (1984), Springer New York · Zbl 0556.03001
[10]	Emde Boas, P.van, Dominoes are forever, Report 83-04, (January 1983), Dept. of Math., Univ. of Amsterdam
[11]	Emde Boas, P.van; Savelsbergh, M.W.P., Bounded tilings, an alternative to satisfiability?, Report OS-R8405, (March 1984), Dept. of Operations Research and System Theory, Centre for Mathematics and Computer Science Amsterdam
[12]	Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, (), 27-41
[13]	Friedman, H.; Robertson, N.; Seymour, P.D., The metamathematics of the graph minor theorem, (), 229-261
[14]	Garfunkel, S.; Schmerl, J.H., The undecidability of theories of groupoids with an extra predicate, Proc. amer. math. soc., 42, 286-289, (1974) · Zbl 0273.02032
[15]	Gurevich, Y., Monadic theory of order and topology I, Israel J. math., 27, 299-319, (1977) · Zbl 0359.02061
[16]	Gurevich, Y., Modest theory of short chains I, J. symbolic logic, 44, 481-490, (1979) · Zbl 0464.03013
[17]	Gurevich, Y., Monadic theory of order and topology II, Israel J. math., 34, 45-71, (1979) · Zbl 0428.03034
[18]	Gurevich, Y., Monadic second-order theories, (), 479-506, Chapter XIII
[19]	Gurevich, Y.; Harrington, L., Trees, automata, and games, Proc. ACM STOC, 60-65, (May, 1982), San Francisco
[20]	Gurevich, Y.; Magidor, M.; Shelah, S., The monadic theory of \gw_{2}, J. symbolic logic, 48, 387-398, (1983) · Zbl 0549.03010
[21]	Gurevich, Y.; Shelah, S., Modest theory of short chains II, J. symbolic logic, 44, 491-502, (1979) · Zbl 0464.03014
[22]	Gurevich, Y., The monadic theory and the lsquonext worldrsquo, (), 30
[23]	Gurevich, Y., Monadic theory of order and topology in ZFC, Ann. math. logic, 23, 179-198, (1982) · Zbl 0516.03007
[24]	Gurevich, Y., Interpreting second-order logic in the monadic theory of order, J. symbolic logic, 48, 816-828, (1983) · Zbl 0559.03008
[25]	Gurevich, Y., On the strength of the interpretation method, (July 1986), Preprint
[26]	Halin, R., Zerlegungssatz für unendliche graphen und seine anwendung auf homomorphismen, Math. nachr., 33, 91-105, (1967) · Zbl 0145.20701
[27]	Harary, F., Graph theory, (1969), Addison-Wesley Reading · Zbl 0797.05064
[28]	Harel, D., A simple highly undecidable domino problem (or, a lemma on infinite trees, with applications), Preprint CS83-14, (October 1983), Dept. of Applied Mathematics, The Weizmann Institute of Science
[29]	Harel, D., A general result on infinite trees and its applications, Proc. ACM symp. theory of computation, (May 1984)
[30]	Immerman, N., Languages which capture complexity classes, Proc. 15th annual ACM symp. on the theory of computing, 347-354, (1983)
[31]	Johnson, D.S., The NP-completeness column: an ongoing guide, J. algorithms, 6, (1987) · Zbl 0633.68022
[32]	Korec, J.; Rautenberg, W., Model-interpretability into trees and applications, Arch. math. logik, 17, 97-104, (1976) · Zbl 0324.02041
[33]	Kuratowski, K.; Mostowski, A., Set theory with an introduction to descriptive set theory, (1976), North-Holland Amsterdam · Zbl 0337.02034
[34]	Monk, D., Decidability of the monadic second-order theory of two successors, (May 1982), Preprint
[35]	Muller, D.E.; Schupp, P.E., Pushdown automata, graph ends, second-order logic, and reachability problems, Proc. STOC, 46-54, (1981), Milwaukee
[36]	Rabin, M.O., A simple method for undecidability proofs and some applications, (), 58-68 · Zbl 0192.05502
[37]	Rabin, M.O., Decidable theories, (), 595-629
[38]	Rabin, M.O., Decidability of second order theories and automata on infinite trees, Trans. amer. math. soc., 141, 1-35, (1969) · Zbl 0221.02031
[39]	Robertson, N.; Seymour, P.D., Graphs minors—a survey, surveys in combinatorics 1985, London math. soc. lecture notes, 103, (1985), Proc. 10th British Combinatorial Conference
[40]	Robertson, N.; Seymour, P.D., Graph minors, Part 1: excluding a forest, J. combin. theory, ser. B, 35, 39-61, (1983) · Zbl 0521.05062
[41]	Robertson, N.; Seymour, P.D., Graph minors, Part 2: algorithmic aspects of tree-width, J. algorithms, 7, 309-322, (1986) · Zbl 0611.05017
[42]	Robertson, N.; Seymour, P.D., Graph minors, Part 3: planar tree-width, J. combin. theory, ser. B, 36, 49-64, (1984) · Zbl 0548.05025
[43]	Robertson, N.; Seymour, P.D., Graph minors, Part 4: tree-width and well-quasi-ordering, (1985), Preprint · Zbl 0568.05025
[44]	Robertson, N.; Seymour, P.D., Graph minors, Part 5: excluding a planar graph, 41, 92-114, (1986), J. Combin. Theory, Ser. B · Zbl 0598.05055
[45]	Robertson, N.; Seymour, P.D., Graph minors, Part 6: disjoint paths across a disc, 41, 115-139, (1986), J. Combin. Theory, Ser. B · Zbl 0598.05042
[46]	Robertson, N.; Seymour, P.D., Graph minors, Part 7: disjoint paths on a surface, (1985), Preprint · Zbl 0568.05025
[47]	Robertson, N.; Seymour, P.D., Graph minors, Part 8: A Kuratowski theorem for general surfaces, (1985), Preprint · Zbl 0568.05025
[48]	Robertson, N.; Seymour, P.D., Disjoint paths: a survey, SIAM J. algebraic discrete methods, 6, 300-305, (1985) · Zbl 0565.05045
[49]	Robertson, N.; Seymour, P.D., Graph width and well-ordering: a survey, (), 399-406
[50]	Scheffler, P., What graphs have bounded tree-width?, Proc. 7th fischland-colloquium on discrete mathematics and applications, (1988), to appear in Rostock Math. Kolloq
[51]	Scheffler, P., Die baumweite von graphen als ein mass für die kompliziertheit algorithmischer probleme, Dissertation A, akademie der wissenschaften der DDR, (1989), Berlin · Zbl 0684.68061
[52]	Scheffler, P., A combinatorial and logical approach to linear-time computability, (), Lecture Notes in Computer Science · Zbl 1209.90362
[53]	Schmerl, J.H., Decidability and ℵ_{0}-categoricity of theories of partially ordered sets, J. symbolic logic, 45, 3, 585-611, (1980) · Zbl 0441.03007
[54]	Schmerl, J.H., Decidability and finite axiomatizability of theories of ℵ_{0}-categorical partially ordered sets, J. symbolic logic, 46, 1, 101-120, (1981) · Zbl 0475.03010
[55]	Schmerl, J.H., Arborescent structures, II: interpretability in the theory of trees, Trans. amer. math. soc., 266, 2, 629-643, (1981) · Zbl 0475.03014
[56]	Seese, D.G., Ein unentscheidbarkeitskriterium, (), 772-780 · Zbl 0331.02026
[57]	Seese, D.G., Zur entscheidbarkeit der monadischen theorie zweiter stufe baumartiger graphen, (), 768-772 · Zbl 0362.02037
[58]	Seese, D.G., Entscheidbarkeits- und definierbarkeitsfragen der theorie ‘netzartiger’ graphen, (), 513-517, Teil 1 · Zbl 0254.02036
[59]	Seese, D.G., Entscheidbarkeits- und interpretierbarkeitsfragen monadischer theorien zweiter stufe gewisser klassen von graphen, Diss. A., (1976), Humboldt-Univ Berlin
[60]	Seese, D.G., Some graph theoretical operations and decidability, Math. nachr., 87, 15-21, (1979) · Zbl 0414.03007
[61]	Seese, D.G., Tree-partite graphs and the complexity of algorithms, (), 412-421, Lecture Notes in Computer Science
[62]	Seese, D.G., Tree-partite graphs and the complexity of algorithms, Preprint P-MATH-08/86, (1986), Berlin
[63]	Seese, D.G., Über unentscheidbare erweiterungen von SC, Z. math. logik grundlag. math., 24, 63-71, (1978) · Zbl 0375.02043
[64]	Seese, D.G., Ordered tree-representations of infinite graphs, Preprint P-MATH-12/88, (1988), Berlin
[65]	Seese, D.G.; Wessel, W., Grids and their minors, Preprint P-MATH-41/86, (1986), to appear in J. Combin. Theory, Ser. B. · Zbl 0636.05023
[66]	Shelah, S., The monadic theory of order, Ann. of math., 102, 379-419, (1975) · Zbl 0345.02034
[67]	Shoenfield, J.R., Mathematical logic, (1967), Addison-Wesley Reading, MA · Zbl 0155.01102
[68]	Siefkes, D., Büchi’s monadic second order successor arithmetic, Lecture notes in math., 120, (1970), Springer Berlin · Zbl 0399.03011
[69]	Stupp, J., The lattice-modell is recursive in the original model, (January 1975), Institute of Mathematics, The Hebrew University Jerusalem, Preprint
[70]	Thomas, R., Letter 11, IX, (1985)
[71]	Thomas, R., Letter 09, I, (1986)
[72]	Thomassen, C., Infinite graphs, (), 129-160
[73]	Thomassen, C., Configurations in graphs of large minimum degree, connectivity or chromatic number, (1985), Preprint
[74]	LeTourneau, J.J., Decision problems related to the concept of operation, Ph. D. thesis, (1968), Berkeley
[75]	Tutte, W.T., Graph theory, (1984), Addison-Wesley Reading, MA · Zbl 0554.05001
[76]	Wang, H., Proving theorems by pattern recognition II, Bell syst. tech. J., 40, 1-41, (1961)