TY - JOUR

T1 - On recursively enumerable structures

AU - Selivanov, Victor

PY - 1996/4/4

Y1 - 1996/4/4

N2 - We state some general facts on r.e. structures, e.g. we show that the free countable structures in quasivarieties are r.e. and construct acceptable numerations and universal r.e. structures in quasivarieties. The last facts are similar to the existence of acceptable numerations of r.e. sets and creative sets. We state a universality property of the acceptable numerations, classify some index sets and discuss their relation to other decision problems. These results show that the r.e. structures behave in some respects better than the recursive structures.

AB - We state some general facts on r.e. structures, e.g. we show that the free countable structures in quasivarieties are r.e. and construct acceptable numerations and universal r.e. structures in quasivarieties. The last facts are similar to the existence of acceptable numerations of r.e. sets and creative sets. We state a universality property of the acceptable numerations, classify some index sets and discuss their relation to other decision problems. These results show that the r.e. structures behave in some respects better than the recursive structures.

UR - http://www.scopus.com/inward/record.url?scp=0030568393&partnerID=8YFLogxK

U2 - 10.1016/0168-0072(94)00050-6

DO - 10.1016/0168-0072(94)00050-6

M3 - Article

AN - SCOPUS:0030568393

VL - 78

SP - 243

EP - 258

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

SN - 0168-0072

IS - 1-3

ER -