ACM/IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Ninth Annual IEEE Symposium on

Logic in Computer Science (LICS 1994)

Paper: The power of reflective relational machines (at LICS 1994)

Authors: Serge Abiteboul Christos H. Papadimitriou Victor Vianu


A model of database programming with reflection, called reflective relational machine, is introduced and studied. The reflection consists here of dynamic generation of queries in a host programming language. The main results characterize the power of the machine in terms of known complexity classes. In particular, the polynomial-time restriction of the machine is shown to express PSPACE, and to correspond precisely to uniform circuits of polynomial depth and exponential size. This provides an alternative, logic-based formulation of the uniform circuit model, more convenient for problems naturally formulated in logic terms. Since time in the polynomially-bounded machine coincides with time in the uniform circuit model, this also shows that reflection allows for more “intense” parallelism, which is not attainable otherwise (unless P=PSPACE). Other results concern the power of the reflective relational machine subject to restrictions on the number of variables used


    author = 	 {Serge Abiteboul and Christos H. Papadimitriou and Victor Vianu},
    title = 	 {The power of reflective relational machines},
    booktitle =  {Proceedings of the Ninth Annual IEEE Symposium on Logic in Computer Science (LICS 1994)},
    year =	 {1994},
    month =	 {July}, 
    pages =      {230--240},
    location =   {Paris, France}, 
    publisher =	 {IEEE Computer Society Press}

Last modified: 2021-04-0120:36
Sam Staton