×

Trees, grids, and MSO decidability: from graphs to matroids. (English) Zbl 1093.03006

Summary: Monadic second-order (MSO) logic has proved to be a useful tool in many areas of application, reaching from decidability and complexity to picture processing, correctness of programs and parallel processes. To characterize the structural borderline between decidability and undecidability is a classical research problem here. This problem is related to questions in computational complexity, especially to the model checking problem, for which many tools developed in the area of decidability have proved to be useful. For more than two decades it was conjectured [D. Seese, “The structure of the models of decidable monadic theories of graphs”, Ann. Pure Appl. Logic 53, 169–195 (1991; Zbl 0733.03026)] that decidability of monadic theories of countable structures implies that the theory can be reduced via interpretability to a theory of trees.
It is one of the main goals of this article to prove a variant of this conjecture for matroids representable over a finite field. (Matroids can be viewed as a wide generalization of graphs, and they seem to capture some second-order properties in a more suitable way than graphs themselves, cf. the recent development in matroid structure theory [J. F. Geelen, A. H. M. Gerards, and G. P. Whittle, “Branch-width and well-quasi-ordering in matroids and graphs”, J. Comb. Theory, Ser. B 84, 270–290 (2002; Zbl 1037.05013); J. F. Geelen, A. H. M. Gerards, N. Robertson, and G. P. Whittle, “Excluding a planar graph from a GF\((q)\)-representable matroid”, manuscript (2003)]). More exactly we prove, for every finite field \(\mathbb F\), that any class of \(\mathbb F\)-representable matroids with a decidable MSO theory must have uniformly bounded branch-width. Moreover, we show that bounding the branch-width of all matroids in general is not sufficient to obtain a decidable MSO theory.
Our paper gives a (rather detailed) introduction to these different subjects, and shows that a blend of ideas and methods from logic together with structural matroid theory can lead to new tools and algorithms, and can shed light on some old open problems.

MSC:

