Unary automatic graphs: an algorithmic approach

Simple item page
aut.researcherLiu, Jiamou
dc.contributor.authorKhoussainov, B
dc.contributor.authorLiu, J
dc.contributor.authorMinnes, M
dc.date.accessioned2011-11-27T05:24:24Z
dc.date.accessioned2011-11-27T05:27:27Z
dc.date.available2011-11-27T05:24:24Z
dc.date.available2011-11-27T05:27:27Z
dc.date.copyright2009-02
dc.date.issued2009-02
dc.description.abstractThis 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.
dc.format.mediumpaper and online
dc.identifier.citationJournal of Mathematical Structures in Computer Science, vol.19 (1), pp.133 - 152
dc.identifier.doi10.1017/S0960129508007342
dc.identifier.issn0960-1295 (print) 1469-8072 (online)
dc.identifier.urihttps://hdl.handle.net/10292/2817
dc.languageEnglish
dc.publisherCambridge University Press
dc.relation.replaceshttp://hdl.handle.net/10292/2816
dc.relation.replaces10292/2816
dc.relation.urihttp://dx.doi.org/10.1017/S0960129508007342
dc.rightsCopyright © Cambridge University Press, 2009. (http://journals.cambridge.org). Authors retain the right to place his/her pre-publication version of the work on a personal website or institutional repository for non commercial purposes. The definitive version was published in (see Citation). The original publication is available at (see Publisher's Version)
dc.rights.accessrightsOpenAccess
dc.titleUnary automatic graphs: an algorithmic approach
dc.typeJournal Article
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
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
mscs08.pdf
Size:
259.65 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
licence.htm
Size:
29.98 KB
Format:
Unknown data format
Description:
Download
Collections
School of Engineering, Computer and Mathematical Sciences - Te Kura Mātai Pūhanga, Rorohiko, Pāngarau