Queries and Algorithms Computable by Polynomial Time Existential Reflective Machines

1 January 1997

journal article
Published by SAGE Publications in Fundamenta Informaticae

Vol. 32 (1) , 91-105
https://doi.org/10.3233/fi-1997-32104

Abstract

We consider two kinds of reflective relational machines: the usual ones, which use first order queries, and existential reflective machines, which use only first order existential queries. We compare these two computation models. We build on already existing results for standard relational machines, obtained by Abiteboul, Pa-padimitriou and Vianu [2], so we prove only results for existential machines. First we show that for both standard and existential reflective machines the set of polynomial time computable Boolean queries consists precisely of all 𝒫𝒮𝒫𝒜𝒞ℰ computable queries. Then we go further and compare which classes of algorithms both kinds of machines represent. Unless 𝒫𝒮𝒫𝒜𝒞ℰ = 𝒫

Keywords

This publication has 0 references indexed in Scilit: