🚀 go-pugleaf

Lecture Announcement
--------------------


HOWARD BLAIR
============
(Syracuse University, New York)


Logic Programming and Degrees of Computability
----------------------------------------------
Wednesday, September 29, 1993, 16:15


The arithmetic hierarchy, hyperarithmetic sets, and the first
levels of the analytic hierarchy will be discussed using examples 
from logic programming.  Horn, stratified and locally stratified 
programs with various natural properties, together with their 
unique stable models, can be used to define and directly classify 
arithmetic sets, hyperarithmetic sets and some analytic sets.  
A simple two-player game will be presented that can be played in
several equivalent ways by interacting logic program modules.
A correspondence between winning strategies, well-founded
dependencies, constructible ordinals and hyperaritmetic sets
will be exhibited.  From the correspondence a number of
"super-recursive" complexity results can be obtained for logic
program properties in a uniform way.  Simple examples from
logic programming will be used throughout the talk.

----------

HOWARD BLAIR received his PhD from Syracuse University's
School of Computer and Information Science in 1980.  In 1985,
following a period of collaboration with Krzysztof Apt at IBM's 
Thomas J. Watson Research Center at Yorktown Heights in which they
first investigated stratified logic programs, he returned to
Syracuse University as an Associate Professor.  Since 1985 he
has served as a visiting scientist at the Aerospace Corporation, 
and at the Xerox Corporation's Webster Research Center.	 He is
currently a Visiting Senior Fellow of Cornell University's
Mathematical Sciences Institute.

He can be reached by email at: blair@top.cis.syr.edu


Place:
Seminarraum SEM 181A, Instituts fuer Informationssysteme,
Paniglgasse 16, 1040 Wien, 1. Stock (3rd floor).


Kurt-Goedel-Gesellschaft
Technische Universitaet Wien
Institut fuer Computersprachen E185.2
Resselgasse 3/1, A-1040 Wien

Tel: (+43 1) 588 01/4088
Fax: (+43 1) 504 15 89
email: kgs@logic.tuwien.ac.at