Computation models and function algebras

DOI10.1007/3-540-60178-3_81MaRDI QIDQ6064278

Peter Clote

Publication date: 12 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

zbMATH Keywords

Turing machinefunction algebrarandom access machineinput tapehigh type

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX)

Cites Work

• Functional interpretations of feasibly constructive arithmetic
• Subrecursive hierarchies on Scott domains
• Complexity for type-2 relations
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• On uniform circuit complexity
• A machine description and the hierarchy of initial Grzegorczyk classes
• Arithmetizing uniform \(NC\)
• Bounded arithmetic for NC, ALogTIME, L and NL
• A new recursion-theoretic characterization of the polytime functions
• Polynomial and abstract subrecursive classes
• A recursive and a grammatical characterization of the exponential-time languages
• Complete sets and the polynomial-time hierarchy
• Function-algebraic characterizations of log and polylog parallel time
• Nondeterministic stack register machines
• On uniformity within \(NC^ 1\)
• General recursive functions of natural numbers
• Über die mehrfache Rekursion
• Classes of Predictably Computable Functions
• Simulation of Parallel Random Access Machines by Circuits
• Languages that Capture Complexity Classes
• Finite automata, real time processes and counting problems in bounded arithmetics
• Equivalence of some Hierarchies of Primitive Recursive Functions
• Alternation
• A universal interconnection pattern for parallel computers
• An O(logn) parallel connectivity algorithm
• A time-space hierarchy between polynomial time and polynomial space
• Provably total functions of intuitionistic bounded arithmetic
• Small Grzegorczyk classes and limited minimum
• Satisfiability Is Quasilinear Complete in NQL
• Expressibility and Parallel Complexity
• Turing machines and the spectra of first-order formulas
• Parallelism in random access machines
• Subrecursiveness: Machine-independent notions of computability in restricted time and storage
• An Unsolvable Problem of Elementary Number Theory
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Definability and decision problems in arithmetic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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: Computation models and function algebras