Analysing complexity in classes of unary automatic structures

Simple item page
aut.researcherLiu, Jiamou
dc.contributor.authorLiu, J
dc.contributor.authorMinnes, M
dc.contributor.editorDediu, A
dc.contributor.editorIonescu, A
dc.contributor.editorMartin-Vide, C
dc.date.accessioned2011-11-27T03:38:00Z
dc.date.available2011-11-27T03:38:00Z
dc.date.copyright2009-04
dc.date.issued2009-04
dc.description.abstractThis paper addresses the time complexity of several queries (including membership and isomorphism) in classes of unary automatic structures and the state complexity of describing these classes. We focus on unary automatic equivalence relations, linear orders, trees, and graphs with finite degree. We prove that in various senses, the complexity of these classes is low: (1) For the isomorphism problem, we either greatly improve known algorithms (reducing highly exponential bounds to small polynomials) or answer open questions about the existence of a decision procedure; (2) for state complexity, we provide polynomial bounds with respect to natural measures of the sizes of the structures.
dc.format.mediumPaper and online
dc.identifier.citationLecture Notes in Computer Science: proceedings from the Language and Automata Theory and Applications 3rd International Conference (LATA'09), Tarragona, Spain, vol.5457, pp. 518 - 529
dc.identifier.doi10.1007/978-3-642-00982-2_44
dc.identifier.isbn978-3-642-00981-5
dc.identifier.issn0302-9743 (Print) 1611-3349 (Online)
dc.identifier.urihttps://hdl.handle.net/10292/2810
dc.publisherSpringer Berlin / Heidelberg
dc.relation.urihttp://dx.doi.org/10.1007/978-3-642-00982-2_44
dc.rightsAn 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.accessrightsOpenAccess
dc.titleAnalysing complexity in classes of unary automatic structures
dc.typeConference 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
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
lata09final.pdf
Size:
251.26 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