Expressibility and Parallel Complexity
From MaRDI portal
Publication:4207580
DOI10.1137/0218043zbMath0688.68038OpenAlexW2055874330WikidataQ61687225 ScholiaQ61687225MaRDI QIDQ4207580
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/4278570098b65d1a94598a05dd08fc95ce63c598
Related Items
ALOGTIME and a conjecture of S. A. Cook, Circuits in bounded arithmetic. I, A logical characterization of constant-depth circuits over the reals, A note on some languages in uniform \(ACC^ 0\), On uniformity within \(NC^ 1\), Some results on uniform arithmetic circuit complexity, 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, Extensions of an idea of McNaughton, Capturing complexity classes with Lindström quantifiers, Nondeterministic stack register machines, Computation models and function algebras, Logics capturing relativized complexity classes uniformly, A query language for NC (extended abstract), Model-checking hierarchical structures, Extensional Uniformity for Boolean Circuits, A Characterisation of NL Using Membrane Systems without Charges and Dissolution, Reversal complexity revisited, Rudimentary reductions revisited, The invariant problem for binary string structures and the parallel complexity theory of queries, Computing with Spikes: The Advantage of Fine-Grained Timing, Capturing complexity classes by fragments of second-order logic, A constant-space sequential model of computation for first-order logic, Reasoning and Query Answering in Description Logics, Diagonalization, uniformity, and fixed-point theorems, Low-complexity aggregation in GraphLog and Datalog, Number of variables is equivalent to space, The computational power of membrane systems under tight uniformity conditions, The descriptive complexity approach to LOGCFL, First-order logics: some characterizations and closure properties, A topological approach to non-uniform complexity, A Language-Theoretical Approach to Descriptive Complexity, Reflective relational machines, A constant-space sequential model of computation for first-order logic, Separating NC along the \(\delta\) axis, Computational Power of Quantum Machines, Quantum Grammars and Feasible Computation, PARALLEL VERTEX COLOURING OF INTERVAL GRAPHS, A logic-based approach to incremental reasoning on multi-agent systems, Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\), Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space, The parallel complexity of two problems on concurrency, Dynamic complexity of expansion
