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

https://hal.inria.fr/hal-02497078
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

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

15