{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:37:59Z","timestamp":1725471479195},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540659228"},{"type":"electronic","value":"9783540488552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/10703163_9","type":"book-chapter","created":{"date-parts":[[2006,10,9]],"date-time":"2006-10-09T18:15:50Z","timestamp":1160417750000},"page":"126-141","source":"Crossref","is-referenced-by-count":4,"title":["Monadic NP and Graph Minors"],"prefix":"10.1007","author":[{"given":"Martin","family":"Kreidler","sequence":"first","affiliation":[]},{"given":"Detlef","family":"Seese","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"9_CR1","doi-asserted-by":"publisher","first-page":"113","DOI":"10.2307\/2274958","volume":"55","author":"M. Ajtai","year":"1990","unstructured":"Ajtai, M., Fagin, R.: Reachability is harder for directed than for undirected finite graphs. Journal of Symbolic Logic\u00a055(1), 113\u2013150 (1990)","journal-title":"Journal of Symbolic Logic"},{"key":"9_CR2","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy Problems for Tree-Decomposable Graphs. Journal of Algorithms\u00a012, 308\u2013340 (1991)","journal-title":"Journal of Algorithms"},{"key":"9_CR3","volume-title":"Model Theory","author":"C. Chang","year":"1974","unstructured":"Chang, C., Keisler, H.: Model Theory, 3rd edn. North-Holland, Amsterdam (1974) (1990)","edition":"3"},{"key":"9_CR4","volume-title":"Graph Theory","author":"R. Diestel","year":"1997","unstructured":"Diestel, R.: Graph Theory. Springer, Heidelberg (1997)"},{"key":"9_CR5","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1995","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory. Springer, Heidelberg (1995)"},{"key":"9_CR6","unstructured":"Fagin, R.: Generalized First-Order spectra and polynomial-time recognizable sets. In: Karp, R. (ed.) Complexity of Computation, SIAM-AMS Proc., vol.\u00a07, pp. 27\u201341 (1974)"},{"key":"9_CR7","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1002\/malq.19750210112","volume":"21","author":"R. Fagin","year":"1975","unstructured":"Fagin, R.: Monadic generalized spectra. Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik\u00a021, 89\u201396 (1975)","journal-title":"Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik"},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1002\/malq.19970430402","volume":"43","author":"R. Fagin","year":"1997","unstructured":"Fagin, R.: Comparing the Power of Games on Graphs. Mathematical Logic Quarterly\u00a043, 431\u2013455 (1997)","journal-title":"Mathematical Logic Quarterly"},{"issue":"1","key":"9_CR9","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1006\/inco.1995.1100","volume":"120","author":"R. Fagin","year":"1995","unstructured":"Fagin, R., Stockmeyer, L., Vardi, M.: On Monadic NP vs. Monadic co-NP. Information and Computation\u00a0120(1), 78\u201392 (1995)","journal-title":"Information and Computation"},{"key":"9_CR10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574","volume-title":"Model Theory","author":"W. Hodges","year":"1993","unstructured":"Hodges, W.: Model Theory. Cambridge University Press, Cambridge (1993)"},{"issue":"4","key":"9_CR11","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"Immerman, N.: Languages That Capture Complexity Classes. SIAM Journal of Computing\u00a016(4), 760\u2013778 (1987)","journal-title":"SIAM Journal of Computing"},{"key":"9_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/3-540-63172-0_44","volume-title":"Proc. CSL1996","author":"M. Kreidler","year":"1997","unstructured":"Kreidler, M., Seese, D.: Monadic NP and Built-in Trees. In: van Dalen, D., Bezem, M. (eds.) CSL 1996. LNCS, vol.\u00a01258, pp. 260\u2013274. Springer, Heidelberg (1997)"},{"key":"9_CR13","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley Publishing Company, Reading (1994)"},{"key":"9_CR14","first-page":"153","volume-title":"Surveys in Combinatorics","author":"N. Robertson","year":"1985","unstructured":"Robertson, N., Seymour, P.: Graph minors - a survey. In: Anderson, I. (ed.) Surveys in Combinatorics, pp. 153\u2013171. Cambridge University Press, Cambridge (1985)"},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0095-8956(90)90120-O","volume":"48","author":"N. Robertson","year":"1990","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors IV: Tree-Width and Well-Quasi- Ordering. Journal of Comb. Theory Series B\u00a048, 227\u2013254 (1990)","journal-title":"Journal of Comb. Theory Series B"},{"key":"9_CR16","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1006\/jctb.1995.1034","volume":"64","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.: Graph minors XII: Excluding a non-planar graph. Journal of Combinatorial Theory Series B\u00a064, 240\u2013272 (1995)","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"9_CR17","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.: Graph minors XIII: The disjoint path problem. Journal of Combinatorial Theory Series B\u00a063, 65\u2013110 (1995)","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"9_CR18","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0168-0072(95)00030-5","volume":"79","author":"T. Schwentick","year":"1996","unstructured":"Schwentick, T.: On Winning Strategies in Ehrenfeucht Games and Monadic NP. Annals of Pure and Applied Logic\u00a079, 61\u201392 (1996)","journal-title":"Annals of Pure and Applied Logic"},{"key":"9_CR19","unstructured":"Seese, D., Wessel, W.: Graphminoren und Gitter: Zu einigen Arbeiten von N. Robertson und P. Seymour. In: Wagner, K., Bodendiek,R (eds.) Graphentheorie III, BI Wissenschaftsverlag (1993)"},{"key":"9_CR20","series-title":"Studies in Logic series","volume-title":"Classification Theory and the Number of Non-Isomorphic Models","author":"S. Shelah","year":"1978","unstructured":"Shelah, S.: Classification Theory and the Number of Non-Isomorphic Models. Studies in Logic series. North-Holland, Amsterdam (1978)"},{"key":"9_CR21","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1007\/BF01594196","volume":"114","author":"K. Wagner","year":"1937","unstructured":"Wagner, K.: \u00dcber eine Eigenschaft der ebenen Komplexe. Mathematische Annalen\u00a0114, 570\u2013590 (1937)","journal-title":"Mathematische Annalen"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/10703163_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T08:01:26Z","timestamp":1552636886000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/10703163_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540659228","9783540488552"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/10703163_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1999]]}}}