{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,12]],"date-time":"2024-08-12T18:35:00Z","timestamp":1723487700672},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2009,2,1]],"date-time":"2009-02-01T00:00:00Z","timestamp":1233446400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2009,2]]},"abstract":"<jats:p>This paper studies infinite graphs produced from a natural unfolding operation applied to finite graphs. Graphs produced using such operations are of finite degree and automatic over the unary alphabet (that is, they can be described by finite automata over the unary alphabet). We investigate algorithmic properties of such unfolded graphs given their finite presentations. In particular, we ask whether a given node belongs to an infinite component, whether two given nodes in the graph are reachable from one another and whether the graph is connected. We give polynomial-time algorithms for each of these questions. For a fixed input graph, the algorithm for the first question is in constant time and the second question is decided using an automaton that recognises the reachability relation in a uniform way. Hence, we improve on previous work, in which non-elementary or non-uniform algorithms were found.<\/jats:p>","DOI":"10.1017\/s0960129508007342","type":"journal-article","created":{"date-parts":[[2009,2,20]],"date-time":"2009-02-20T20:49:19Z","timestamp":1235162959000},"page":"133-152","source":"Crossref","is-referenced-by-count":6,"title":["Unary automatic graphs: an algorithmic perspective"],"prefix":"10.1017","volume":"19","author":[{"given":"BAKHADYR","family":"KHOUSSAINOV","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JIAMOU","family":"LIU","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MIA","family":"MINNES","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,2,1]]},"reference":[{"key":"S0960129508007342_ref9","unstructured":"Khoussainov B. and Minnes M. (2008) Automatic structures and their complexity (extended abstract). In: Proc. TAMC'08. Springer-Verlag Lecture Notes in Computer Science (to appear)."},{"key":"S0960129508007342_ref7","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"S0960129508007342_ref12","first-page":"467","article-title":"Graphs with automatic presentations over a unary alphabet","volume":"6","author":"Khoussainov","year":"2001","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"S0960129508007342_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_57"},{"key":"S0960129508007342_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/10722167_20"},{"key":"S0960129508007342_ref1","unstructured":"Blumensath A. (1999) Automatic Structures, Diploma Thesis, RWTH Aachen."},{"key":"S0960129508007342_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/1094622.1094625"},{"key":"S0960129508007342_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63141-0_10"},{"key":"S0960129508007342_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60178-3_93"},{"key":"S0960129508007342_ref18","unstructured":"Rubin S. (2004) Automatic Structures, Ph.D. Thesis, University of Auckland."},{"key":"S0960129508007342_ref8","unstructured":"Hodgson B. R. (1976) Th\u00e9ories d\u00e9cidables par automate fini., Ph.D. thesis, University of Montr\u00e9al."},{"key":"S0960129508007342_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46011-X_10"},{"key":"S0960129508007342_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1133-y"},{"key":"S0960129508007342_ref4","first-page":"1","volume-title":"Proc. International Congress on Logic, Methodology and Philosophy of Science","author":"B\u00fcchi","year":"1960"},{"key":"S0960129508007342_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45687-2_13"},{"key":"S0960129508007342_ref11","doi-asserted-by":"crossref","unstructured":"Khoussainov B. , Nies A. , Rubin S. and Stephan F. (2004) Automatic structures: richness and limitations. In: Proc. 19th LICS 44\u201353.","DOI":"10.1109\/LICS.2004.1319599"},{"key":"S0960129508007342_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1"},{"key":"S0960129508007342_ref15","first-page":"344","article-title":"Automatic structures of bounded degree","volume":"2850","author":"Lohrey","year":"2003","journal-title":"Springer-Verlag Lecture Notes in Artificial Intelligence"},{"key":"S0960129508007342_ref17","first-page":"1","article-title":"Decidability of second-order theories and automata on infinite trees","volume":"141","author":"Rabin","year":"1969","journal-title":"Trans. Amer. Math. Soc."},{"key":"S0960129508007342_ref20","doi-asserted-by":"crossref","unstructured":"W\u00f6hrle S. and Thomas W. (2004) Model Checking Synchronized Products of Infinite Transition Systems. In Proc. 19th Annual IEEE Symposium on Logic in Computer Science (LICS'04) 2\u201311.","DOI":"10.1109\/LICS.2004.1319595"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129508007342","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,3]],"date-time":"2019-04-03T20:21:04Z","timestamp":1554322864000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129508007342\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,2]]}},"alternative-id":["S0960129508007342"],"URL":"https:\/\/doi.org\/10.1017\/s0960129508007342","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2]]}}}