✦ LIBER ✦

Bounding computably enumerable degrees in the Ershov hierarchy

✍ Scribed by Angsheng Li; Guohua Wu; Yue Yang

Publisher: Elsevier Science
Year: 2006
Tongue: English
Weight: 219 KB
Volume: 141
Category: Article
ISSN: 0168-0072
DOI: 10.1016/j.apal.2005.10.004

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Interpreting N in the computably enumera

Interpreting N in the computably enumerable weak truth table degrees

✍ André Nies 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 129 KB

We give a ÿrst-order coding without parameters of a copy of (N; +; ×) in the computably enumerable weak truth table degrees. As a tool, we develop a theory of parameter deÿnable subsets.

Undecidability and 1-types in intervals

Undecidability and 1-types in intervals of the computably enumerable degrees

✍ Klaus Ambos-Spies; Denis R. Hirschfeldt; Richard A. Shore 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 338 KB

We show that the theory of the partial ordering of the computably enumerable degrees in any given nontrivial interval is undecidable and has uncountably many 1-types.

Computable categoricity and the Ershov h

Computable categoricity and the Ershov hierarchy

✍ Bakhadyr Khoussainov; Frank Stephan; Yue Yang 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 666 KB

A necessary and sufficient condition for

A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees

✍ M. Lerman 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 176 KB

We present a necessary and su cient condition for the embeddability of a principally decomposable ÿnite lattice into the computably enumerable degrees. This improves a previous result which required that, in addition, the lattice be ranked. The same condition is also necessary and su cient for a ÿni

A necessary and sufficient condition for

A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees preserving greatest element

✍ Burkhard Englert 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 196 KB

We present a necessary and su cient condition for the embeddability of a ÿnite principally decomposable lattice into the computably enumerable degrees preserving greatest element.

Bounding queries in the analytic polynom

Bounding queries in the analytic polynomial-time hierarchy

✍ Herbert Baier; Klaus W. Wagner 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 1004 KB

In a previous paper the present authors (Baier and Wagner, 1996) investigated an S-V-hierarchy over P using word quantifiers as well as two types of set quantifiers, the so-called analytic polynomial-time hierarchy. The fact that some constructions there result in a bounded number of oracle queries