Artykuł w czasopiśmie
Brak miniatury
Licencja

CC-BYCC-BY - Uznanie autorstwa

Definable isomorphism problem

Autor
Lasota, Sławomir
Keshvardoost, Khadijeh
Ochremiak, Joanna
Klin, Bartosz
Toruńczyk, Szymon
Data publikacji
2019
Abstrakt (EN)

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

Dyscyplina PBN
informatyka
Czasopismo
Logical Methods in Computer Science
Tom
15
Zeszyt
4
Strony od-do
14:1–14:19
ISSN
1860-5974
Data udostępnienia w otwartym dostępie
2019-12-11
Licencja otwartego dostępu
Uznanie autorstwa