Applicative theories for logarithmic complexity classes

DOI10.1016/j.tcs.2015.03.007zbMath1330.68086OpenAlexW2139005125MaRDI QIDQ2346995

Sebastian Eberhard

Publication date: 26 May 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.03.007

zbMATH Keywords

applicative theorieslogarithmic spaceCantini's approach to Cook-Bellantoni algebralogarithmic complexity classestwo-sorted algebra for polynomial timetwo-sorted characterisations of complexity classes

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Algebraic theory of languages and automata (68Q70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Regressive computations characterize logarithmic space

Cites Work

• The provably terminating operations of the subsystem PETJ of explicit mathematics
• A new recursion-theoretic characterization of the polytime functions
• Feasible mathematics II. Based on a workshop, held at the Cornell University, Ithaca, NY, USA, May 28-30, 1992
• Polytime, combinatory logic and positive safe induction
• Theories with self-application and computational complexity.
• Function algebraic characterizations of the polytime functions
• Applicative theories for the polynomial hierarchy of time and its levels
• A feasible theory of truth over combinatory algebra
• Programming Languages and Systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Applicative theories for logarithmic complexity classes