Show simple item record

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.issued2011-11-27
dc.identifier.citationPresentation at the 25th annual IEEE symposium on logic in computer science (LICS'10), Edinburgh, UK, pp. 160 - 169
dc.identifier.isbn978-0-7695-4114-3
dc.identifier.issn1043-6871
dc.identifier.urihttp://hdl.handle.net/10292/2808
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.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.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
dc.rights.accessrightsOpenAccess
dc.identifier.doi10.1109/LICS.2010.10


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record