Khadijeh Keshvardoost ; Bartek Klin ; Sławomir Lasota ; Joanna Ochremiak ; Szymon Toruńczyk - Definable isomorphism problem

lmcs:4321 - Logical Methods in Computer Science, December 11, 2019, Volume 15, Issue 4 - https://doi.org/10.23638/LMCS-15(4:14)2019
Definable isomorphism problemArticle

Authors: Khadijeh Keshvardoost ; Bartek Klin ; Sławomir Lasota ; Joanna Ochremiak ; Szymon Toruńczyk

    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.


    Volume: Volume 15, Issue 4
    Published on: December 11, 2019
    Accepted on: November 11, 2019
    Submitted on: February 27, 2018
    Keywords: Computer Science - Logic in Computer Science
    Funding:
      Source : OpenAIRE Graph
    • A unified theory of finite-state recognisability; Funder: European Commission; Code: 683080

    Consultation statistics

    This page has been seen 1829 times.
    This article's PDF has been downloaded 277 times.