Lecture 13 (20.1.97)
Previous lecture:
Lecture 12 ,
Overview ,
Course home page ,
Material of this and subsequent lectures:
-
1995/TR849
J.A. Makowsky and Y.B. Pnueli:
Logics Capturing Relativized Complexity Classes Uniformly.
17 pp., revised version, March 1995
published in LCC'94, Lecture Notes in Computer Science,
D. Leivant ed.
-
1994/TR820.ps
J.A. Makowsky and Y.B. Pnueli:
Oracles and Quantifiers.
34 pp., May 1994
(Expanded version of TR785, published in CSL'93,
Lecture Notes in Computer Science, vol. 832)
Oracles and Quantifiers
- Two kind of Turing machines: Acceptors and Transducers
- Oracle Turing Machines (OTM)
- Logics capturing transducers.
The theorems of Fagin, Immerman and Vardi can be improved
such as to capture the tranducers.
- Turing reducibility and Oracle Turing Machines
- Capturing Turing reducibility uniformly
- Statement of the theorems of Gottlob and Makowsky-Pnueli
Next lecture:
Lecture 14