Frank Stephan: Closed left-r.e. sets

Invitation to the Logic Seminar at the National University of Singapore

Please find below the invitation to the logic seminar. Note that we will
also fix the timetable for the logic seminar in this semester in the first
meeting; in the case that you want to speak but cannot come, please reply
to this email with timings possible for you; you can consult the webpage
of the seminar for possible time-slots.

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Date: Wednesday, 15 January 2013, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Frank Stephan

Title: Closed left-r.e. sets

Abstract:
A set A is called many-one closed left-r.e. iff every set many-one
reducible to A is a left-r.e. set. Similarly one can define the notions
of ascending closed left-r.e. sets, conjunctive closed left-r.e. sets,
disjunctive closed left-r.e. sets and positive closed left-r.e. sets.
The implications r.e. => positive closed left-r.e. =>
many-one closed left-r.e. => ascending closed left-r.e. =>
left-r.e. hold and no arrow can be reversed. Cohesive,
r-cohesive and weakly 1-generic sets are not r.e.
but can be many-one closed left-r.e.; furthermore there is
an ascending closed left-r.e. set which is cohesive and not
many-one closed left-r.e.; however every cohesive left-r.e.
set is also an ascending closed left-r.e. set.
The initial segment complexity of ascending closed left-r.e.
sets is sublinear and can be kept near to linear; for
many-one closed left-r.e. sets, one can obtain such bounds
infinitely often; for conjunctive / disjunctive / positive closed
left-r.e. sets the bound is logarithmic.

This talk reports on joint work with Sanjay Jain and Jason Teutsch
and has been presented at CCR 2013; the results extend those presented
on 24 August 2011 in the logic seminar.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.