RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2009 Volume 48, Number 5, Pages 549–563 (Mi al413)

This article is cited in 21 papers

Computability on linear orderings enriched with predicates

P. E. Alaevab, J. Thurberc, A. N. Frolovd

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia
c Math. Program, Eastern Oregon Univ., La Grande, OR, USA
d N. G. Chebotarev Research Institute of Mathematics and Mechanics, Kazan State University, Kazan, Russia

Abstract: 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,\operatorname{adj})$, where $\operatorname{adj}(x,y)$ is a predicate distinguishing adjacent elements.

Keywords: computability, quasidiscrete linear ordering.

UDC: 510.5+510.6

Received: 17.12.2008


 English version:
Algebra and Logic, 2009, 48:5, 313–320

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024