Computation models and function algebras
From MaRDI portal
Publication:6064278
DOI10.1007/3-540-60178-3_81MaRDI QIDQ6064278
Publication date: 12 December 2023
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
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