|
This article is cited in 4 scientific papers (total in 4 papers)
The computable embedding problem
J. Carson, E. Fokinaa, V. S. Harizanovb, J. F. Knightc, S. Quinnd, C. Safranskie, J. Wallbaum a Kurt Goedel Res. Center Math. Log., Univ. Vienna, Vienna, Austria
b Dep. Math., George Washington Univ., Washington, D.C., USA
c Dep. Math., Univ. Notre Dame, Notre Dame, IN, USA
d Dep. Math., Dominican Univ., , River Forest, IL, USA
e Saint Vincent College, Latrobe, PA, USA
Abstract:
Calvert calculated the complexity of the computable isomorphism problem for a number of familiar classes of structures. Rosendal suggested that it might be interesting to do the same for the computable embedding problem. By the computable isomorphism problem and (computable embedding problem) we mean the difficulty of determining whether there exists an isomorphism (embedding) between two members of a class of computable structures. For some classes, such as the class of $\mathbb Q$-vector spaces and the class of linear orderings, it turns out that the two problems have the same complexity. Moreover, calculations are essentially the same. For other classes, there are differences. We present examples in which the embedding problem is trivial (within the class) and the computable isomorphism problem is more complicated. We also give an example in which the embedding problem is more complicated than the isomorphism problem.
Keywords:
computable structure, computable isomorphism problem, computable embedding problem.
Received: 27.11.2011
Citation:
J. Carson, E. Fokina, V. S. Harizanov, J. F. Knight, S. Quinn, C. Safranski, J. Wallbaum, “The computable embedding problem”, Algebra Logika, 50:6 (2011), 707–732; Algebra and Logic, 50:6 (2012), 478–493
Linking options:
https://www.mathnet.ru/eng/al513 https://www.mathnet.ru/eng/al/v50/i6/p707
|
Statistics & downloads: |
Abstract page: | 298 | Full-text PDF : | 70 | References: | 33 | First page: | 15 |
|