Definable isomorphism problem Article Swipe

View

Related Concepts

Isomorphism (crystallography) Decidability Mathematics Core (optical fiber) Isomorphism extension theorem Combinatorics Subgraph isomorphism problem Discrete mathematics Pure mathematics Computer science Crystal structure Crystallography Chemistry Telecommunications Picard–Lindelöf theorem Fixed-point theorem Graph

Khadijeh Keshvardoost , Bartek Klin , Sławomir Lasota , Joanna Ochremiak , Szymon Toruńczyk ·

YOU? · · 2019 · Open Access · · DOI: https://doi.org/10.23638/lmcs-15(4:14)2019 · OA: W2789092302

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.

Definable isomorphism problem Article Swipe

Related Topics