Definable isomorphism problem - Archive ouverte HAL Access content directly
Journal Articles Logical Methods in Computer Science Year : 2019

Definable isomorphism problem

(1) , (2) , (2) , (3, 4) , (2)
1
2
3
4

Abstract

We investigate the isomorphism problem in the setting of definable sets (equivalent to sets with atoms): given two definable relational structures, are they related by a definable isomorphism? Under mild assumptions on the underlying structure of atoms, we prove decidability of the problem. The core result is parameter-elimination: existence of an isomorphism definable with parameters implies existence of an isomorphism definable without parameters.

Dates and versions

hal-02497078 , version 1 (03-03-2020)

Identifiers

Cite

Khadijeh Keshvardoost, Bartek Klin, Sławomir Lasota, Joanna Ochremiak, Szymon Toruńczyk. Definable isomorphism problem. Logical Methods in Computer Science, 2019, ⟨10.23638/LMCS-15(4:14)2019⟩. ⟨hal-02497078⟩

Collections

CNRS
8 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More