{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:38Z","timestamp":1725663278404},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540514985"},{"type":"electronic","value":"9783540481805"}],"license":[{"start":{"date-parts":[[1989,1,1]],"date-time":"1989-01-01T00:00:00Z","timestamp":599616000000},"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":[[1989]]},"DOI":"10.1007\/3-540-51498-8_46","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:02:30Z","timestamp":1330203750000},"page":"470-479","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The complexity of connectivity problems on context-free graph languages"],"prefix":"10.1007","author":[{"given":"Egon","family":"Wanke","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"46_CR1","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(87)90102-2","volume":"55","author":"B. Courcelle","year":"1987","unstructured":"B. Courcelle. An axiomatic definition of context-free rewriting and its application to NLC graph grammars. Theoretical Computer Science, 55:141\u2013181, 1987.","journal-title":"Theoretical Computer Science"},{"key":"46_CR2","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/3-540-18771-5_50","volume-title":"Proceedings of Graph-Grammars and Their Application to Computer Science '86","author":"B. Courcelle","year":"1987","unstructured":"B. Courcelle. On context-free sets of graphs and their monadic second-order theory. In H. Ehrig, M. Nagl, A. Rosenfeld, and G. Rozenberg, editors, Proceedings of Graph-Grammars and Their Application to Computer Science '86, pages 133\u2013146, LNCS No. 291, Springer Verlag, Berlin\/New York, 1987."},{"key":"46_CR3","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/3-540-18771-5_52","volume-title":"Proceedings of Graph-Grammars and Their Application to Computer Science '86","author":"J. Engelfriet","year":"1987","unstructured":"J. Engelfriet, G Leih, and G Rozenberg. Apex graph grammars. In H. Ehrig, M. Nagl, A. Rosenfeld, and G. Rozenberg, editors, Proceedings of Graph-Grammars and Their Application to Computer Science '86, pages 167\u2013185, LNCS No. 291, Springer Verlag, Berlin\/New York, 1987."},{"key":"46_CR4","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/3-540-50728-0_33","volume-title":"Proceedings of Graph-Theoretic Concepts in Computer Science, WG '88","author":"A. Habel","year":"1989","unstructured":"A. Habel. Graph-theoretic properties compatible with graph derivations. In J. van Leeuwen, editor, Proceedings of Graph-Theoretic Concepts in Computer Science, WG '88, pages 11\u201329, LNCS No. 344, Springer Verlag, Berlin\/New York, 1989."},{"key":"46_CR5","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/3-540-18771-5_41","volume-title":"Proceedings of Graph-Grammars and Their Application to Computer Science '86","author":"A. Habel","year":"1987","unstructured":"A. Habel and H.J. Kreowski. May we introduce to you: hyperedge replacement. In H. Ehrig, M. Nagl, A. Rosenfeld, and G. Rozenberg, editors, Proceedings of Graph-Grammars and Their Application to Computer Science '86, pages 15\u201326, LNCS No. 291, Springer Verlag, Berlin\/New York, 1987."},{"unstructured":"A. Habel, H.J. Kreowski, and W. Vogler. Compatible graph properties are decidable for hyperedge replacement graph languages. In Bulletin of the European Association for Theoretical Computer Science No. 33, pages 55\u201362, EATCS, October 1987. To appear in Acta Informatica.","key":"46_CR6"},{"key":"46_CR7","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. E. Hopcroft","year":"1979","unstructured":"J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, Massachusetts, 1979."},{"key":"46_CR8","series-title":"LNCS","first-page":"379","volume-title":"Proceedings of ICALP '88","author":"T. Lengauer","year":"1988","unstructured":"T. Lengauer and E. Wanke. Efficient analysis of graph properties on context-free graph languages. In T. Lepist\u00f6 and A. Salomaa, editors, Proceedings of ICALP '88, pages 379\u2013393, LNCS No. 317, Springer Verlag, Berlin\/New York, 1988."},{"issue":"6","key":"46_CR9","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.1137\/0217068","volume":"17","author":"T. Lengauer","year":"1988","unstructured":"T. Lengauer and E. Wanke. Efficient solution of connectivity problems on hierarchically defined graphs. SIAM Journal of Computing, 17(6):1063\u20131080, 1988.","journal-title":"SIAM Journal of Computing"},{"issue":"1\u20133","key":"46_CR10","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/S0019-9958(86)80045-6","volume":"69","author":"G. Rozenberg","year":"1986","unstructured":"G. Rozenberg and E. Welzl. Boundary NLC graph grammars \u2014 basic definitions, normal forms, and complexity. Information and Control, 69(1\u20133):136\u2013167, April\/May\/June 1986.","journal-title":"Information and Control"},{"key":"46_CR11","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/BF00289115","volume":"23","author":"G. Rozenberg","year":"1986","unstructured":"G. Rozenberg and E. Welzl. Graph theoretic closure properties of the family of boundary NLC graph languages. Acta Informatica, 23:289\u2013309, 1986.","journal-title":"Acta Informatica"},{"key":"46_CR12","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0166-218X(87)90054-0","volume":"16","author":"G. Rozenberg","year":"1987","unstructured":"G. Rozenberg and E. Welzl. Combinatorial properties of boundary NLC graph languages. Discrete Applied Mathematics, 16:59\u201373, 1987.","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"46_CR13","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/0020-0190(82)90086-2","volume":"14","author":"A. O. Slisenko","year":"1982","unstructured":"A.O. Slisenko. Context-free grammars as a tool for describing polynomial-time subclasses of hard problems. Information Processing Letters, 14(2):52\u201356, 1982.","journal-title":"Information Processing Letters"},{"key":"46_CR14","series-title":"Technical Report","volume-title":"Algorithms for graph problems on BNLC structured graphs","author":"E. Wanke","year":"1989","unstructured":"E. Wanke. Algorithms for graph problems on BNLC structured graphs. Technical Report 58, Universit\u00e4t-Gesamthochschule Paderborn, West-Germany, 1989."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51498-8_46","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T02:06:28Z","timestamp":1578535588000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51498-8_46"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540514985","9783540481805"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-51498-8_46","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]},"assertion":[{"value":"28 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}