{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:32:50Z","timestamp":1725564770448},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540204527"},{"type":"electronic","value":"9783540398905"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39890-5_21","type":"book-chapter","created":{"date-parts":[[2010,9,3]],"date-time":"2010-09-03T21:16:57Z","timestamp":1283548617000},"page":"237-248","source":"Crossref","is-referenced-by-count":5,"title":["NCE Graph Grammars and Clique-Width"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Glikson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johann A.","family":"Makowsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"21_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BFb0029946","volume-title":"Mathematical Foundations of Computer Science 1997","author":"H. Bodlaender","year":"1997","unstructured":"Bodlaender, H.: Treewidth: Algorithmic techniques and results. In: Privara, I., Ru\u017ei\u010dka, P. (eds.) MFCS 1997. LNCS, vol.\u00a01295, pp. 29\u201336. Springer, Heidelberg (1997)"},{"key":"21_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci.\u00a0209, 1\u201345 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01204169","volume":"28","author":"B. Courcelle","year":"1995","unstructured":"Courcelle, B., Engelfriet, J.: A logical characterization of the sets of hypergraphs defined by hyperedge replacement grammars. Mathematical Systems Theory\u00a028, 515\u2013552 (1995)","journal-title":"Mathematical Systems Theory"},{"key":"21_CR4","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B. Courcelle","year":"1993","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. Journal of computer and system sciences\u00a046, 218\u2013270 (1993)","journal-title":"Journal of computer and system sciences"},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"Corneil, D., Habib, M., Lanlignel, J., Read, B., Rotics, U.: Polynomial time recogntion of clique-width \u2264 3 graphs. LNCS, vol.\u00a01726, pp. 126\u2013134 (2000)","DOI":"10.1007\/10719839_14"},{"key":"21_CR6","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique-width of graphs. Discrete Applied Mathematics\u00a0101, 77\u2013114 (2000)","journal-title":"Discrete Applied Mathematics"},{"key":"21_CR7","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Systems\u00a033, 125\u2013150 (2000)","journal-title":"Theory Comput. Systems"},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"Courcelle, B., Makowsky, J.A.: Fusion on relational structures and the verification of monadic second order properties. Mathematical Structures in Computer Science, 12 (2002) (in print)","DOI":"10.1017\/S0960129501003565"},{"key":"21_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/3-540-45477-2_9","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D. Corneil","year":"2001","unstructured":"Corneil, D., Rotics, U.: On the relationship between clique-width and tree-width. In: Brandst\u00e4dt, A., Le, V.B. (eds.) WG 2001. LNCS, vol.\u00a02204, pp. 78\u201390. Springer, Heidelberg (2001)"},{"key":"21_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(92)90148-9","volume":"101","author":"B. Courcelle","year":"1992","unstructured":"Courcelle, B.: Monadic second-order logic of graphs VII: Graphs as relational structures. Theoretical Computer Science\u00a0101, 3\u201333 (1992)","journal-title":"Theoretical Computer Science"},{"key":"21_CR11","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1006\/inco.1995.1020","volume":"116","author":"B. Courcelle","year":"1995","unstructured":"Courcelle, B.: Structural properties of context-free sets of graphs generated by vertex replacement. Information and Computation\u00a0116, 275\u2013293 (1995)","journal-title":"Information and Computation"},{"key":"21_CR12","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1142\/9789812384720_0002","volume-title":"Handbook of graph grammars and computing by graph transformations, Foundations","author":"F. Drewes","year":"1997","unstructured":"Drewes, F., Kreowski, H.-J., Habel, H.: Hyperedge replacement. In: Rozenberg, G. (ed.) Handbook of graph grammars and computing by graph transformations, Foundations, vol.\u00a01, pp. 95\u2013162. World Scientific, Singapore (1997)"},{"key":"21_CR13","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-3-642-59126-6_3","volume-title":"Handbook of formal languages, Beyond Words","author":"J. Engelfriet","year":"1997","unstructured":"Engelfriet, J.: Context-free graph grammars. In: Handbook of formal languages, Beyond Words, vol.\u00a03, pp. 125\u2013213. Springer, Heidelberg (1997)"},{"key":"21_CR14","series-title":"Perspectives in Mathematical Logic","volume-title":"Finite Model Theory","author":"H.D. Ebbinghaus","year":"1995","unstructured":"Ebbinghaus, H.D., Flum, J.: Finite Model Theory. Perspectives in Mathematical Logic. Springer, Heidelberg (1995)"},{"key":"21_CR15","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0890-5401(90)90038-J","volume":"84","author":"J. Engelfriet","year":"1990","unstructured":"Engelfriet, J., Rozenberg, G.: A comparison of boundary graph grammars and context-free hypergraph grammars. Information and Computation\u00a084, 163\u2013206 (1990)","journal-title":"Information and Computation"},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1006\/jcss.1997.1510","volume":"55","author":"J. Engelfriet","year":"1997","unstructured":"Engelfriet, J., van Oostrom, V.: Logical description of context-free graphlanguages. Journal of Computer and System Sciences\u00a055, 489\u2013503 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"21_CR17","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0304-3975(97)00212-0","volume":"201","author":"M. Flasi\u0144ski","year":"1998","unstructured":"Flasi\u0144ski, M.: Power properties of NLC graph grammars with a polynomial membership problem. Theoretical Computer Science\u00a0201, 189\u2013231 (1998)","journal-title":"Theoretical Computer Science"},{"key":"21_CR18","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1145\/167088.167245","volume-title":"STOC 1993","author":"T. Feder","year":"1993","unstructured":"Feder, T., Vardi, M.: The computational structure of monotone monadic SNP and constraint satisfaction. In: STOC 1993, pp. 612\u2013622. ACM, New York (1993)"},{"key":"21_CR19","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1142\/S0129054100000260","volume":"11","author":"M.C. Golumbic","year":"2000","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Internation Journal of Foundations of Computer Science\u00a011, 423\u2013443 (2000)","journal-title":"Internation Journal of Foundations of Computer Science"},{"key":"21_CR20","unstructured":"Glikson, A.: M. Sc. thesis. The Technion, Israeli Institute of Technology (2003), http:\/\/www.cs.technion.ac.il\/admlogic\/readme.html"},{"key":"21_CR21","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/S0304-3975(97)86542-5","volume":"186","author":"C. Kim","year":"1997","unstructured":"Kim, C.: A hierarchy of eNCE families of graph languages. Theoretical Computer Science\u00a0186, 157\u2013169 (1997)","journal-title":"Theoretical Computer Science"},{"key":"21_CR22","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/PL00013320","volume":"37","author":"C. Kim","year":"2001","unstructured":"Kim, C.: Efficient recogniztion algorithms for boundary and linear eNCE graph languages. Acta Informatica\u00a037, 619\u2013623 (2001)","journal-title":"Acta Informatica"},{"key":"21_CR23","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/S0304-3975(99)00258-3","volume":"223","author":"C. Kim","year":"1999","unstructured":"Kim, C., Jeong, T.E.: HRNCE grammars - a hypergraph generating system with an eNCE way of rewriting. Theoretical Computer Science\u00a0223, 143\u2013178 (1999)","journal-title":"Theoretical Computer Science"},{"key":"21_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/BFb0026094","volume-title":"CAAP \u201988","author":"C. Lautemann","year":"1988","unstructured":"Lautemann, C.: Decomposition trees: structured graph representation and efficient algorithms. In: Dauchet, M., Nivat, M. (eds.) CAAP 1988. LNCS, vol.\u00a0299, pp. 28\u201339. Springer, Heidelberg (1988)"},{"key":"21_CR25","unstructured":"Makowsky, J.A.: Algorithmic uses of the Feferman-Vaught theorem. Submitted to the Special Issue of APAL with papers from the Tarski Centennary Conference (January 2003)"},{"key":"21_CR26","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors. II. Algorithmic Aspects of Treewidth. J. Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"J. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39890-5_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,3]],"date-time":"2019-06-03T09:19:36Z","timestamp":1559553576000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39890-5_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540204527","9783540398905"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39890-5_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}