next up previous
Next: Notations and Assumptions Up: Introduction Previous: Results


In the next section we introduce the notation and the assumptions that we adopt in this work. In Section 3 (Compilability) we briefly recall some notions on non-uniform computation that are important for what follows and we recall the basic definitions of compilability classes [6]. In Section 4 (Reductions) we describe the constraints we impose on reductions, while in Section 5 (Space Efficiency) we introduce our compactness classes. In Section 6 (Applications) we actually compare many known PKR formalisms using our framework. Finally, in Section 7 (Related Work and Conclusions) we compare our work with other proposals presented in the literature and draw some conclusions.

Paolo Liberatore