The isomorphism problem on classes of automatic structures

Simple item page
aut.researcherLiu, Jiamou
dc.contributor.authorKuske, D
dc.contributor.authorLiu, J
dc.contributor.authorLohrey, M
dc.date.accessioned2011-11-27T03:22:29Z
dc.date.available2011-11-27T03:22:29Z
dc.date.copyright2010-07-11
dc.date.issued2010-07-11
dc.description.abstractSeveral new undecidability results on isomorphism problems for automatic structures are shown: (i) The isomorphism problem for automatic equivalence relations is \Pi^0_1-complete, (ii) The isomorphism problem for automatic trees of height n≥2 is \Pi^0_{2n-3}-complete, (iii) The isomorphism problem for automatic linear orders is not arithmetical.
dc.format.mediumPaper and online
dc.identifier.citationPresentation at the 25th annual IEEE symposium on logic in computer science (LICS'10), Edinburgh, UK, pp. 160 - 169
dc.identifier.doi10.1109/LICS.2010.10
dc.identifier.isbn978-0-7695-4114-3
dc.identifier.issn1043-6871
dc.identifier.urihttps://hdl.handle.net/10292/2808
dc.publisherIEEE Computer Society
dc.relation.isreplacedby10292/3350
dc.relation.isreplacedbyhttp://hdl.handle.net/10292/3350
dc.relation.urihttp://dx.doi.org/10.1109/LICS.2010.10
dc.rightsCopyright © 2010 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
dc.rights.accessrightsOpenAccess
dc.subjectArithmetical hierarchy
dc.subjectAutomatic structures
dc.subjectIsomorphism problems
dc.subjectAutomata
dc.subjectBoolean algebra
dc.subjectConstruction industry
dc.subjectHuman computer interaction
dc.subjectPediatrics
dc.subjectSilicon
dc.subjectTerminology
dc.titleThe isomorphism problem on classes of 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:
lics.pdf
Size:
150.26 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
School of Engineering, Computer and Mathematical Sciences - Te Kura Mātai Pūhanga, Rorohiko, Pāngarau