DocumentCode :
2049195
Title :
The Isomorphism Problem on Classes of Automatic Structures
Author :
Kuske, Dietrich ; Liu, Jiamou ; Lohrey, Markus
Author_Institution :
LaBRI, Univ. Bordeaux I, Bordeaux, France
fYear :
2010
fDate :
11-14 July 2010
Firstpage :
160
Lastpage :
169
Abstract :
Several new undecidability results on isomorphism problems for automatic structures are shown: (i) The isomorphism problem for automatic equivalence relations is Π10 -complete, (ii) The isomorphism problem for automatic trees of height n ≥ 2 is Π2n-30 -complete, (iii) The isomorphism problem for automatic linear orders is not arithmetical.
Keywords :
automata theory; equivalence classes; trees (mathematics); automatic equivalence relations; automatic structures; automatic trees; isomorphism problem; Automata; Boolean algebra; Construction industry; Human computer interaction; Pediatrics; Silicon; Terminology; arithmetical hierarchy; automatic structures; isomorphism problems;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Logic in Computer Science (LICS), 2010 25th Annual IEEE Symposium on
Conference_Location :
Edinburgh
ISSN :
1043-6871
Print_ISBN :
978-1-4244-7588-9
Electronic_ISBN :
1043-6871
Type :
conf
DOI :
10.1109/LICS.2010.10
Filename :
5570886
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2049195
بازگشت