Applicative theories for logarithmic complexity classes

DOI10.1016/J.TCS.2015.03.007MaRDI QIDQ2346995zbMATH OpenOpenAlexFDO

Authors 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 theoriesCantini's approach to Cook-Bellantoni algebralogarithmic complexity classeslogarithmic spacetwo-sorted algebra for polynomial timetwo-sorted characterisations of complexity classes

Mathematics Subject Classification ID

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

Review text

Two theories for logarithmic space are presented. The first formalises a new two-sorted algebra that is very similar to Cook and Bellantoni's two-sorted algebra \(B\) for polynomial time [\textit{S. Bellantoni} and \textit{S. Cook}, Comput. Complexity 2, No. 2, 97--110 (1992; Zbl 0766.68037)]. The second theory describes logarithmic space by formalising concatenation- and sharply bounded recursion. The theories are inspired by Cantini's theories formalising \(B\) [\textit{A. Cantini}, Arch. Math. Logic 41, No. 2, 169--189 (2002; Zbl 1042.03015)].

Recommendations

• Logics for complexity classes
• Approximate formulae for a logic that capture classes of computational complexity
• Logical and schematic characterization of complexity classes
• Towards applied theories based on computability logic
• scientific article; zbMATH DE number 2196512
• The structure of logarithmic advice complexity classes
• scientific article; zbMATH DE number 4008383
• scientific article; zbMATH DE number 4103047
• Applications of Kolmogorov complexity to computable model theory
• Logics capturing relativized complexity classes uniformly

Cites work

• A feasible theory of truth over combinatory algebra
• A new recursion-theoretic characterization of the polytime functions
• Applicative theories for the polynomial hierarchy of time and its levels
• Feasible mathematics II. Based on a workshop, held at the Cornell University, Ithaca, NY, USA, May 28-30, 1992
• Function algebraic characterizations of the polytime functions
• scientific article; zbMATH DE number 3900744 (Why is no real title available?)
• scientific article; zbMATH DE number 4006266 (Why is no real title available?)
• scientific article; zbMATH DE number 4033738 (Why is no real title available?)
• scientific article; zbMATH DE number 4066875 (Why is no real title available?)
• scientific article; zbMATH DE number 3556031 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• scientific article; zbMATH DE number 1390027 (Why is no real title available?)
• Logical foundations of proof complexity
• Logspace without bounds
• Polytime, combinatory logic and positive safe induction
• Programming Languages and Systems
• The provably terminating operations of the subsystem PETJ of explicit mathematics
• Theories with self-application and computational complexity.
• Weak theories of operations and types

Cited in

(6)

• The structure of logarithmic advice complexity classes
• Gap-languages and log-time complexity classes
• Theories with self-application and computational complexity.
• Applicative theories for the polynomial hierarchy of time and its levels
• Regressive computations characterize logarithmic space
• The equivalence of theories that characterize ALogTime

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2346995)