Languages that Capture Complexity Classes
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Arithmetizing uniform NC
- Lower bounds for invariant queries in logics with counting.
- The complexity of the \(K_{n,n}\)-problem for node replacement graph languages
- Planar and grid graph reachability problems
- Locally finite languages
- The monadic second-order logic of graphs. VII: Graphs as relational structures
- Extensions of an idea of McNaughton
- Low-complexity aggregation in GraphLog and Datalog
- Many Facets of Dualities
- -languages for sets and LOGSPACE computable graph transformers
- Querying disjunctive databases through nonmonotonic logics
- Capturing the polynomial hierarchy by second-order revised Krom logic
- Lower bounds for the modular communication complexity of various graph accessibility problems
- The expressive power of ``possible-is-certain semantics (extended abstract)
- Infinite trees and automaton-definable relations over -words
- Using the Hamiltonian path operator to capture NP
- scientific article; zbMATH DE number 7561616 (Why is no real title available?)
- A note on first-order projections and games.
- A descriptive complexity approach to the linear hierarchy.
- Circuit complexity and the expressive power of generalized first-order formulas
- The navigational power of web browsers
- Inherent complexity of recursive queries
- Circuit complexity before the dawn of the new millennium
- Local properties of query languages
- Fixed-point definability and polynomial time on chordal graphs and line graphs
- Graph properties checkable in linear time in the number of vertices
- The Kolmogorov expressive power of Boolean query languages
- Computing with graph rewriting systems with priorities
- An operational and denotational approach to non-context-freeness
- On completeness for NP via projection translations
- Complete problems for symmetric logspace involving free groups
- Finite-model theory -- A personal perspective
- Counting quantifiers, successor relations, and logarithmic space
- On locating cubic subgraphs in bounded-degree connected bipartite graphs
- Reachability in Petri nets with inhibitor arcs
- Logically defined subsets of \(\mathbb{N}{}^ k\)
- Positive versions of polynomial time
- The polynomial and linear time hierarchies in V0
- scientific article; zbMATH DE number 1086669 (Why is no real title available?)
- A generalized closure and complement phenomenon
- An extension of fixpoint logic with a symmetry-based choice construct
- A note on complexity measures for inductive classes in constructive type theory
- Complete problems for fixed-point logics
- Non-determinism in logic-based languages
- Number of variables is equivalent to space
- y= 2xVS.y= 3x
- Semantics and expressive power of nondeterministic constructs in deductive databases
- Functional queries in datalog
- Relativized logspace and generalized quantifiers over finite ordered structures
- Reachability and connectivity queries in constraint databases
- Dot operators
- Choiceless polynomial time with witnessed symmetric choice
- On the power of built-in relations in certain classes of program schemes
- Verifiable properties of database transactions
- Generalized hex and logical characterizations of polynomial space
- Query languages for bags and aggregate functions
- Bounded arithmetic for NC, ALogTIME, L and NL
- Finitely representable databases
- Queries with arithmetical constraints
- Descriptive characterizations of computational complexity
- The expressive powers of stable models for bound and unbound DATALOG queries
- Recursion theoretic characterizations of complexity classes of counting functions
- Languages represented by Boolean formulas
- Logical and schematic characterization of complexity classes
- Reflective relational machines
- Typed monoids -- an Eilenberg-like theorem for non regular languages
- Fifty years of the spectrum problem: survey and new results
- Datalog extensions for database queries and updates
- Capturing complexity classes with Lindström quantifiers
- A new recursion-theoretic characterization of the polytime functions
- Cyclic hypersequent system for transitive closure logic
- Methods for proving completeness via logical reductions
- Succinctness as a source of complexity in logical formalisms
- scientific article; zbMATH DE number 7533347 (Why is no real title available?)
- Multiple total stable models are definitely needed to solve unique solution problems
- Tailoring recursion for complexity
- Unary and two-variable interval logics
- Complete problems for monotone NP
- Querying incomplete data: complexity and tractability via Datalog and first-order rewritings
- First-order spectra with one variable
- Program verification with interacting analysis plugins
- Dependence logic with generalized quantifiers: axiomatizations
- Comparison of expressive power of some query languages for databases
- A double arity hierarchy theorem for transitive closure logic
- Quantum first-order logics that capture logarithmic-time/space quantum computability
- Separating rank logic from polynomial time
- Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
- Arithmetical definability and computational complexity
- A logical characterization of constant-depth circuits over the reals
- Some results on uniform arithmetic circuit complexity
- Hereditarily-finite sets, data bases and polynomial-time computability
- The algebra of recursive graph transformation language UnCAL: complete axiomatisation and iteration categorical semantics
- On the unusual effectiveness of logic in computer science
- Characterizing parallel time by type 2 recursions with polynomial output length
- Computation models and function algebras
- An optimal lower bound on the number of variables for graph identification
- Context-sensitive transitive closure operators
- The method of forced enumeration for nondeterministic automata
- NP-completeness by first-order and quantifier-free interpretations and related topics
- Succinct representation, leaf languages, and projection reductions
This page was built for publication: Languages that Capture Complexity Classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3773337)
