Geodesic
On the existential interpretability of structures
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 11 (2014), pp. 557-566

Voir la notice de l'article provenant de la source Math-Net.Ru

We introduce and study the notion of $\exists$-interpretability of constructive algebraic structures. It is shown that any finite partially ordered set is embeddable into the semilattice this interpretability generates; we also prove the existence of universal computable structures. As an application of this concept, we consider the transformations of abstract databases and their queries in case when one data structure is $\exists$-interpretable in another one.
Keywords: existential interpretability, definability, computable structure, semilattice.
Mots-clés : constructive structure 
A. S. Morozov; A. Zh. Satekbaeva; D. A. Tussupov. On the existential interpretability of structures. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 11 (2014), pp. 557-566. http://geodesic.mathdoc.fr/item/SEMR_2014_11_a17/
@article{SEMR_2014_11_a17,
     author = {A. S. Morozov and A. Zh. Satekbaeva and D. A. Tussupov},
     title = {On the existential interpretability of structures},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {557--566},
     year = {2014},
     volume = {11},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2014_11_a17/}
}
TY  - JOUR
AU  - A. S. Morozov
AU  - A. Zh. Satekbaeva
AU  - D. A. Tussupov
TI  - On the existential interpretability of structures
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2014
SP  - 557
EP  - 566
VL  - 11
UR  - http://geodesic.mathdoc.fr/item/SEMR_2014_11_a17/
LA  - en
ID  - SEMR_2014_11_a17
ER  - 
%0 Journal Article
%A A. S. Morozov
%A A. Zh. Satekbaeva
%A D. A. Tussupov
%T On the existential interpretability of structures
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2014
%P 557-566
%V 11
%U http://geodesic.mathdoc.fr/item/SEMR_2014_11_a17/
%G en
%F SEMR_2014_11_a17

[1] A. A. Mučnik, “Solution of Post's reduction problem and of certain other problems in the theory of algorithms”, Trudy Moskov. Mat. Obšč., 7, 1958, 391–405 (Russian) | MR

[2] Ju. V. Matijasevič, “Enumerable sets are Diophantine”, Soviet Math. Doklady, 11:20 (1970), 354–357

[3] Yu. L. Ershov, Decidability Problems and Constructive Models, Nauka, M., 1980 (Russian) | MR

[4] Yu. L. Ershov, “$\Sigma$–{D}efinabiility of algebraic systems”, Handbook of Recursive Mathematics, (Recursive Model Theory), Studies in Logic and Foundations of Mathematics, 1, Elsevier, Amsterdam–Lausanne–New York–Oxford–Shannon–Singapore–Tokyo, 1998, 235–260 | DOI | MR | Zbl