References

  1. Bill Allen (1991): Arithmetizing Uniform NC. Ann. Pure Appl. Logic 53(1), pp. 1–50, doi:10.1016/0168-0072(91)90057-S.
  2. Stephen Bellantoni & Stephen A. Cook (1992): A New Recursion-Theoretic Characterization of the Polytime Functions. Computational Complexity 2, pp. 97–110, doi:10.1007/BF01201998.
  3. Stephen A. Bloch (1994): Function-Algebraic Characterizations of Log and Polylog Parallel Time. Computational Complexity 4, pp. 175–205, doi:10.1007/BF01202288.
  4. Guillaume Bonfante, Reinhard Kahle, Jean-Yves Marion & Isabel Oitavem (2016): Two function algebras defining functions in \voidb@x NC^\voidb@x k boolean circuits. Inf. Comput. 248, pp. 82–103, doi:10.1016/j.ic.2015.12.009.
  5. Ashok K. Chandra, Dexter Kozen & Larry J. Stockmeyer (1981): Alternation. J. ACM 28(1), pp. 114–133, doi:10.1145/322234.322243.
  6. P. Clote (1989): Sequential, machine-independent characterizations of the parallel complexity classes \voidb@x ALOGTIME, \voidb@x AC^k, \voidb@x NC^k and \voidb@x NC. Feasible Mathematics, \voidb@x Birkhaüser, 49-69, doi:10.1007/978-1-4612-3466-1_4.
  7. A. Cobham (1962): The intrinsic computational difficulty of functions. In: Y. Bar-Hillel: Proceedings of the International Conference on Logic, Methodology, and Philosophy of Science. North-Holland, Amsterdam, pp. 24–30, doi:10.2307/2270886.
  8. Martin Hofmann (2003): Linear types and non-size-increasing polynomial time computation. Inf. Comput. 183(1), pp. 57–85, doi:10.1016/S0890-5401(03)00009-9.
  9. Martin Hofmann & Ulrich Schöpp (2010): Pure pointer programs with iteration. ACM Trans. Comput. Log. 11(4), pp. 26:1–26:23, doi:10.1145/1805950.1805956.
  10. Satoru Kuroda (2004): Recursion Schemata for Slowly Growing Depth Circuit Classes. Computational Complexity 13(1-2), pp. 69–89, doi:10.1007/s00037-004-0184-4.
  11. Daniel Leivant (1991): A Foundational Delineation of Computational Feasiblity. In: Proceedings of the Sixth Annual Symposium on Logic in Computer Science (LICS '91), Amsterdam, The Netherlands, July 15-18, 1991. IEEE Computer Society, pp. 2–11, doi:10.1109/LICS.1991.151625.
  12. Daniel Leivant & Jean-Yves Marion (1994): Ramified Recurrence and Computational Complexity II: Substitution and Poly-Space. In: Leszek Pacholski & Jerzy Tiuryn: CSL, Lecture Notes in Computer Science 933. Springer, pp. 486–500, doi:10.1016/0022-0000(83)90008-9.
  13. Daniel Leivant & Jean-Yves Marion (2000): A characterization of alternating log time by ramified recurrence. Theor. Comput. Sci. 236(1-2), pp. 193–208, doi:10.1016/S0304-3975(99)00209-1.
  14. Daniel Leivant & Jean-Yves Marion (2000): Ramified Recurrence and Computational Complexity IV : Predicative Functionals and Poly-Space. Information and Computation, pp. 12 p. Available at https://hal.inria.fr/inria-00099077. To appear. Article dans revue scientifique avec comité de lecture..
  15. J. C. Lind (1974): Computing in logarithmic space. Technical Report. Massachusetts Institute of Technology.
  16. Walter L. Ruzzo (1981): On Uniform Circuit Complexity. J. Comput. Syst. Sci. 22(3), pp. 365–383, doi:10.1016/0022-0000(81)90038-6.

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org