{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T05:36:38Z","timestamp":1648532198244},"reference-count":39,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[2003,11,1]],"date-time":"2003-11-01T00:00:00Z","timestamp":1067644800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3582,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2003,11]]},"DOI":"10.1016\/s0022-0000(03)00065-5","type":"journal-article","created":{"date-parts":[[2003,6,30]],"date-time":"2003-06-30T13:57:28Z","timestamp":1056981448000},"page":"497-545","source":"Crossref","is-referenced-by-count":2,"title":["Automatic graphs and D0L-sequences of finite graphs"],"prefix":"10.1016","volume":"67","author":[{"given":"Olivier","family":"Ly","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(03)00065-5_BIB1","series-title":"Riemann Surfaces","author":"Ahlfors","year":"1960"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB2","unstructured":"F. Berman, Edge grammars and parallel computation, in: Proceedings of the 21st Annual Allerton Conference on Communication, Control and Computing, Monticello, IL, 1983, pp. 214\u2013223."},{"key":"10.1016\/S0022-0000(03)00065-5_BIB3","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0020-0255(93)90080-6","article-title":"Representing graph families with edge grammars","volume":"70","author":"Berman","year":"1993","journal-title":"Inf. Sci."},{"key":"10.1016\/S0022-0000(03)00065-5_BIB4","doi-asserted-by":"crossref","unstructured":"A. Blumensath, E. Gr\u00e4del, Automatic structures, in: Proceedings of 15th IEEE Symposium on Logic in Computer Science LICS 2000, Santa Barbara, CA, 2000, pp. 51\u201362.","DOI":"10.1109\/LICS.2000.855755"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB5","series-title":"A Graphic Apology for Symmetry and Implicitness","author":"Carbone","year":"2000"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB6","doi-asserted-by":"crossref","unstructured":"D. Caucal, On infinite transition graphs having decidable monadic theory, in: ICALP\u201996-LNCS, Vol. 1099, Springer, New York-Berlin, 1996, pp. 194\u2013205.","DOI":"10.1007\/3-540-61440-0_128"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB7","unstructured":"A.D.M. Clow, Ends of groups\u2014a computational approach, Ph.D. Thesis, Warwick University, UK, 2000."},{"key":"10.1016\/S0022-0000(03)00065-5_BIB8","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF02088013","article-title":"The monadic second-order logic of graphs II","volume":"21","author":"Courcelle","year":"1989","journal-title":"Math. Syst. Theory"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB9","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0168-0072(90)90027-Y","article-title":"The monadic second-order logic of graphs IV","volume":"49","author":"Courcelle","year":"1990","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB10","doi-asserted-by":"crossref","unstructured":"B. Courcelle, The expression of graph properties and graph transformations in monadic second-order logic, in: G. Rozenberg (Ed.), Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 1, World Scientific, Singapore, 1997.","DOI":"10.1142\/9789812384720_0005"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB11","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","article-title":"Handle rewriting hypergraph grammars","volume":"46","author":"Courcelle","year":"1993","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0022-0000(03)00065-5_BIB12","doi-asserted-by":"crossref","unstructured":"M. De Does, A. Lindenmayer, Algorithms for the generation and drawing of maps representing cell clones, in: GGACS\u201982, LNCS, Vol. 153, Springer, Berlin, 1982, pp. 39\u201357.","DOI":"10.1007\/BFb0000098"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB13","article-title":"Groups acting on graphs","volume":"Vol. 17","author":"Dicks","year":"1989"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB14","doi-asserted-by":"crossref","unstructured":"F. Drewes, H.-J. Kreowski, A. Habel, Hyperedge replacement graph grammars, in: G. Rozenberg (Ed.), Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 1, World Scientific, Singapore, 1997, pp. 95\u2013162.","DOI":"10.1142\/9789812384720_0002"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB15","doi-asserted-by":"crossref","unstructured":"J. Engelfriet, G. Rozenberg, Node replacement graph grammars, in: G. Rozenberg (Ed.), Handbook of Graph Grammars and Computing by Graph Transformation, Vol. 1, World Scientific, Singapore, 1997, pp. 1\u201394.","DOI":"10.1142\/9789812384720_0001"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB16","series-title":"Word Processing in Groups","author":"Epstein","year":"1992"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB17","unstructured":"V. Gerasimov, Detecting connectedness of the boundary of a hyperbolic group, 1999, Preprint."},{"key":"10.1016\/S0022-0000(03)00065-5_BIB18","article-title":"Sur les groupes hyperboliques d'apr\u00e8s Mikhael Gromov","volume":"Vol. 83","author":"Ghys","year":"1990"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB19","series-title":"Model Theoretic Logic","first-page":"479","article-title":"Monadic second-order theories","author":"Gurevich","year":"1985"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB20","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF01362670","article-title":"\u00dcber unendliche wege in graphen","volume":"157","author":"Halin","year":"1964","journal-title":"Math. Ann."},{"key":"10.1016\/S0022-0000(03)00065-5_BIB21","doi-asserted-by":"crossref","first-page":"219","DOI":"10.2307\/2269811","article-title":"The undecidability of the turing machine immortality problem","volume":"31","author":"Hooper","year":"1966","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB22","series-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft","year":"1979"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB23","doi-asserted-by":"crossref","unstructured":"B. Khoussainov, A. Nerode, Automatic presentations of structures, in: Logic and Computational Complexity (Indianapolis, IN, 1994), Vol. 960, Lecture Notes in Computer Science, Springer, Berlin, 1995, pp. 367\u2013392.","DOI":"10.1007\/3-540-60178-3_93"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB24","doi-asserted-by":"crossref","unstructured":"A. Lindenmayer, An introduction to parallel map generating systems, in: GGACS\u201986, LNCS, Vol. 291, Springer, Berlin, 1986, pp. 27\u201340.","DOI":"10.1007\/3-540-18771-5_42"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB25","doi-asserted-by":"crossref","unstructured":"A. Lindenmayer, G. Rozenberg, Parallel generation of maps: developmental systems for cell layers, in: GGACS\u201978, LNCS, Vol. 73, Springer, Berlin, 1978, pp. 301\u2013316.","DOI":"10.1007\/BFb0025728"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB26","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1090\/conm\/250\/03847","article-title":"On effective decidability of the homeomorphism problem for non-compact surfaces","volume":"250","author":"Ly","year":"1999","journal-title":"Contemp. Math.Amer. Math. Soc."},{"key":"10.1016\/S0022-0000(03)00065-5_BIB27","series-title":"MFCS\u20192000","first-page":"539","article-title":"Automatic graphs and graph D0L-systems","volume":"Vol. 1893","author":"Ly","year":"2000"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB28","article-title":"Algebraic topology: an introduction","volume":"Vol. 56","author":"Massey","year":"1967"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB29","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0304-3975(85)90087-8","article-title":"The theory of ends, pushdown automata, and second-order logic","volume":"37","author":"Muller","year":"1985","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0022-0000(03)00065-5_BIB30","series-title":"Computational Complexity","author":"Papadimitriou","year":"1994"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB31","unstructured":"L. Pelecq, Isomorphismes et automorphismes des graphes context-free, \u00e9quationnels et automatiques, Ph.D. Thesis, Bordeaux I, 1997."},{"key":"10.1016\/S0022-0000(03)00065-5_BIB32","first-page":"343","article-title":"Some new results on the well-quasi ordering of graphs","volume":"23","author":"Robertson","year":"1984","journal-title":"Ann. Discrete Math."},{"key":"10.1016\/S0022-0000(03)00065-5_BIB33","series-title":"Development in Language Theory","first-page":"438","article-title":"Parallel BNLC graph grammars","author":"R\u00f6der","year":"1994"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB34","series-title":"Theory of Recursive Functions and Effective Computability, Series in Higher Mathematics","author":"Rogers","year":"1967"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB35","series-title":"The Mathematical Theory of L-Systems","author":"Rozenberg","year":"1980"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB36","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/S0019-9958(86)80045-6","article-title":"Boundary nlc graph grammars","volume":"69","author":"Rozenberg","year":"1986","journal-title":"Inform. Control"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB37","unstructured":"G. S\u00e9nizergues, Definability in weak monadic second-order logic of some infinite graphs, in: K. Compton, J.E. Pin, W. Thomas (Eds.), Dagstuhl Seminar on Automata Theory: Infinite Computations, Vol. 28, Wadern, Germany, 1992, pp. 16\u201316."},{"key":"10.1016\/S0022-0000(03)00065-5_BIB38","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, LNCS, Vol. 700, Springer, Berlin, 1993, pp. 478\u2013495.","DOI":"10.1007\/3-540-56939-1_96"},{"key":"10.1016\/S0022-0000(03)00065-5_BIB39","doi-asserted-by":"crossref","first-page":"312","DOI":"10.2307\/1970577","article-title":"On torsion-free groups with infinitely many ends","volume":"88","author":"Stallings","year":"1968","journal-title":"Ann. Math."}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000655?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000003000655?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,24]],"date-time":"2020-03-24T06:31:11Z","timestamp":1585031471000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000003000655"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,11]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2003,11]]}},"alternative-id":["S0022000003000655"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(03)00065-5","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2003,11]]}}}