Languages that Capture Complexity Classes
From MaRDI portal
Publication:3773337
DOI10.1137/0216051zbMath0634.68034OpenAlexW1970629906WikidataQ56040402 ScholiaQ56040402MaRDI QIDQ3773337
Publication date: 1987
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0216051
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
Finite Variable Logics in Descriptive Complexity Theory, On asymptotic probabilities in logics that capture DSPACE(log n) in presence of ordering, The polynomial and linear time hierarchies in V0, On uniformity within \(NC^ 1\), Program verification with interacting analysis plugins, A logic of reachable patterns in linked data-structures, Some results on uniform arithmetic circuit complexity, On completeness for NP via projection translations, The dimension of the negation of transitive closure, Complete problems for fixed-point logics, Extensions of an idea of McNaughton, Reachability is harder for directed than for undirected finite graphs, Lower bounds for the modular communication complexity of various graph accessibility problems, Logics of Finite Hankel Rank, Capturing complexity classes with Lindström quantifiers, Cyclic hypersequent system for transitive closure logic, Tailoring recursion for complexity, Computation models and function algebras, Characterizing parallel time by type 2 recursions with polynomial output length, Logics capturing relativized complexity classes uniformly, A query language for NC (extended abstract), The 2CNF Boolean formula satisfiability problem and the linear space hypothesis, Capturing the polynomial hierarchy by second-order revised Krom logic, Bounded tree-width and LOGCFL, Many Facets of Dualities, Unnamed Item, Relativized logspace and generalized quantifiers over finite ordered structures, y= 2xVS.y= 3x, Computing on structures, Fifty years of the spectrum problem: survey and new results, On the Unusual Effectiveness of Logic in Computer Science, The bounded degree problem for non-obstructing eNCE graph grammars, Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates, Typed Monoids – An Eilenberg-Like Theorem for Non Regular Languages, Complexity and expressive power of second‐order extended Horn logic, Number of variables is equivalent to space, Finding Reductions Automatically, Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs, Locally finite languages, Unnamed Item, Semantics and expressive power of nondeterministic constructs in deductive databases, Lower bounds for the majority communication complexity of various graph accessibility problems, Unnamed Item, Dot operators, Computational complexity of some problems involving congruences on algebras, Circuit complexity and the expressive power of generalized first-order formulas, Complexity thresholds in inclusion logic, Choiceless Logarithmic Space, Reachability in Petri Nets with Inhibitor Arcs, Almost Everywhere Equivalence of Logics in Finite Model Theory, The algebra of recursive graph transformation language UnCAL: complete axiomatisation and iteration categorical semantics, Canonisation and Definability for Graphs of Bounded Rank Width, Logics which capture complexity classes over the reals, The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions., Dependence logic with generalized quantifiers: axiomatizations, Describing parameterized complexity classes, The monadic second order logic of graphs. VI: On several representations of graphs by relational structures, Generalized hex and logical characterizations of polynomial space, Languages represented by Boolean formulas, Closure properties of locally finite \(\omega\)-languages, Arithmetical definability and computational complexity, Multiple total stable models are definitely needed to solve unique solution problems, Querying disjunctive databases through nonmonotonic logics, The method of forced enumeration for nondeterministic automata, A logical characterization of constant-depth circuits over the reals, An algebra and a logic for \(NC^ 1\), On locating cubic subgraphs in bounded-degree connected bipartite graphs, Non-determinism in logic-based languages, Isomorphisms and 1-L reductions, Counting quantifiers, successor relations, and logarithmic space, The expressive powers of stable models for bound and unbound DATALOG queries, The bounded degree problem for eNCE graph grammars, Recursion theoretic characterizations of complexity classes of counting functions, Reachability and the power of local ordering, How to define a linear order on finite models, A double arity hierarchy theorem for transitive closure logic, Graph properties checkable in linear time in the number of vertices, Dyn-FO: A parallel, dynamic complexity class, Query languages for bags and aggregate functions, Finitely representable databases, A query language for NC, The complexity of the evaluation of complex algebra expressions, Hierarchies in transitive closure logic, stratified Datalog and infinitary logic, Descriptive characterizations of computational complexity, The Kolmogorov expressive power of Boolean query languages, Gap-languages and log-time complexity classes, Queries with arithmetical constraints, \(\Delta\)-languages for sets and LOGSPACE computable graph transformers, Reachability and connectivity queries in constraint databases, The isomorphism conjecture for constant depth reductions, On the state complexity of closures and interiors of regular languages with subwords and superwords, A note on first-order projections and games., A descriptive complexity approach to the linear hierarchy., Incremental recomputation in local languages., Forbidden lifts (NP and CSP for combinatorialists), Circuit complexity of linear functions: gate elimination and feeble security, Undecidability of the bandwidth problem on linear graph languages, First-order spectra with one variable, Arithmetizing uniform \(NC\), Datalog extensions for database queries and updates, Complete problems for symmetric logspace involving free groups, Logically defined subsets of \(\mathbb{N}{}^ k\), Monadic partition logics and finite automata, The expressiveness of a family of finite set languages, Complete problems for monotone NP, The invariant problem for binary string structures and the parallel complexity theory of queries, Regular languages in \(NC\), Bounded arithmetic for NC, ALogTIME, L and NL, The monadic second-order logic of graphs. VII: Graphs as relational structures, Capturing complexity classes by fragments of second-order logic, A survey of space complexity, Formulas, regular languages and Boolean circuits, Methods for proving completeness via logical reductions, Using the Hamiltonian path operator to capture NP, Infinite trees and automaton-definable relations over \(\omega\)-words, Finite-model theory -- A personal perspective, Low-complexity aggregation in GraphLog and Datalog, An optimal lower bound on the number of variables for graph identification, The navigational power of web browsers, A new recursion-theoretic characterization of the polytime functions, Inherent complexity of recursive queries, A model-theoretic characterization of constant-depth arithmetic circuits, Comparison of expressive power of some query languages for databases, Planar and grid graph reachability problems, Computing with graph rewriting systems with priorities, Mathematical logic and quantum finite state automata, Non-well-founded deduction for induction and coinduction, An extension of fixpoint logic with a symmetry-based choice construct, Logic, semigroups and automata on words, Reflective relational machines, A note on complexity measures for inductive classes in constructive type theory, Succinct representation, leaf languages, and projection reductions, On the power of built-in relations in certain classes of program schemes, Verifiable properties of database transactions, Positive versions of polynomial time, Local properties of query languages, Resolution of Hartmanis' conjecture for NL-hard sparse sets, Programs over semigroups of dot-depth one, Arity hierarchies, A logic-based approach to incremental reasoning on multi-agent systems, Succinctness as a source of complexity in logical formalisms, A generalized closure and complement phenomenon, Integrating induction and coinduction via closure operators and proof cycles, Lower bounds for invariant queries in logics with counting., Languages defined with modular counting quantifiers, The complexity of the \(K_{n,n}\)-problem for node replacement graph languages, Hereditarily-finite sets, data bases and polynomial-time computability, Cyclic proofs, hypersequents, and transitive closure logic, Functional queries in datalog, Program schemes, arrays, Lindström quantifiers and zero-one laws, Context-sensitive transitive closure operators, Logical and schematic characterization of complexity classes, An operational and denotational approach to non-context-freeness
