𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Computable categoricity and the Ershov hierarchy

✍ Scribed by Bakhadyr Khoussainov; Frank Stephan; Yue Yang

Publisher
Elsevier Science
Year
2008
Tongue
English
Weight
666 KB
Volume
156
Category
Article
ISSN
0168-0072

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On Genericity and Ershov's Hierarchy
On Genericity and Ershov's Hierarchy
✍ Amy Gale; Rod Downey πŸ“‚ Article πŸ“… 2001 πŸ› John Wiley and Sons 🌐 English βš– 281 KB
Recursive Structures and Ershov's Hierar
Recursive Structures and Ershov's Hierarchy
✍ Christopher J. Ash; Julia F. Knight πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 460 KB

Ash and Nerode [2] gave natural definability conditions under which a relation is intrinsically r.e. Here we generalize this to arbitrary levels in Ershov's hierarchy of A: sets, giving conditions under which a relation is intrinsically a-r. e.

On the complexity of categoricity in com
On the complexity of categoricity in computable structures
✍ Walker M. White πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 192 KB

## Abstract We investigate the computational complexity the class of Γ‐categorical computable structures. We show that hyperarithmetic categoricity is Ξ ^1^~1~‐complete, while computable categoricity is Ξ ^0^~4~‐hard. (Β© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)