Authors: Finkel, Olivier
Todorčević, Stevo 
Title: The isomorphism relation between tree-automatic Structures
Journal: Central European Journal of Mathematics
Volume: 8
Issue: 2
First page: 299
Last page: 313
Issue Date: 1-Apr-2010
Rank: M22
ISSN: 1895-1074
DOI: 10.2478/s11533-010-0014-7
Abstract: 
An ω-tree-automatic structure is a relational structure whose domain and relations are accepted by Muller or Rabin tree automata. We investigate in this paper the isomorphism problem for ω-tree-automatic structures. We prove first that the isomorphism relation for ω-tree-automatic boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups, nilpotent groups of class n ≥ 2) is not determined by the axiomatic system ZFC. Then we prove that the isomorphism problem for ω-tree-automatic boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups, nilpotent groups of class n ≥ 2) is neither a Σ21-set nor a Π21-set.
Keywords: ω-tree-automatic structures | Boolean algebras | Groups | Independence results | Isomorphism relation | Models of set theory | Partial orders | Rings
Publisher: Springer Link

Show full item record

SCOPUSTM   
Citations

6
checked on Jan 30, 2023

Page view(s)

16
checked on Jan 31, 2023

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.