Logical Approaches to Computational Barriers

Omega Degree Spectra

Speaker:
| Alexandra Soskova |

Slot: |
Array, 12:00-12:20, col. 3 |

We present a notion of a degree spectrum of a structure with respect to countably many sets, based on the notion of omega enumeration reducibility. We prove that some properties of the degree spectrum such as the minimal pair theorem and the existence of quasi-minimal degree are true for the omega degree spectrum.

websites: Arnold Beckmann | 2008-05-18 |