{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:52:51Z","timestamp":1725663171689},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540514862"},{"type":"electronic","value":"9783540481768"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51486-4_54","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:58:05Z","timestamp":1330203485000},"page":"18-34","source":"Crossref","is-referenced-by-count":0,"title":["Monadic second-order logic and context-free graph-grammars"],"prefix":"10.1007","author":[{"given":"Bruno","family":"Courcelle","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,25]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF01692060","volume":"20","author":"M. Bauderon","year":"1987","unstructured":"BAUDERON M., COURCELLE B., Graph expressions and graph rewritings, Mathematical Systems Theory 20(1987) 83\u2013127.","journal-title":"Mathematical Systems Theory"},{"key":"2_CR2","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1002\/malq.19600060105","volume":"5","author":"J. B\u00fcchi","year":"1960","unstructured":"B\u00dcCHI J., Weak second order logic and finite automata, S.Math. Logik Grundlagen Math. 5 (1960) 66\u201392.","journal-title":"S.Math. Logik Grundlagen Math."},{"key":"2_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(86)90050-2","volume":"42","author":"B. Courcelle","year":"1986","unstructured":"COURCELLE B., Equivalence and transformations of regular systems. Applications to recursive program schemes and grammars, Theor. Comp. Sci. 42 (1986) 1\u2013122.","journal-title":"Theor. Comp. Sci."},{"key":"2_CR4","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0304-3975(87)90102-2","volume":"55","author":"B. Courcelle","year":"1987","unstructured":"COURCELLE B., An axiomatic definition of context-free rewriting and its application to NLC graph grammars, Theoretical Computer Science 55 (1987) 141\u2013181.","journal-title":"Theoretical Computer Science"},{"key":"2_CR5","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/3-540-18771-5_49","volume":"291","author":"B. Courcelle","year":"1987","unstructured":"COURCELLE B., A representation of graphs by algebraic expressions and its use for graph rewriting systems, Proceedings of the 3rd international workshop on grah grammars,-L.N.C.S. 291, 1987, pp. 112\u2013132.","journal-title":"Lecture Notes in Computer Science"},{"key":"2_CR6","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/3-540-18771-5_50","volume":"291","author":"B. Courcelle","year":"1987","unstructured":"COURCELLE B., On context-free sets of graphs and their monadic second-order theory Proceedings fo te 3rd international workshop on graph grammars,-L.N.C.S. 291, 1987,pp. 133\u2013146.","journal-title":"Lecture Notes in Computer Science"},{"key":"2_CR7","unstructured":"COURCELLE B., Some applications of logic, of universal algebra and of category theory to the theory of graph transformations, Bulleting of E.A.T.C.S. no 36, October 1988, pp. 161\u2013218."},{"key":"2_CR8","unstructured":"COURCELLE B., Graph rewriting: An algebraic and logical approach, in \"Handbook of Computer Science\", J. Van Leeuwen ed., North-Holland-Elsevier, to appear."},{"key":"2_CR9","unstructured":"COURCELLE B., On the use of context-free graph grammars for analyzing recursive definitions, in \"Programming of future generation computers II\", K. Fuchi, L.Kott eds., Elsevier, 1988,pp. 83\u2013122."},{"key":"2_CR10","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1007\/3-540-50728-0_34","volume":"344","author":"B. Courcelle","year":"1989","unstructured":"COURCELLE B., The monadic second-order logic of graphs:Definable sets of finite graphs, Workshop on graph Theoretical concepts in computer science,-L.N.C.S. 344, (1989) pp. 30\u201353.","journal-title":"Lecture Notes in Computer Science"},{"key":"2_CR11","unstructured":"COURCELLE B., The monadic second-order logic of graphs I: Recognizable sets of finite graphs, to appear in Information and Computation."},{"key":"2_CR12","unstructured":"COURCELLE B., The monadic second-order logic of graphs II: Infinite graphs of bounded width, to appear in Mathematical Systems Theory."},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"COURCELLE B., The monadic second-order logic of graphs III: Tree-width, forbidden minors, and complexity issues, Report I-8852, 1988, Bordeaux-1 University, submitted.","DOI":"10.1007\/BF02088013"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"COURCELLE B., The monadic second-order logic of graphs IV: Every equational graph is definable, Report I-8830, 1988, Submitted for publication.","DOI":"10.1007\/3-540-50728-0_34"},{"key":"2_CR15","unstructured":"COURCELLE B., The monadic second-order logic of graphs V: On context-free graph-grammars generating definable sets., Research report in preparation."},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"COURCELLE B., On recognizable sets and tree-automata, in \"Resolution of equations in algebraic structures\", H.Ait-Kaci and M.Nivat eds., Academic Press, 1989.","DOI":"10.1016\/B978-0-12-046370-1.50009-7"},{"key":"2_CR17","unstructured":"COURCELLE B., ENGELFRIET J., ROZENBERG.G., In preparation."},{"key":"2_CR18","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1016\/S0022-0000(70)80041-1","volume":"4","author":"J. Doner","year":"1970","unstructured":"DONER J., Tree acceptors and some of their applications, J. Comput System Sci. 4(1970) 406\u2013451.","journal-title":"J. Comput System Sci."},{"key":"2_CR19","unstructured":"EHRIG H. et al., eds, Graph-grammars and their applications in computer science and biology, L.N.C.S. Lecture Notes in Computer Science. Springer 73, 1979."},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"EHRIG. H. et al., eds, Graph-grammars and their applications to computer science, L.N.C.S. Lecture Notes in Computer Science. Springer 153, 1983.","DOI":"10.1007\/BFb0000094"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"EHRIG. H. et al., eds, Graph-grammars and their applications to computer science, L.N.C.S. Lecture Notes in Computer Science. Springer 291, 1987.","DOI":"10.1007\/3-540-18771-5"},{"key":"2_CR22","unstructured":"ENGELFRIET J., Private communication, October 1988."},{"key":"2_CR23","unstructured":"GECSEG F., STEINBY M., Tree-automata, Akademia kiado, Budapest, 1984."},{"key":"2_CR24","first-page":"68","volume":"24","author":"J. Goguen","year":"1977","unstructured":"GOGUEN J., THATCHER J., WAGNER E., WRIGHT J., Initial algebra semantics and continuous algebras,-L.N.C.S. 24 (1977) 68\u201395.","journal-title":"Lecture Notes in Computer Science"},{"key":"2_CR25","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0304-3975(87)90050-8","volume":"51","author":"A. Habel","year":"1987","unstructured":"HABEL A., KREOWSKI H.J., Characteristics of graph languages generated by edge replacement, Theoret. Comp. Sci 51 (1987) 81\u2013115.","journal-title":"Theoret. Comp. Sci"},{"key":"2_CR26","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/3-540-18771-5_41","volume":"291","author":"A. Habel","year":"1987","unstructured":"HABEL A., KREOWSKI H.J., May we introduce to you: hyperedge replacement,-L.N.C.S. 291, (1987), pp. 15\u201326.","journal-title":"Lecture Notes in Computer Science"},{"key":"2_CR27","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/3-540-12727-5_5","volume":"159","author":"D. Janssens","year":"1983","unstructured":"JANSSENS D., ROZENBERG G., A survey of NLC grammars, in Proc. CAAP'83,-L.N.C.S. 159, (1983), pp. 114\u2013128.","journal-title":"Lecture Notes in Computer Science"},{"key":"2_CR28","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/3-540-19488-6_128","volume":"317","author":"C. Lautemann","year":"1988","unstructured":"LAUTEMANN C., Efficient algorithms on context-free graph languages, ICALP'88, Tampere,-L.N.C.S. 317, (1988), pp. 362\u2013378.","journal-title":"Lecture Notes in Computer Science"},{"key":"2_CR29","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/3-540-19488-6_129","volume":"317","author":"T. Lengauer","year":"1988","unstructured":"LENGAUER T., WANKE E., Efficient analysis of graph properties on context-free graph languages, ICAP'88,-L.N.C.S. 317, (1988), pp. 379\u2013393.","journal-title":"Lecture Notes in Computer Science"},{"key":"2_CR30","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0019-9958(67)90353-1","volume":"11","author":"J. Mezei","year":"1967","unstructured":"MEZEI J., WRIGHT J., Algebraic automata and context-free sets, Information and control 11 (1967) 3\u201329.","journal-title":"Information and control"},{"key":"2_CR31","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1007\/3-540-18771-5_69","volume":"291","author":"U. Montanari","year":"1987","unstructured":"MONTANARI U., ROSSI F., An efficient algorithm for the solution of hierarchical networks of constraints.-L.N.C.S. 291, (1987), pp. 440\u2013457.","journal-title":"Lecture Notes in Computer Science"},{"key":"2_CR32","first-page":"343","volume":"23","author":"N. Roberston","year":"1984","unstructured":"ROBERSTON N., SEYMOUR P., Some new results on the well-quasi-ordering of graphs, Annals of Discrete Mathematics 23 (1984) 343\u2013354 (Elsevier Science Publisher).","journal-title":"Annals of Discrete Mathematics"},{"key":"2_CR33","unstructured":"SEESE D., The structure of the models of decidable monadic theories of graphs, Preprint 1987, to appear in the Journal of Pure and Applied Logic."},{"key":"2_CR34","unstructured":"THOMAS W., Automata on infinite objects, \"Handbook of Theoretical Computer Science\", same volume as [8]."},{"key":"2_CR35","first-page":"569","volume":"70","author":"B. Trahtenbrot","year":"1950","unstructured":"TRAHTENBROT B., Impossibility of an algorithm for the decision problem on finite classes, Doklady Nauk. SSR 70, (1950), 569\u2013572.","journal-title":"Doklady Nauk. SSR"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1989"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51486-4_54.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T02:54:11Z","timestamp":1640919251000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51486-4_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540514862","9783540481768"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/3-540-51486-4_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}