Switch to: References

Add citations

You must login to add citations.
  1. On parallel hierarchies and Rki.Stephen Bloch - 1997 - Annals of Pure and Applied Logic 89 (2-3):231-273.
    This paper defines natural hierarchies of function and relation classes □i,kc and Δi,kc, constructed from parallel complexity classes in a manner analogous to the polynomial-time hierarchy. It is easily shown that □i−1,kp □c,kc □i,kp and similarly for the Δ classes. The class □i,3c coincides with the single-valued functions in Buss et al.'s class , and analogously for other growth rates. Furthermore, the class □i,kc comprises exactly the functions Σi,kb-definable in Ski−1, and if Tki−1 is Σi,kb-conservative over Ski−1, then □i,kp is (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation