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.