Computability on linear orderings enriched with predicates. (English. Russian original) Zbl 1241.03055
Algebra Logic 48, No. 5, 313-320 (2009); translation from Algebra Logika 48, No. 5, 549-563 (2009).
Summary: Let \(L\) be a quasidiscrete linear ordering. We specify some conditions for the existence of a
computable presentation for \(L\) or for the structure \((L, \mathrm {adj})\), where \(\mathrm {adj}(x, y)\) is a predicate distinguishing
adjacent elements.
References:
| [1] | R. G. Downey and C. G. Jockush, ”Every low Boolean algebra is isomorphic to a recursive one,” Proc. Am. Math. Soc., 122, No. 3, 871–880 (1994). · Zbl 0820.03019 · doi:10.1090/S0002-9939-1994-1203984-4 |
| [2] | J. J. Thurber, ”Every low 2 Boolean algebra has a recursive copy,” Proc. Am. Math. Soc., 123, No. 12, 3859–3866 (1995). · Zbl 0840.03024 |
| [3] | J. F. Knight and M. Stob, ”Computable Boolean algebras,” J. Symb. Log., 65, No. 4, 1605–1623 (2000). · Zbl 0974.03041 · doi:10.2307/2695066 |
| [4] | A. N. Frolov, ”{\(\Delta\)} 2 0 -copies of linear orderings,” Algebra Logika, 45, No. 3, 354–370 (2006). · Zbl 1115.03047 · doi:10.1007/s10469-006-0017-4 |
| [5] | L. Feiner, ”Hierarchies of Boolean algebras,” J. Symb. Log., 35, No. 3, 365–374 (1971). · Zbl 0222.02048 |
| [6] | R. Watnick, ”A generalization of Tennenbaum’s theorem on effectively finite recursive linear orderings,” J. Symb. Log., 49, No. 2, 563–569 (1984). · Zbl 0585.03015 · doi:10.2307/2274189 |
| [7] | C. J. Ash, C. Jockusch, and J. F. Knight, ”Jumps of orderings,” Trans. Am. Math. Soc., 319, No. 2, 573–599 (1990). · Zbl 0705.03022 · doi:10.1090/S0002-9947-1990-0955487-0 |
| [8] | C. J. Ash, ”A construction for recursive linear orderings,” J. Symb. Log., 56, No. 2, 673–683 (1991). · Zbl 0742.03013 · doi:10.2307/2274709 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
