{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:05:58Z","timestamp":1762322758000},"reference-count":76,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1991,7,1]],"date-time":"1991-07-01T00:00:00Z","timestamp":678326400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":8052,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Annals of Pure and Applied Logic"],"published-print":{"date-parts":[[1991,7]]},"DOI":"10.1016\/0168-0072(91)90054-p","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T03:38:59Z","timestamp":1027654739000},"page":"169-195","source":"Crossref","is-referenced-by-count":86,"title":["The structure of the models of decidable monadic theories of graphs"],"prefix":"10.1016","volume":"53","author":[{"given":"D.","family":"Seese","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0168-0072(91)90054-P_BIB1","first-page":"38","article-title":"Problems easy for tree-decomposable graphs, extended abstract","volume":"317","author":"Arnborg","year":"1988"},{"key":"10.1016\/0168-0072(91)90054-P_BIB2","author":"Baudisch","year":"1980"},{"key":"10.1016\/0168-0072(91)90054-P_BIB3","first-page":"72","volume":"66","author":"Berger","year":"1966","journal-title":"The undecidability of the domino problem Mem. Amer. Math. Soc."},{"key":"10.1016\/0168-0072(91)90054-P_BIB4","author":"Bollob\u00e1s","year":"1978"},{"key":"10.1016\/0168-0072(91)90054-P_BIB5","first-page":"333","article-title":"Spectral problem and completeness of logical decision problems","volume":"171","author":"B\u00f6rger","year":"1983"},{"key":"10.1016\/0168-0072(91)90054-P_BIB6","first-page":"367","article-title":"Using determinacy of games to eliminate quantifiers","volume":"56","author":"B\u00fcchi","year":"1977"},{"key":"10.1016\/0168-0072(91)90054-P_BIB7","article-title":"The monadic second order theory of all countable ordinals","volume":"328","author":"B\u00fcchi","year":"1973"},{"key":"10.1016\/0168-0072(91)90054-P_BIB8","article-title":"Recognizability and second-order definability for sets of finite graphs","author":"Courcelle","year":"1987"},{"key":"10.1016\/0168-0072(91)90054-P_BIB9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2355-7","article-title":"Mathematical Logic","author":"Ebbinghaus","year":"1984"},{"key":"10.1016\/0168-0072(91)90054-P_BIB10","article-title":"Dominoes are forever","author":"Emde Boas","year":"1983"},{"key":"10.1016\/0168-0072(91)90054-P_BIB11","article-title":"Bounded tilings, an alternative to satisfiability?","author":"Emde Boas","year":"1984"},{"key":"10.1016\/0168-0072(91)90054-P_BIB12","first-page":"27","article-title":"Generalized first-order spectra and polynomial-time recognizable sets","volume":"7","author":"Fagin","year":"1974"},{"key":"10.1016\/0168-0072(91)90054-P_BIB13","first-page":"229","article-title":"The metamathematics of the graph minor theorem","volume":"65","author":"Friedman","year":"1987"},{"key":"10.1016\/0168-0072(91)90054-P_BIB14","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1090\/S0002-9939-1974-0325378-3","article-title":"The undecidability of theories of groupoids with an extra predicate","volume":"42","author":"Garfunkel","year":"1974","journal-title":"Proc. Amer. Math. Soc."},{"key":"10.1016\/0168-0072(91)90054-P_BIB15","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/BF02756489","article-title":"Monadic theory of order and topology I","volume":"27","author":"Gurevich","year":"1977","journal-title":"Israel J. Math."},{"key":"10.1016\/0168-0072(91)90054-P_BIB16","doi-asserted-by":"crossref","first-page":"481","DOI":"10.2307\/2273287","article-title":"Modest theory of short chains I","volume":"44","author":"Gurevich","year":"1979","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/0168-0072(91)90054-P_BIB17","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/BF02761824","article-title":"Monadic theory of order and topology II","volume":"34","author":"Gurevich","year":"1979","journal-title":"Israel J. Math."},{"key":"10.1016\/0168-0072(91)90054-P_BIB18","first-page":"479","article-title":"Monadic second-order theories","author":"Gurevich","year":"1985"},{"key":"10.1016\/0168-0072(91)90054-P_BIB19","first-page":"60","article-title":"Trees, automata, and games","author":"Gurevich","year":"1982","journal-title":"Proc. ACM STOC"},{"key":"10.1016\/0168-0072(91)90054-P_BIB20","doi-asserted-by":"crossref","first-page":"387","DOI":"10.2307\/2273556","article-title":"The monadic theory of \\Gw2","volume":"48","author":"Gurevich","year":"1983","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/0168-0072(91)90054-P_BIB21","doi-asserted-by":"crossref","first-page":"491","DOI":"10.2307\/2273288","article-title":"Modest theory of short chains II","volume":"44","author":"Gurevich","year":"1979","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/0168-0072(91)90054-P_BIB22","first-page":"30","article-title":"The monadic theory and the lsquonext worldrsquo","author":"Gurevich","year":"1981"},{"key":"10.1016\/0168-0072(91)90054-P_BIB23","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0003-4843(82)90004-3","article-title":"Monadic theory of order and topology in ZFC","volume":"23","author":"Gurevich","year":"1982","journal-title":"Ann. Math. Logic"},{"key":"10.1016\/0168-0072(91)90054-P_BIB24","doi-asserted-by":"crossref","first-page":"816","DOI":"10.2307\/2273475","article-title":"Interpreting second-order logic in the monadic theory of order","volume":"48","author":"Gurevich","year":"1983","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/0168-0072(91)90054-P_BIB25","author":"Gurevich","year":"1986","journal-title":"On the strength of the interpretation method"},{"key":"10.1016\/0168-0072(91)90054-P_BIB26","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1002\/mana.19670330108","article-title":"Zerlegungssatz f\u00fcr unendliche Graphen und seine Anwendung auf Homomorphismen","volume":"33","author":"Halin","year":"1967","journal-title":"Math. Nachr."},{"key":"10.1016\/0168-0072(91)90054-P_BIB27","author":"Harary","year":"1969"},{"key":"10.1016\/0168-0072(91)90054-P_BIB28","article-title":"A simple highly undecidable domino problem (or, a lemma on infinite trees, with applications)","author":"Harel","year":"1983"},{"key":"10.1016\/0168-0072(91)90054-P_BIB29","article-title":"A general result on infinite trees and its applications","author":"Harel","year":"1984","journal-title":"Proc. ACM Symp. Theory of Computation"},{"key":"10.1016\/0168-0072(91)90054-P_BIB30","first-page":"347","article-title":"Languages which capture complexity classes","author":"Immerman","year":"1983","journal-title":"Proc. 15th Annual ACM Symp. on the Theory of Computing"},{"key":"10.1016\/0168-0072(91)90054-P_BIB31","article-title":"The NP-completeness column: an ongoing guide","volume":"6","author":"Johnson","year":"1987","journal-title":"J. Algorithms"},{"key":"10.1016\/0168-0072(91)90054-P_BIB32","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF02276797","article-title":"Model-Interpretability into trees and applications","volume":"17","author":"Korec","year":"1976","journal-title":"Arch. Math. Logik"},{"key":"10.1016\/0168-0072(91)90054-P_BIB33","author":"Kuratowski","year":"1976"},{"key":"10.1016\/0168-0072(91)90054-P_BIB34","author":"Monk","year":"1982","journal-title":"Decidability of the monadic second-order theory of two successors"},{"key":"10.1016\/0168-0072(91)90054-P_BIB35","first-page":"46","article-title":"Pushdown automata, graph ends, second-order logic, and reachability problems","author":"Muller","year":"1981","journal-title":"Proc. STOC"},{"key":"10.1016\/0168-0072(91)90054-P_BIB36","first-page":"58","article-title":"A simple method for undecidability proofs and some applications","author":"Rabin","year":"1965"},{"key":"10.1016\/0168-0072(91)90054-P_BIB37","first-page":"595","article-title":"Decidable theories","author":"Rabin","year":"1977"},{"key":"10.1016\/0168-0072(91)90054-P_BIB38","first-page":"1","article-title":"Decidability of second order theories and automata on infinite trees","volume":"141","author":"Rabin","year":"1969","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/0168-0072(91)90054-P_BIB39","article-title":"Graphs minors\u2014a survey, Surveys in Combinatorics 1985","volume":"103","author":"Robertson","year":"1985","journal-title":"London Math. Soc. Lecture Notes"},{"key":"10.1016\/0168-0072(91)90054-P_BIB40","first-page":"39","article-title":"Graph minors","volume":"35","author":"Robertson","year":"1983","journal-title":"Part 1: Excluding a forest, J. Combin. Theory, Ser. B"},{"key":"10.1016\/0168-0072(91)90054-P_BIB41","first-page":"309","article-title":"Graph minors","volume":"7","author":"Robertson","year":"1986","journal-title":"Part 2: Algorithmic aspects of tree-width, J. Algorithms"},{"key":"10.1016\/0168-0072(91)90054-P_BIB42","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","article-title":"Graph minors","volume":"36","author":"Robertson","year":"1984","journal-title":"Part 3: Planar tree-width, J. Combin. Theory, Ser. B"},{"key":"10.1016\/0168-0072(91)90054-P_BIB43","article-title":"Graph minors","author":"Robertson","year":"1985","journal-title":"Part 4: Tree-width and well-quasi-ordering"},{"key":"10.1016\/0168-0072(91)90054-P_BIB44","first-page":"92","article-title":"Graph minors","volume":"41","author":"Robertson","year":"1986","journal-title":"Part 5: Excluding a planar graph"},{"key":"10.1016\/0168-0072(91)90054-P_BIB45","first-page":"115","article-title":"Graph minors","volume":"41","author":"Robertson","year":"1986","journal-title":"Part 6: Disjoint paths across a disc"},{"key":"10.1016\/0168-0072(91)90054-P_BIB46","article-title":"Graph minors","author":"Robertson","year":"1985","journal-title":"Part 7: Disjoint paths on a surface"},{"key":"10.1016\/0168-0072(91)90054-P_BIB47","article-title":"Graph minors","author":"Robertson","year":"1985","journal-title":"Part 8: A Kuratowski theorem for general surfaces"},{"key":"10.1016\/0168-0072(91)90054-P_BIB48","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/0606030","article-title":"Disjoint paths: a survey","volume":"6","author":"Robertson","year":"1985","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"10.1016\/0168-0072(91)90054-P_BIB49","first-page":"399","article-title":"Graph width and well-ordering: a survey","author":"Robertson","year":"1984"},{"key":"10.1016\/0168-0072(91)90054-P_BIB50","article-title":"What graphs have bounded tree-width?","author":"Scheffler","year":"1988","journal-title":"Proc. 7th Fischland-Colloquium on Discrete Mathematics and Applications"},{"key":"10.1016\/0168-0072(91)90054-P_BIB51","article-title":"Die Baumweite von Graphen als ein Mass f\u00fcr die Kompliziertheit algorithmischer Probleme","author":"Scheffler","year":"1989","journal-title":"Dissertation A, Akademie der Wissenschaften der DDR"},{"key":"10.1016\/0168-0072(91)90054-P_BIB52","article-title":"A combinatorial and logical approach to linear-time computability","author":"Scheffler","year":"1988"},{"issue":"3","key":"10.1016\/0168-0072(91)90054-P_BIB53","doi-asserted-by":"crossref","first-page":"585","DOI":"10.2307\/2273425","article-title":"Decidability and \u21350-categoricity of theories of partially ordered sets","volume":"45","author":"Schmerl","year":"1980","journal-title":"J. Symbolic Logic"},{"issue":"1","key":"10.1016\/0168-0072(91)90054-P_BIB54","doi-asserted-by":"crossref","first-page":"101","DOI":"10.2307\/2273263","article-title":"Decidability and finite axiomatizability of theories of \u21350-categorical partially ordered sets","volume":"46","author":"Schmerl","year":"1981","journal-title":"J. Symbolic Logic"},{"issue":"2","key":"10.1016\/0168-0072(91)90054-P_BIB55","first-page":"629","article-title":"Arborescent structures, II: Interpretability in the theory of trees","volume":"266","author":"Schmerl","year":"1981","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/0168-0072(91)90054-P_BIB56","first-page":"772","article-title":"Ein Unentscheidbarkeitskriterium","volume":"24","author":"Seese","year":"1975"},{"key":"10.1016\/0168-0072(91)90054-P_BIB57","first-page":"768","article-title":"Zur Entscheidbarkeit der Monadischen Theorie zweiter Stufe baumartiger Graphen","volume":"24","author":"Seese","year":"1975"},{"key":"10.1016\/0168-0072(91)90054-P_BIB58","first-page":"513","article-title":"Entscheidbarkeits- und Definierbarkeitsfragen der Theorie \u2018netzartiger\u2019 Graphen","volume":"21","author":"Seese","year":"1972"},{"key":"10.1016\/0168-0072(91)90054-P_BIB59","article-title":"Entscheidbarkeits- und Interpretierbarkeitsfragen monadischer Theorien zweiter Stufe gewisser Klassen von Graphen","author":"Seese","year":"1976"},{"key":"10.1016\/0168-0072(91)90054-P_BIB60","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1002\/mana.19790870103","article-title":"Some graph theoretical operations and decidability","volume":"87","author":"Seese","year":"1979","journal-title":"Math. Nachr."},{"key":"10.1016\/0168-0072(91)90054-P_BIB61","first-page":"412","article-title":"Tree-partite graphs and the complexity of algorithms","author":"Seese","year":"1985"},{"key":"10.1016\/0168-0072(91)90054-P_BIB62","article-title":"Tree-partite graphs and the complexity of algorithms","author":"Seese","year":"1986","journal-title":"Preprint P-MATH-08\/86"},{"key":"10.1016\/0168-0072(91)90054-P_BIB63","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1002\/malq.19780240109","article-title":"\u00dcber unentscheidbare Erweiterungen von SC","volume":"24","author":"Seese","year":"1978","journal-title":"Z. Math. Logik Grundlag. Math."},{"key":"10.1016\/0168-0072(91)90054-P_BIB64","article-title":"Ordered tree-representations of infinite graphs","author":"Seese","year":"1988","journal-title":"Preprint P-MATH-12\/88"},{"key":"10.1016\/0168-0072(91)90054-P_BIB65","article-title":"Grids and their minors","author":"Seese","year":"1986","journal-title":"Preprint P-MATH-41\/86"},{"key":"10.1016\/0168-0072(91)90054-P_BIB66","doi-asserted-by":"crossref","first-page":"379","DOI":"10.2307\/1971037","article-title":"The monadic theory of order","volume":"102","author":"Shelah","year":"1975","journal-title":"Ann. of Math."},{"key":"10.1016\/0168-0072(91)90054-P_BIB67","author":"Shoenfield","year":"1967"},{"key":"10.1016\/0168-0072(91)90054-P_BIB68","article-title":"B\u00fcchi's monadic second order successor arithmetic","volume":"120","author":"Siefkes","year":"1970"},{"key":"10.1016\/0168-0072(91)90054-P_BIB69","author":"Stupp","year":"1975"},{"key":"10.1016\/0168-0072(91)90054-P_BIB70","volume":"IX","author":"Thomas","year":"1985","journal-title":"Letter 11"},{"key":"10.1016\/0168-0072(91)90054-P_BIB71","volume":"I","author":"Thomas","year":"1986","journal-title":"Letter 09"},{"key":"10.1016\/0168-0072(91)90054-P_BIB72","first-page":"129","article-title":"Infinite graphs","author":"Thomassen","year":"1983"},{"key":"10.1016\/0168-0072(91)90054-P_BIB73","author":"Thomassen","year":"1985","journal-title":"Configurations in graphs of large minimum degree, connectivity or chromatic number"},{"key":"10.1016\/0168-0072(91)90054-P_BIB74","article-title":"Decision problems related to the concept of operation","author":"LeTourneau","year":"1968","journal-title":"Ph. D. Thesis"},{"key":"10.1016\/0168-0072(91)90054-P_BIB75","author":"Tutte","year":"1984"},{"key":"10.1016\/0168-0072(91)90054-P_BIB76","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/j.1538-7305.1961.tb03975.x","article-title":"Proving theorems by pattern recognition II","volume":"40","author":"Wang","year":"1961","journal-title":"Bell Syst. Tech. J."}],"container-title":["Annals of Pure and Applied Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:016800729190054P?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:016800729190054P?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,13]],"date-time":"2019-04-13T07:53:03Z","timestamp":1555141983000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/016800729190054P"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,7]]},"references-count":76,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,7]]}},"alternative-id":["016800729190054P"],"URL":"https:\/\/doi.org\/10.1016\/0168-0072(91)90054-p","relation":{},"ISSN":["0168-0072"],"issn-type":[{"value":"0168-0072","type":"print"}],"subject":[],"published":{"date-parts":[[1991,7]]}}}