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