## Oracles and First Order Lindström Quantifiers -- A correction to TR # B 94-17


Yachin Pnueli
Institut für Informatik
Freie Universität Berlin
email: pnueli@inf.fu-berlin.de
(joint work with Janos A. Makowski)
Report B 94-19
November 1994

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-94-19.ps.gz

Oracles and First Order Lindström Quantifiers -- A correction to TR # B 94-17 We investigate the tight relationship between oracles and quantifiers. Our main thesis is that for a logic $\cL$ which captures a complexity class $\bC$, by enhancing that logic with a Lindstr\"om quantifier for some set of structures $K$, we get a new logic $\cL[K]$ which captures $\bC^K$ - the class $\bC$ relativized to (using an oracle for) the set $K$. We note however that for this thesis to be correct, we must equate'' the set of {\em transducers} in both the logic and the complexity class. This brings up a second theme that the relationship between the set of transducers and the set of acceptors (in a logic or complexity class) is less obvious than expected.