|
This article is cited in 10 scientific papers (total in 10 papers)
Degree Spectra of Relations on Boolean Algebras
S. S. Goncharova, R. Downeyb, D. Hirschfeldtc a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
b Victoria University of Wellington, School of Mathematics, Statistics and Computer Science
c University of Chicago
Abstract:
We show that every computable relation on a computable Boolean algebra $\mathfrak B$ is either definable by a quantifier-free formula with constants from $\mathfrak B$ (in which case it is obviously intrinsically computable) or has infinite degree spectrum.
Keywords:
computable Boolean algebra, computable relation, intrinsically computable relation.
Received: 21.11.2000
Citation:
S. S. Goncharov, R. Downey, D. Hirschfeldt, “Degree Spectra of Relations on Boolean Algebras”, Algebra Logika, 42:2 (2003), 182–193; Algebra and Logic, 42:2 (2003), 105–111
Linking options:
https://www.mathnet.ru/eng/al24 https://www.mathnet.ru/eng/al/v42/i2/p182
|
Statistics & downloads: |
Abstract page: | 502 | Full-text PDF : | 136 | References: | 83 | First page: | 1 |
|