{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:02:10Z","timestamp":1725483730878},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679011"},{"type":"electronic","value":"9783540446125"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44612-5_49","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T13:28:20Z","timestamp":1178371700000},"page":"539-548","source":"Crossref","is-referenced-by-count":1,"title":["Automatic Graphs and Graph D0L-Systems"],"prefix":"10.1007","author":[{"given":"Olivier","family":"Ly","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,1]]},"reference":[{"key":"49_CR1","doi-asserted-by":"crossref","unstructured":"L. W. Ahlfors and L. Sario. Riemann Surfaces. Princeton University Press, 1960.","DOI":"10.1515\/9781400874538"},{"key":"49_CR2","unstructured":"A. Blumensath and E. Gr\u00e4del. Automatic structures. In LICS\u20192000, 2000."},{"key":"49_CR3","unstructured":"A. Carbonne and S. Semmes. A graphic apology for symmetry and implicitness. Preprint."},{"key":"49_CR4","volume-title":"Computer Program","author":"A. Clow","year":"1998","unstructured":"A. Clow and S. Billington. Recognizing Two-Ended and Infinitely Ended Automatic Groups. Computer Program, Warwick University-UK, 1998."},{"key":"49_CR5","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(83)90059-2","volume":"25","author":"B. Courcelle","year":"1983","unstructured":"B. Courcelle. Fundamental Properties of Infinite Trees. Theoretical Computer Science, 25:95\u2013169, 1983.","journal-title":"Theoretical Computer Science"},{"key":"49_CR6","doi-asserted-by":"crossref","unstructured":"B. Courcelle. Graph Rewriting: An algebraic and Logic Approach. In Handbook of Theoretical Computer Science vol. B, Van Leeuwen J. (editor). Elsevier Science Publishers, 1990.","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"49_CR7","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0168-0072(90)90027-Y","volume":"49","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle. The Monadic Second-order Logic of Graphs IV: Definability Properties of Equational Graphs. Annals of Pure and Applied Logic, 49:193\u2013255, 1990.","journal-title":"Annals of Pure and Applied Logic"},{"key":"49_CR8","doi-asserted-by":"crossref","unstructured":"B. Courcelle. The Expression of Graph Properties and Graph Transformations in Monadic Second-Order Logic. In G. Rozenberg, (editor), Handbook of Graph Grammars and Computing by Graph Transformation, volume 1. World Scientific, 1997.","DOI":"10.1142\/9789812384720_0005"},{"issue":"6","key":"49_CR9","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01204169","volume":"28","author":"B. Courcelle","year":"1995","unstructured":"B. Courcelle and J. Engelfriet. A logical characterization of the sets of hypergraphs defined by hyperedge replacement grammars. Math. Syst. Theory, 28(6):515\u2013552, 1995.","journal-title":"Math. Syst. Theory"},{"key":"49_CR10","first-page":"218","volume":"46","author":"B. Courcelle","year":"1993","unstructured":"B. Courcelle, J. Engelfriet, and G. Rozenberg. Handle Rewriting Hypergraph Grammars. JCSS, 46:218\u2013270, 1993.","journal-title":"JCSS"},{"key":"49_CR11","doi-asserted-by":"crossref","unstructured":"M. De Does and A. Lindenmayer. Algorithms for the Generation and Drawing of Maps Representing Cell Clones. In GGACS\u201982, volume 153 of Lect. Notes in Comp. Sci., pages 39\u201357. Springer-Verlag, 82.","DOI":"10.1007\/BFb0000098"},{"key":"49_CR12","unstructured":"W. Dicks and M.J. Dunwoody. Groups Acting on Graphs, volume 17 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, 1989."},{"key":"49_CR13","doi-asserted-by":"crossref","unstructured":"J. Engelfriet and G. Rozenberg. Node Replacement Graph Grammars. In G. Rozenberg, (editor), Handbook of Graph Grammars and Computing by Graph Transformation, volume 1. World Scientific, 1997.","DOI":"10.1142\/9789812384720_0001"},{"key":"49_CR14","doi-asserted-by":"crossref","unstructured":"D.B.A. Epstein, J.W. Cannon, D.F. Holt, S.V.F. Levy, M.S. Paterson, and W.P. Thurston. Word processing in groups. Jones and Bartlett, 1992.","DOI":"10.1201\/9781439865699"},{"key":"49_CR15","unstructured":"V. Gerasimov. Detecting Connectedness of the Boundary of a Hyperbolic Group. Preprint, 1999."},{"key":"49_CR16","doi-asserted-by":"crossref","unstructured":"E. Ghys and P. de la Harpe. Sur les groupes hyperboliques d\u2019apr\u00e9es Mikhael Gromov, volume 83 of Progress in Mathematics. Birkh\u00e4user, 1990.","DOI":"10.1007\/978-1-4684-9167-8"},{"key":"49_CR17","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF01362670","volume":"157","author":"R. Halin","year":"1964","unstructured":"R. Halin. \u00dcber Unendliche Wege in Graphen. Math. Ann., 157:125\u2013137, 1964.","journal-title":"Math. Ann."},{"key":"49_CR18","unstructured":"J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing Company, 1979."},{"key":"49_CR19","series-title":"Lecture Notes in Comput. Sci","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/3-540-60178-3_93","volume-title":"Logic and Computational Complexity (Indianapolis, IN, 1994)","author":"B. Khoussainov","year":"1995","unstructured":"B. Khoussainov and A. Nerode. Automatic Presentations of Structures. In Logic and Computational Complexity (Indianapolis, IN, 1994), volume 960 of Lecture Notes in Comput. Sci, pages 367\u2013392. Springer, Berlin, 1995."},{"key":"49_CR20","doi-asserted-by":"crossref","unstructured":"A. Lindenmayer. An Introduction to Parallel Map Generating Systems. In GGACS\u201986, volume 291 of Lect. Notes in Comp. Sci., pages 27\u201340. Springer-Verlag, 1986.","DOI":"10.1007\/3-540-18771-5_42"},{"key":"49_CR21","doi-asserted-by":"crossref","unstructured":"A. Lindenmayer and G. Rozenberg. Parallel generation of maps: developmental systems systems for cell layers. In GGACS\u201978, volume 73 of Lect. Notes in Comp. Sci., pages 301\u2013316. Springer-Verlag, 1978.","DOI":"10.1007\/BFb0025728"},{"key":"49_CR22","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1090\/conm\/250\/03847","volume":"250","author":"O. Ly","year":"1999","unstructured":"O. Ly. On Effective Decidability of the Homeomorphism Problem for Non-Compact Surfaces. Contemporary Mathematics-Amer. Math. Soc., 250:89\u2013112, 1999.","journal-title":"Contemporary Mathematics-Amer. Math. Soc."},{"key":"49_CR23","unstructured":"W. S. Massey. Algebraic Topology: An Introduction, volume 56 of Graduate Text in Mathematics. Springer, 1967."},{"key":"49_CR24","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0304-3975(85)90087-8","volume":"37","author":"D. E. Muller","year":"1985","unstructured":"D. E. Muller and P. E. Schupp. The theory of ends, pushdown automata, and second-order logic. Theoretical Computer Science, 37:51\u201375, 1985.","journal-title":"Theoretical Computer Science"},{"key":"49_CR25","unstructured":"P. Narbel. Limits and Boundaries of Word and Tiling Substitutions. PhD thesis, Paris 7, 1993."},{"key":"49_CR26","unstructured":"C.H. Papadimitriou. Computational Complexity. Addison-Wesley Publishing Company, 1994."},{"key":"49_CR27","unstructured":"L. Pelecq. Isomorphisme et automorphismes des graphes context-free, \u00e9quationnels et automatiques. PhD thesis, Bordeaux I, 1997."},{"issue":"4","key":"49_CR28","doi-asserted-by":"crossref","first-page":"181","DOI":"10.5802\/aif.855","volume":"31","author":"J. Peyri\u00e9re","year":"1981","unstructured":"J. Peyri\u00e9re. Processus de naissance avec int\u00e9raction des voisins, \u00e9volution de graphes. Ann. Inst. Fourier, Grenoble, 31(4):181\u2013218, 1981.","journal-title":"Ann. Inst. Fourier, Grenoble"},{"key":"49_CR29","first-page":"41","volume":"47","author":"J. Peyri\u00e9re","year":"1986","unstructured":"J. Peyri\u00e9re. Frequency of patterns in certain graphs and in Penrose tilings. Journal de Physique, 47:41\u201361, 1986.","journal-title":"Journal de Physique"},{"key":"49_CR30","first-page":"343","volume":"23","author":"N. Robertson","year":"1984","unstructured":"N. Robertson and P. Seymour. Some New Results on the Well-Quasi Ordering of Graphs. Annals of Dicrete Math., 23:343\u2013354, 1984.","journal-title":"Annals of Dicrete Math."},{"key":"49_CR31","doi-asserted-by":"crossref","unstructured":"G. Rozenberg. Handbook of Graph Grammars and Computing by Graph Transformation, volume1. World Scientific, 1997.","DOI":"10.1142\/3303"},{"key":"49_CR32","unstructured":"G. Rozenberg and A. Salomaa. The Mathematical Theory of L-Systems. Academic Press, 1980."},{"key":"49_CR33","first-page":"16","volume":"28","author":"G. S\u00e9nizergues","year":"1992","unstructured":"G. S\u00e9nizergues. Definability in weak monadic second-order logic of some infinite graphs. In Dagstuhl seminar on Automata theory: Infinite computations. Wadern, Germany, volume 28, pages 16\u201316, 1992.","journal-title":"Dagstuhl seminar on Automata theory: Infinite computations. Wadern, Germany"},{"key":"49_CR34","doi-asserted-by":"crossref","unstructured":"G. S\u00e9nizergues. An effective version of Stallings\u2019 theorem in the case of context-free groups. In ICALP\u201993, pages 478\u2013495. Lect. Notes Comp. Sci. 700, 1993.","DOI":"10.1007\/3-540-56939-1_96"},{"key":"49_CR35","doi-asserted-by":"publisher","first-page":"312","DOI":"10.2307\/1970577","volume":"88","author":"J.R. Stallings","year":"1968","unstructured":"J.R. Stallings. On torsion-free groups with infinitely many ends. Ann. of Math., 88:312\u2013334, 1968.","journal-title":"Ann. of Math."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44612-5_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T18:41:21Z","timestamp":1556390481000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44612-5_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679011","9783540446125"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/3-540-44612-5_49","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}