Skip to Main content Skip to Navigation
Journal articles

Definable isomorphism problem

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.
Document type :
Journal articles
Complete list of metadata
Contributor : Joanna Ochremiak <>
Submitted on : Tuesday, March 3, 2020 - 2:32:48 PM
Last modification on : Wednesday, March 4, 2020 - 1:34:19 AM

Links full text




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



Record views