{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T03:26:16Z","timestamp":1763436376249},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540544876"},{"type":"electronic","value":"9783540384014"}],"license":[{"start":{"date-parts":[[1991,1,1]],"date-time":"1991-01-01T00:00:00Z","timestamp":662688000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54487-9_49","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:53:34Z","timestamp":1330210414000},"page":"1-16","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Monadic second order logic, tree automata and forbidden minors"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Arnborg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Proskurowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Detlef","family":"Seese","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"1_CR1","unstructured":"M.R. Fellows and K. Abrahamson 1989, Cutset-Regularity Beats Well-Quasi-Ordering for Bounded Tree-width (Extended Abstract), preprint Nov. 1989."},{"key":"1_CR2","unstructured":"S. Arnborg, A. Proskurowski and D.G. Corneil 1986, Forbidden minor characterization of partial 3-trees, Discrete Math., to appear."},{"key":"1_CR3","unstructured":"S.Arnborg, B.Courcelle, A. Proskurowski and D. Seese 1990, An algebraic theory of graph reduction, preprint January 17, 1990."},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"S. Arnborg and J. Lagergren 1990, Finding minimal forbidden minors using a finite congruence, preprint November 13, 1990.","DOI":"10.1007\/3-540-54233-7_161"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"S. Arnborg, J. Lagergren and D. Seese 1988, Problems Easy for Tree-descomosable graphs (extended abstract). Proc. 15th ICALP, Springer Verlag, Lect. Notes in Comp. Sc. 317 38\u201351.","DOI":"10.1007\/3-540-19488-6_105"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"S. Arnborg, J. Lagergren and D. Seese 1989, Problems Easy for Tree-descomposable graphs to appear in J. of Algorithm.","DOI":"10.1007\/3-540-19488-6_105"},{"key":"1_CR7","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0607033","volume":"7","author":"S. Arnborg","year":"1986","unstructured":"S. Arnborg and A. Proskurowski 1986, Characterization and Recognition of Partial 3-trees, SIAM J.Alg. and Discr. Methods 7, 305\u2013314.","journal-title":"SIAM J.Alg. and Discr. Methods"},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"S. Arnborg and A. Proskurowski 1989, Linear Time Algorithm for NP-hard Problems on Graphs Embedded in k-trees Discr. Appl. Math. 23, 11\u201324.","journal-title":"Discr. Appl. Math."},{"key":"1_CR9","unstructured":"S. Arnborg, A. Proskurowski, and D. Seese 1989, Logical description of graphs of path-width 2 and their minimal forbidden minors (Draft), preliminary version, preprint July 25, 1989."},{"key":"1_CR10","unstructured":"H.L. Bodlaender 1887, Dynamic Programming on Graphs with Bounded Tree-width, MIT\/LCS\/TR-394, MIT."},{"key":"1_CR11","unstructured":"H.L. Bodlaender 1988, Improved self-reduction algorithms for graphs with bounded tree-width, Technical Report RUU-CS-88-29, September 1988, University of Utrecht."},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender, T. KloksBetter Algorithms for the Pathwidth and Treewidth of Graphs (extended abstract), preprint 1990.","DOI":"10.1007\/3-540-54233-7_162"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"J.A. Bondy and U.S.R. Murty 1976, Graph Theory with Applications, North Holland.","DOI":"10.1007\/978-1-349-03521-2"},{"key":"1_CR14","unstructured":"B. Courcelle 1988, The monadic second order logic of graphs III: Tree-width, forbidden minors, and complexity issues, Report I \u2014 8852, Bordeaux-1 University."},{"key":"1_CR15","unstructured":"J.E. Doner 1966, Decidability of the Weak Second Order Theory of two Successors, Abstract 65T-468, Notices Amer. Math. Soc. 12, 819,ibid., 513."},{"key":"1_CR16","unstructured":"M. Fellows 1989, Nonconstructive Proofs of Polynomial-Time Complexity: Algorithms for Computing Obstructing Sets, draft, preprint April 12, 1989."},{"key":"1_CR17","unstructured":"M. Fellows 1989, Applications of an Analogue of the Myhill-Nerode Theorem, In Obstruction Set Computation, preprint April 28, 1989."},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0020-0190(87)90054-8","volume":"26","author":"M. Fellows","year":"1987","unstructured":"M. Fellows and M. Langston 1987, Nonconstructive Advances in Polynomial Time Complexity, Info. Proc. Letters 26, 157\u2013162.","journal-title":"Info. Proc. Letters"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"M. Fellows and M. Langston 1989, An Analogue of the Myhill-Nerode Theorem and Its Use in Computing Finite-Basis Characterizations (Extended Abstract), to appear, FOCS 89.","DOI":"10.1109\/SFCS.1989.63528"},{"key":"1_CR20","unstructured":"M. Fellows and M.Langston 1989, Exploiting RS Posets: Constructive Algorithms from Nonconstructive Tools, preprint revised February 1989."},{"key":"1_CR21","unstructured":"N.Kinnersley 1989, Obstruction set isolation for layout permutation problems, Ph.D. thesis, Washington State University."},{"key":"1_CR22","unstructured":"J. Matou\u0161ek, R. ThomasAlgorithms finding tree \u2014 decompositions of graphs, preprint 1988."},{"key":"1_CR23","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0012-365X(84)90164-X","volume":"49","author":"A. Proskurowski","year":"1984","unstructured":"A. Proskurowski 1984, Separating subgraphs in k-trees: cables and caterpillar, Discrete Mathematics 49, 275\u2013285.","journal-title":"Discrete Mathematics"},{"key":"1_CR24","unstructured":"M.O. Rabin 1964, A simple Method of Undecidability proofs and some applications, in Log. Meth. Phil. Sci. Proc. Jerusalem, 58\u201368."},{"key":"1_CR25","first-page":"1","volume":"141","author":"M.O. Rabin","year":"1969","unstructured":"M.O. Rabin 1969, Desidability of second order and automata on infinite trees, Trans. Am. Math. Soc. 141, 1\u201335.","journal-title":"Trans. Am. Math. Soc."},{"key":"1_CR26","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"N. Robertson and P.D. Seymour 1983, Graph Minors I. Excluding a forest, J. Combin. Theory Ser.B. 35, 39\u201361.","journal-title":"J. Combin. Theory Ser.B."},{"key":"1_CR27","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P.D. Seymour 1986 Graph Minors II. Algorithmic Aspects of Tree Width Journal of Algorithms, 7, 309\u2013322.","journal-title":"Journal of Algorithms"},{"key":"1_CR28","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P.D. Seymour 1986, Graph Minors V. Excluding a planar graph J. Combinatorial Theory, Ser. B, 41, 92\u2013114.","journal-title":"J. Combinatorial Theory, Ser. B"},{"key":"1_CR29","doi-asserted-by":"crossref","unstructured":"N. Robertson and P.D. Seymour 1986, Graph Minors XIII. The Disjoint Path Problem Preprint.","DOI":"10.1016\/0095-8956(86)90031-6"},{"key":"1_CR30","unstructured":"N. Robertson and P.D. Seymour 1988, Graph Minors XV. Wagners conjecture Preprint."},{"key":"1_CR31","volume-title":"Personal Communication","author":"N. Robertson","year":"1989","unstructured":"N. Robertson and P.D. Seymour 1989, Personal Communication, Toronto, Eugene."},{"key":"1_CR32","unstructured":"P. Scheffler 1986, Dynamic programming algorithms for tree-descomposition problems, Karl-Weierstrass-Institut f\u00fcr Mathematik, Preprint P-Math-28\/86, Berlin."},{"key":"1_CR33","volume-title":"Die Baumwerte von Graphen als ein Ma\u00df f\u00fcr die Kompliziertheit algorithmischer Probleme","author":"P. Scheffler","year":"1989","unstructured":"P. Scheffler 1989 Die Baumwerte von Graphen als ein Ma\u00df f\u00fcr die Kompliziertheit algorithmischer Probleme, Dissertation (A), AdW d. DDR, Berlin 1989."},{"key":"1_CR34","first-page":"412","volume-title":"FCT'85","author":"D. Seese","year":"1985","unstructured":"D. Seese 1985, Tree-partite graphs and the complexity of algorithms (extended abstract), in FCT'85, ed. L. Budach, LNCS 199, Springer, Berlin, 412\u2013421."},{"key":"1_CR35","unstructured":"D. Seese 1986, Tree-partite graphs and the complexity of algorithms, preprint P-Math 08\/86, Karl-Weierstrass-Institute f\u00fcr Mathematik."},{"key":"1_CR36","doi-asserted-by":"crossref","unstructured":"J.W. Thatcher and J.B. Wright 1968, Generalized Finite Automata Theory with an Application to a Decision Problem in Second-Order Logic, Mathematical Systems Theory 2, 57\u201381.","DOI":"10.1007\/BF01691346"},{"key":"1_CR37","unstructured":"T.V. Wimer 1988, Ph D Thesis URI-030, Clemson."}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54487-9_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T03:49:59Z","timestamp":1640922599000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54487-9_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540544876","9783540384014"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/3-540-54487-9_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]},"assertion":[{"value":"3 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}