Expressibility and Parallel Complexity
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 4068238
- scientific article; zbMATH DE number 515222
- scientific article; zbMATH DE number 4172382
- scientific article; zbMATH DE number 1305047
- scientific article; zbMATH DE number 1163093
- scientific article; zbMATH DE number 4117855
- Parallel restructuring and evaluation of expressions
- Complexity measures on systems of parallel algorithms
- The expressive power of monotonic parallel composition
Cited in
(51)- Extensions of an idea of McNaughton
- Low-complexity aggregation in GraphLog and Datalog
- Nondeterministic stack register machines
- Dynamic complexity of expansion
- Circuit complexity before the dawn of the new millennium
- Lenient evaluation and parallelism
- Computational Power of Quantum Machines, Quantum Grammars and Feasible Computation
- Model-checking hierarchical structures
- The computational power of membrane systems under tight uniformity conditions
- A constant-space sequential model of computation for first-order logic
- Expressibility and Nonuniform Complexity Classes
- Number of variables is equivalent to space
- A constant-space sequential model of computation for first-order logic
- Circuits in bounded arithmetic. I
- scientific article; zbMATH DE number 515222 (Why is no real title available?)
- Recursion theoretic characterizations of complexity classes of counting functions
- Reflective relational machines
- Capturing complexity classes with Lindström quantifiers
- A language-theoretical approach to descriptive complexity
- A Characterisation of NL Using Membrane Systems without Charges and Dissolution
- Reversal complexity revisited
- The descriptive complexity approach to LOGCFL
- The parallel complexity of two problems on concurrency
- Rudimentary reductions revisited
- A logical characterization of constant-depth circuits over the reals
- Some results on uniform arithmetic circuit complexity
- Computation models and function algebras
- A note on some languages in uniform \(ACC^ 0\)
- Capturing complexity classes by fragments of second-order logic
- Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space
- Reasoning and query answering in description logics
- Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\)
- Extensional Uniformity for Boolean Circuits
- On uniformity within \(NC^ 1\)
- A topological approach to non-uniform complexity
- Parallel vertex colouring of interval graphs
- Diagonalization, uniformity, and fixed-point theorems
- First-order logics: some characterizations and closure properties
- scientific article; zbMATH DE number 4172382 (Why is no real title available?)
- Interdefinability of parallel operations in PCF
- ALOGTIME and a conjecture of S. A. Cook
- A query language for NC (extended abstract)
- Reachability and the power of local ordering
- A logic-based approach to incremental reasoning on multi-agent systems
- Logics capturing relativized complexity classes uniformly
- Separating NC along the \(\delta\) axis
- The invariant problem for binary string structures and the parallel complexity theory of queries
- A query language for NC
- Dyn-FO: A parallel, dynamic complexity class
- scientific article; zbMATH DE number 4106276 (Why is no real title available?)
- Computing with spikes: the advantage of fine-grained timing
This page was built for publication: Expressibility and Parallel Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4207580)
