Unary automatic graphs: an algorithmic perspective
| aut.researcher | Liu, Jiamou | |
| dc.contributor.author | Khoussainov, B | |
| dc.contributor.author | Liu, J | |
| dc.contributor.author | Minnes, M | |
| dc.date.accessioned | 2011-11-27T03:48:01Z | |
| dc.date.available | 2011-11-27T03:48:01Z | |
| dc.date.copyright | 2008-04-30 | |
| dc.date.issued | 2008-04-30 | |
| dc.description.abstract | This paper studies infinite graphs produced from a natural unfolding operation applied to finite graphs. Graphs produced via such operations are of finite degree and 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. Hence, we improve on previous work, in which nonelementary or non-uniform algorithms were found | |
| dc.identifier.citation | Theory and Applications of Models of Computation: Proceedings of the 5th international conference on Theory and applications of models of computation (Proceeding TAMC'08), Xi'An, China, vol.4978, pages 542 - 553 | |
| dc.identifier.doi | 10.1007/978-3-540-79228-4_47 | |
| dc.identifier.isbn | 3-540-79227-9 978-3-540-79227-7 | |
| dc.identifier.issn | 0302-9743 (Print) 1611-3349 (Online) | |
| dc.identifier.uri | https://hdl.handle.net/10292/2812 | |
| dc.publisher | Springer-Verlag Berlin, Heidelberg | |
| dc.relation.uri | http://dx.doi.org/10.1007/978-3-540-79228-4_47 | |
| dc.rights | An author may self-archive an author-created version of his/her article on his/her own website and or in his/her institutional repository. He/she may also deposit this version on his/her funder’s or funder’s designated repository at the funder’s request or as a result of a legal obligation, provided it is not made publicly available until 12 months after official publication. He/ she may not use the publisher's PDF version, which is posted on www.springerlink.com, for the purpose of self-archiving or deposit. Furthermore, the author may only post his/her version provided acknowledgement is given to the original source of publication and a link is inserted to the published article on Springer's website. The link must be accompanied by the following text: "The final publication is available at www.springerlink.com”. (Please also see Publisher’s Version and Citation) | |
| dc.rights.accessrights | OpenAccess | |
| dc.title | Unary automatic graphs: an algorithmic perspective | |
| dc.type | Conference Contribution | |
| pubs.organisational-data | /AUT | |
| pubs.organisational-data | /AUT/Design & Creative Technologies | |
| pubs.organisational-data | /AUT/Design & Creative Technologies/School of Computing & Mathematical Science | |
| pubs.organisational-data | /AUT/PBRF Researchers | |
| pubs.organisational-data | /AUT/PBRF Researchers/Design & Creative Technologies PBRF Researchers | |
| pubs.organisational-data | /AUT/PBRF Researchers/Design & Creative Technologies PBRF Researchers/DCT C & M Computing |