03B25 Decidability of theories and sets of sentences
03B15 Higher-order logic; type theory (MSC2010)
05B35 Combinatorial aspects of matroids and geometric lattices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arnborg, S.; Corneil, D. G.; Proskurowski, A., Complexity of finding embeddings in a \(k\)-tree, SIAM J. Algebraic Discrete Methods, 8, 277-284 (1987) · Zbl 0611.05022
[2] S. Arnborg, J. Lagergren, D. Seese, Problems easy for tree-decomposable graphs (extended abstract), Proc. 15th ICALP, Lecture Notes in Computer Science, Vol. 317, Springer, Berlin, 1988, pp. 38-51.; S. Arnborg, J. Lagergren, D. Seese, Problems easy for tree-decomposable graphs (extended abstract), Proc. 15th ICALP, Lecture Notes in Computer Science, Vol. 317, Springer, Berlin, 1988, pp. 38-51. · Zbl 0662.03030
[3] Arnborg, S.; Lagergren, J.; Seese, D., Easy problems for tree-decomposable graphs, J. Algorithms, 12, 308-340 (1991) · Zbl 0734.68073
[4] K. Barthelmann, On equational graphs, Technical Report 9, Universität Mainz, Institut für Informatik, 1997.; K. Barthelmann, On equational graphs, Technical Report 9, Universität Mainz, Institut für Informatik, 1997.
[5] A. Baudisch, Zur Methatheorie abelscher Gruppen, Dissertation, Humboldt-Universitaet zu Berlin, 1974 (translation: To the meta-theory of abelian groups).; A. Baudisch, Zur Methatheorie abelscher Gruppen, Dissertation, Humboldt-Universitaet zu Berlin, 1974 (translation: To the meta-theory of abelian groups).
[6] A. Baudisch, D.G. Seese, P. Tuschik, M. Weese, Decidability and Generalized Quantifiers, Akademie-Verlag, Berlin, 1980, xii+235pp.; A. Baudisch, D.G. Seese, P. Tuschik, M. Weese, Decidability and Generalized Quantifiers, Akademie-Verlag, Berlin, 1980, xii+235pp. · Zbl 0442.03011
[7] Baudisch, A.; Seese, D. G.; Tuschik, P.; Weese, M., Decidability and quantifier-elimination, (Barwise, J.; Feferman, S., Model-Theoretic Logics (1985), Springer: Springer New York), 235-268, (Chapter VII)
[8] A. Blumensath, Axiomatising tree-interpretable structures, Technical Report AIB-2001-10, RWTH Aachen, 2001, pp. 1-23, \(\&\#60;\) http://www-mgi.informatik.rwth-aachen.de/\( \sim;>\); A. Blumensath, Axiomatising tree-interpretable structures, Technical Report AIB-2001-10, RWTH Aachen, 2001, pp. 1-23, \(\&\#60;\) http://www-mgi.informatik.rwth-aachen.de/\( \sim;>\) · Zbl 1054.03025
[9] A. Blumensath, A model theoretic characterization of clique width, RWTH Aachen, 2002, preprint, \(\&\#60;\) http://www-mgi.informatik.rwth-aachen.de/\( \sim;>\); A. Blumensath, A model theoretic characterization of clique width, RWTH Aachen, 2002, preprint, \(\&\#60;\) http://www-mgi.informatik.rwth-aachen.de/\( \sim;>\)
[10] A. Blumensath, Axiomatising tree-interpretable structures, in: Proc. 19th Internat. Symp. Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 2285, Springer, Berlin, 2002, pp. 596-607.; A. Blumensath, Axiomatising tree-interpretable structures, in: Proc. 19th Internat. Symp. Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 2285, Springer, Berlin, 2002, pp. 596-607. · Zbl 1054.03025
[11] Bodlaender, H. L., A linear time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25, 1305-1317 (1996) · Zbl 0864.68074
[12] Börger, E.; Grädel, E.; Gurevich, Y., The Classical Decision Problem (1997), Springer: Springer Berlin · Zbl 0865.03004
[13] Büchi, J. R., Weak second-order arithmetic and finite automata, Z. Math. Logik Grundlag. Math., 6, 66-92 (1960) · Zbl 0103.24705
[14] J.R. Büchi, The monadic second order theory of \(\operatorname{\Omega;}_1\); J.R. Büchi, The monadic second order theory of \(\operatorname{\Omega;}_1\)
[15] J.R. Büchi, D. Siefkes, Axiomatization of the monadic second order theory of \(\operatorname{\Omega;}_1\); J.R. Büchi, D. Siefkes, Axiomatization of the monadic second order theory of \(\operatorname{\Omega;}_1\)
[16] B. Courcelle, The decidability of the monadic second order theory of certain sets of finite and infinite graphs, LICS’88, Logic in Computer Science, Edinburgh, 1988.; B. Courcelle, The decidability of the monadic second order theory of certain sets of finite and infinite graphs, LICS’88, Logic in Computer Science, Edinburgh, 1988.
[17] B. Courcelle, The monadic second order theory of graphs III: Tree decompositions, minors, and complexity issues, Inform. and Comput. 85 (1990) 12-75 (Theoret. Inform. Appl. 26(2) (1992) 257-286).; B. Courcelle, The monadic second order theory of graphs III: Tree decompositions, minors, and complexity issues, Inform. and Comput. 85 (1990) 12-75 (Theoret. Inform. Appl. 26(2) (1992) 257-286). · Zbl 0722.03008
[18] B. Courcelle, The monadic second order logic of graphs VI: On several representations of graphs by relational structures, Discrete Appl. Math. 54 (1994) 117-149, Erratum 63 (1995) 199-200.; B. Courcelle, The monadic second order logic of graphs VI: On several representations of graphs by relational structures, Discrete Appl. Math. 54 (1994) 117-149, Erratum 63 (1995) 199-200. · Zbl 0809.03005
[19] B. Courcelle, Monadic second order definable graph transductions: a survey, Theoret. Comput. Sci. 126(1) (1994) 53-75, Seventh Colloq. Trees in Algebra and Programming (CAAP’92) and European Symp. Programming (ESOP), Rrennes, 1992.; B. Courcelle, Monadic second order definable graph transductions: a survey, Theoret. Comput. Sci. 126(1) (1994) 53-75, Seventh Colloq. Trees in Algebra and Programming (CAAP’92) and European Symp. Programming (ESOP), Rrennes, 1992. · Zbl 0805.68077
[20] Courcelle, B., Structural properties of context-free sets of graphs generated by vertex replacement, Inform. and Comput., 116, 275-293 (1995) · Zbl 0828.68091
[21] Courcelle, B., The monadic second order theory of graphs X: Linear orderings, Theoret. Comput. Sci., 160, 87-144 (1996) · Zbl 0877.68087
[22] Courcelle, B., The expression of graph properties and graph transformations in monadic second-order logic, (Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 1 (1997), World Scientific: World Scientific River Edge, NJ), 313-400
[23] Courcelle, B., The monadic second-order logic of graphs XII: Planar graphs and planar maps, Theoret. Comput. Sci., 237, 1-32 (2000) · Zbl 0951.03004
[24] B. Courcelle, Clique-width of countable graphs: a compactness property, Internat. Conf. Graph Theory, Marseille, 2000 (available from \(\&\#60;\) http://dept-info.labri.u-bordeaux.fr/\( \sim;>\); B. Courcelle, Clique-width of countable graphs: a compactness property, Internat. Conf. Graph Theory, Marseille, 2000 (available from \(\&\#60;\) http://dept-info.labri.u-bordeaux.fr/\( \sim;>\)
[25] Courcelle, B., The monadic second-order logic of graphs XIV: Uniformly sparse graphs and edge set quantification, Theoret. Comput. Sci., 299, 1-36 (2003) · Zbl 1038.68048
[26] B. Courcelle, The monadic second-order logic of graphs XV: On a conjecture by D. Seese, manuscript, LaBri, Bordeaux 1 University, March 8, 2004, pp. 1-40.; B. Courcelle, The monadic second-order logic of graphs XV: On a conjecture by D. Seese, manuscript, LaBri, Bordeaux 1 University, March 8, 2004, pp. 1-40.
[27] Courcelle, B.; Engelfriet, J., A logical characterization of the sets of hypergraphs defined by hyperedge replacement grammars, Math. Systems Theory, 28, 6, 515-552 (1995) · Zbl 0830.68098
[28] Courcelle, B.; Engelfriet, J.; Rozenberg, G., Handle-rewriting hypergraph grammars, J. Comput. System Sci., 46, 218-270 (1993) · Zbl 0825.68446
[29] Courcelle, B.; Makowsky, J. A.; Rotics, U., Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Systems, 33, 125-150 (2000) · Zbl 1009.68102
[30] Courcelle, B.; Mosbah, M., Monadic second-order evaluations on tree-decomposable graphs, Theoret. Comput. Sci., 109, 49-82 (1993) · Zbl 0789.68083
[31] Courcelle, B.; Olariu, M., Upper bounds to the clique-width of graphs, Discrete Appl. Math., 101, 77-114 (2000) · Zbl 0958.05105
[32] B. Courcelle, S.-I. Oum, Vertex-minors, monadic second-order logic, and a conjecture by Seese, July 23, 2004, pp. 37, preprint.; B. Courcelle, S.-I. Oum, Vertex-minors, monadic second-order logic, and a conjecture by Seese, July 23, 2004, pp. 37, preprint. · Zbl 1121.03016
[33] Drake, F., Set Theory, an Introduction to Large Cardinals (1974), North-Holland: North-Holland Amsterdam · Zbl 0294.02034
[34] Ebbinghaus, H.-D.; Flum, J., Finite Model Theory (1995), Springer: Springer Berlin
[35] Ebbinghaus, H.-D.; Flum, J.; Thomas, W., Mathematical Logic (1994), Springer: Springer Berlin · Zbl 0795.03001
[36] Feferman, S.; Vaught, R. L., The first-order properties of algebraic systems, Fund. Math., 47, 57-103 (1959) · Zbl 0088.24803
[37] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), Bell Telephone Laboratories · Zbl 0411.68039
[38] 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
[39] Geelen, J. F.; Gerards, A. H.M.; Robertson, N.; Whittle, G. P., On the excluded minors for the matroids of branch-width \(k\), J. Combin. Theory Ser. B, 88, 261-265 (2003) · Zbl 1032.05027
[40] Geelen, J. F.; Gerards, A. H.M.; Whittle, G. P., Branch-width and well-quasi-ordering in matroids and graphs, J. Combin. Theory Ser. B, 84, 270-290 (2002) · Zbl 1037.05013
[41] J.F. Geelen, A.H.M. Gerards, G.P. Whittle, Excluding a planar graph from a \(GF (q)\); J.F. Geelen, A.H.M. Gerards, G.P. Whittle, Excluding a planar graph from a \(GF (q)\) · Zbl 1125.05025
[42] Gurevich, Y., Monadic theory of order and topology, I, Israel J. Math., 27, 299-319 (1977) · Zbl 0359.02061
[43] Gurevich, Y., Monadic theory of order and topology, II, Israel J. Math., 34, 45-71 (1979) · Zbl 0428.03034
[44] Gurevich, Y., Monadic second-order theories, (Barwise, J.; Feferman, S., Model-Theoretic Logics (1985), Springer: Springer New York), 479-506, (Chapter XIII)
[45] Gurevich, Y.; Magidor, M.; Shelah, S., The monadic theory of \(\omega_2\), J. Symbolic Logic, 48, 387-398 (1983) · Zbl 0549.03010
[46] Gurevich, Y.; Shelah, S., Monadic theory of order and topology in ZFC, Ann. Math. Logic, 23, 179-182 (1982) · Zbl 0516.03007
[47] Gurevich, Y.; Shelah, S., The monadic theory of the “next world”, Israel J. Math., 49, 55-68 (1984) · Zbl 0575.03028
[48] Gurevich, Y.; Shelah, S., On the strength of the interpretation method, J. Symbolic Logic, 54, 305-323 (1989) · Zbl 0699.03031
[49] H. Hauschild, H. Herre, W. Rautenberg, Entscheidbarkeit der monadischen Theorie 2. Stufe der \(nn\); H. Hauschild, H. Herre, W. Rautenberg, Entscheidbarkeit der monadischen Theorie 2. Stufe der \(nn\) · Zbl 0264.02046
[50] Hauschild, H.; Rautenberg, W., Interpretierbarkeit in der Gruppentheorie (translation: Interpretability in the theory of groups), Algebra Universalis, 1, 2, 136-151 (1971) · Zbl 0215.04801
[51] H. Herre, Unentscheidbarkeit in der Graphentheorie (translated: Undecidability in graph theory), in: Bulletin de L’Academie Polonaise des Sciences, Serie des Sciences Mathematiques, Astronomiques et Physiques, Vol. XXI(3), 1973, pp. 201-208.; H. Herre, Unentscheidbarkeit in der Graphentheorie (translated: Undecidability in graph theory), in: Bulletin de L’Academie Polonaise des Sciences, Serie des Sciences Mathematiques, Astronomiques et Physiques, Vol. XXI(3), 1973, pp. 201-208. · Zbl 0279.05101
[52] P. Hliněný, Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids, J. Comb. Theory B, 2005, to appear.; P. Hliněný, Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids, J. Comb. Theory B, 2005, to appear.
[53] P. Hliněný, On some hard problems on matroid spikes, Theor. Comput. Syst., 2005, accepted.; P. Hliněný, On some hard problems on matroid spikes, Theor. Comput. Syst., 2005, accepted.
[54] P. Hliněný, A parametrized algorithm for matroid branch-width, SIAM J. Comput. 35 (2005) 259-277 (electronic).; P. Hliněný, A parametrized algorithm for matroid branch-width, SIAM J. Comput. 35 (2005) 259-277 (electronic). · Zbl 1088.05023
[55] P. Hliněný, On matroid properties definable in the MSO logic, in: Math Foundations of Computer Science MFCS 2003, Lecture Notes in Computer Science, Vol. 2747, Springer, Berlin, 2003, pp. 470-479.; P. Hliněný, On matroid properties definable in the MSO logic, in: Math Foundations of Computer Science MFCS 2003, Lecture Notes in Computer Science, Vol. 2747, Springer, Berlin, 2003, pp. 470-479.
[56] P. Hliněný, On hardness of the matroid minor problem, 2005, submitted.; P. Hliněný, On hardness of the matroid minor problem, 2005, submitted.
[57] P. Hliněný, D. Seese, Decidability of MSO theories of representable matroids, in: R. Downey, M. Fellows, F. Dehne (Eds.), Parameterized and Exact Computation, Proc. First Internat. Workshop on Parameterized and Exact Computation, IWPEC 2004, Bergen, Norway, September 14-17, 2004, Lecture Notes in Computer Science, Vol. 3162, Springer, Berlin, 2004, pp. 96-107.; P. Hliněný, D. Seese, Decidability of MSO theories of representable matroids, in: R. Downey, M. Fellows, F. Dehne (Eds.), Parameterized and Exact Computation, Proc. First Internat. Workshop on Parameterized and Exact Computation, IWPEC 2004, Bergen, Norway, September 14-17, 2004, Lecture Notes in Computer Science, Vol. 3162, Springer, Berlin, 2004, pp. 96-107. · Zbl 1104.03007
[58] P. Hliněný, D. Seese, Interpretability and decidability for monadic theories of graphs and matroids, 2005, in preparation.; P. Hliněný, D. Seese, Interpretability and decidability for monadic theories of graphs and matroids, 2005, in preparation.
[59] P. Hliněný, G.P. Whittle, Matroid Tree-Width, 2003, submitted for publication (extended abstract in: Eurocomb’03, ITI Series, Vol. 2003-145, Charles University, Prague, Czech Republic, pp. 202-205).; P. Hliněný, G.P. Whittle, Matroid Tree-Width, 2003, submitted for publication (extended abstract in: Eurocomb’03, ITI Series, Vol. 2003-145, Charles University, Prague, Czech Republic, pp. 202-205).
[60] K. Kunen, Combinatorics, in: J. Barwise (Ed.), Handbook of Mathematical Logic, North-Holland, Amsterdam, 1977, pp. 371-401 (Chapter B.3).; K. Kunen, Combinatorics, in: J. Barwise (Ed.), Handbook of Mathematical Logic, North-Holland, Amsterdam, 1977, pp. 371-401 (Chapter B.3).
[61] P. Lapoire, Recognizability equals monadic second-order definability for sets of graphs of bounded tree-width, in: M. Morvan, Ch. Meinel, Da. Krob (Eds.), Proc. 15th Annual Symp. Theoretical Aspects of Computer Science Paris, France, February 1998, STACS, 1998, Springer Lecture Notes in Computer Science, Springer, Berlin, Vol. 1373, pp. 618-628.; P. Lapoire, Recognizability equals monadic second-order definability for sets of graphs of bounded tree-width, in: M. Morvan, Ch. Meinel, Da. Krob (Eds.), Proc. 15th Annual Symp. Theoretical Aspects of Computer Science Paris, France, February 1998, STACS, 1998, Springer Lecture Notes in Computer Science, Springer, Berlin, Vol. 1373, pp. 618-628. · Zbl 0936.03036
[62] Makowsky, J. A., Algorithmic uses of the Feferman-Vaught theorem, Ann. Pure Appl. Logic, 126, 159-213 (2004) · Zbl 1099.03009
[63] S.-I. Oum, Rank-width and well-quasi-ordering, manuscript, 2004.; S.-I. Oum, Rank-width and well-quasi-ordering, manuscript, 2004.
[64] S.-I. Oum, Approximating rank-width and clique-width quickly, manuscript, 2005.; S.-I. Oum, Approximating rank-width and clique-width quickly, manuscript, 2005. · Zbl 1126.05304
[65] S.-I. Oum, P. Seymour, Approximation algorithm to the clique-width of a graph, manuscript, 2003.; S.-I. Oum, P. Seymour, Approximation algorithm to the clique-width of a graph, manuscript, 2003.
[66] Oxley, J. G., Matroid Theory (1992), Oxford University Press: Oxford University Press Oxford · Zbl 0784.05002
[67] Rabin, M. O., A simple method for undecidability proofs and some applications, (Bar-Hillel, Logic, Methodology and Philosophy of Sciences, Vol. 1 (1964), North-Holland: North-Holland Amsterdam), 58-68 · Zbl 0192.05502
[68] Rabin, M. O., Decidability of second order theories and automata on infinite trees, Trans. Amer. Math. Soc., 141, 1-35 (1969) · Zbl 0221.02031
[69] Rabin, M. O., Decidable theories, (Barwise, J., Handbook of Mathematical Logic (1977), North-Holland: North-Holland Amsterdam), 595-629, (Chapter C.3)
[70] W. Rautenberg, Lectures on decidability theory, Logical Semester Warsaw 1973, Lecture I-VII, Banach Center Warsaw, Warsaw, 1973, p. 67.; W. Rautenberg, Lectures on decidability theory, Logical Semester Warsaw 1973, Lecture I-VII, Banach Center Warsaw, Warsaw, 1973, p. 67.
[71] N. Robertson, P.D. Seymour, Graph minors—a survey, Surveys in Combinatorics, Cambridge University Press, Cambridge, 1985, pp. 153-171.; N. Robertson, P.D. Seymour, Graph minors—a survey, Surveys in Combinatorics, Cambridge University Press, Cambridge, 1985, pp. 153-171. · Zbl 0568.05025
[72] Robertson, N.; Seymour, P. D., Graph minors X. Obstructions to tree-decomposition, J. Combin. Theory Ser. B, 52, 153-190 (1991) · Zbl 0764.05069
[73] N. Robertson, P.D. Seymour, Graph minors XX. Wagner’s conjecture, J. Comb. Theory B 92(2) (2004) 325-357.; N. Robertson, P.D. Seymour, Graph minors XX. Wagner’s conjecture, J. Comb. Theory B 92(2) (2004) 325-357. · Zbl 1061.05088
[74] D. Seese, Entscheidbarkeitsfragen der Theorien 2. Stufe einiger “netzartiger” Graphen (translation: Questions of decidability of second order theories of some “netlike” graphs), Diploma Thesis, Humboldt-University, 1972, p. 45.; D. Seese, Entscheidbarkeitsfragen der Theorien 2. Stufe einiger “netzartiger” Graphen (translation: Questions of decidability of second order theories of some “netlike” graphs), Diploma Thesis, Humboldt-University, 1972, p. 45.
[75] D. Seese, Entscheidbarkeits- und Definierbarkeitsfragen der Theorie “netzartiger” Graphen—I (translation: Questions of decidability and definability of the theory of “netlike” graphs—I), Wiss. Z. Humboldt-Univ. Math.-Natur. Reihe XXI (1972) 513-517.; D. Seese, Entscheidbarkeits- und Definierbarkeitsfragen der Theorie “netzartiger” Graphen—I (translation: Questions of decidability and definability of the theory of “netlike” graphs—I), Wiss. Z. Humboldt-Univ. Math.-Natur. Reihe XXI (1972) 513-517. · Zbl 0254.02036
[76] D. Seese, Zur Entscheidbarkeit der monadischen Theorie 2. Stufe baumartiger Graphen (translation: To the decidability of the monadic second order theory of graphs with a similarity to trees), Wiss. Z. Humboldt-Univ. Berlin Math.-Natur. Reihe. XXIV (6) (1975) 768-772.; D. Seese, Zur Entscheidbarkeit der monadischen Theorie 2. Stufe baumartiger Graphen (translation: To the decidability of the monadic second order theory of graphs with a similarity to trees), Wiss. Z. Humboldt-Univ. Berlin Math.-Natur. Reihe. XXIV (6) (1975) 768-772. · Zbl 0362.02037
[77] D. Seese, Ein Unentscheidbarkeitskriterium (translation: A criterion of undecidability), Wiss. Z. Humboldt-Univ. Berlin Math.-Natur. Reihe XXIV (6) (1975) 772-780.; D. Seese, Ein Unentscheidbarkeitskriterium (translation: A criterion of undecidability), Wiss. Z. Humboldt-Univ. Berlin Math.-Natur. Reihe XXIV (6) (1975) 772-780. · Zbl 0331.02026
[78] D. Seese, Entscheidbarkeits- und Interpretierbarkeitsfragen monadischer Theorien zweiter Stufe gewisser Klassen von Graphen (translation to English: Questions of decidability and interpretability of monadic second order theories of certain classes of graphs), Dissertation, Humboldt-Universität zu Berlin, 1976, pp. iv+172.; D. Seese, Entscheidbarkeits- und Interpretierbarkeitsfragen monadischer Theorien zweiter Stufe gewisser Klassen von Graphen (translation to English: Questions of decidability and interpretability of monadic second order theories of certain classes of graphs), Dissertation, Humboldt-Universität zu Berlin, 1976, pp. iv+172.
[79] D. Seese, Decidability of \(\operatorname{\Omega;} \); D. Seese, Decidability of \(\operatorname{\Omega;} \) · Zbl 0375.02042
[80] D. Seese, Decidability of \(\operatorname{\Omega;} \); D. Seese, Decidability of \(\operatorname{\Omega;} \) · Zbl 0386.03004
[81] D. Seese, Ordered tree representations of infinite graphs, Akademie der Wissenschaften der DDR, Karl-Weierstrass-Institut fuer Mathematik, P-MATH-12/88, Berlin, 1988, pp. 1-50, preprint.; D. Seese, Ordered tree representations of infinite graphs, Akademie der Wissenschaften der DDR, Karl-Weierstrass-Institut fuer Mathematik, P-MATH-12/88, Berlin, 1988, pp. 1-50, preprint.
[82] Seese, D., The structure of the models of decidable monadic theories of graphs, Ann. Pure Appl. Logic, 53, 169-195 (1991) · Zbl 0733.03026
[83] Seese, D., Interpretability and tree automata: a simple way to solve algorithmic problems on graphs closely related to trees, (Nivat, M.; Podelski, A., Tree Automata and Languages (1992), Elsevier: Elsevier Amsterdam), 83-114 · Zbl 0798.68059
[84] Seymour, P. D., Recognizing graphic matroids, Combinatorica, 1, 75-78 (1981) · Zbl 0501.05022
[85] Shelah, S., The monadic theory of order, Ann. of Math., 102, 379-419 (1975) · Zbl 0345.02034
[86] Shelah, S., Notes on monadic logic, part B: Complexity of linear orders, Israel J. Math., 69, 99-116 (1990) · Zbl 0698.03034
[87] H. Wang, Proving theorems by pattern recognition II, Bell System Technical J. 40 (1961) 1-41.; H. Wang, Proving theorems by pattern recognition II, Bell System Technical J. 40 (1961) 1-41.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.