×

zbMATH — the first resource for mathematics

The structure of the models of decidable monadic theories of graphs. (English) Zbl 0733.03026
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.

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
PDF BibTeX Cite
Full Text: DOI
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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.