Languages that Capture Complexity Classes
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Mathematical logic and quantum finite state automata
- The method of forced enumeration for nondeterministic automata
- Isomorphisms and 1-L reductions
- Descriptive characterizations of computational complexity
- 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\)
- 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
- Using the Hamiltonian path operator to capture NP
- Infinite trees and automaton-definable relations over -words
- An optimal lower bound on the number of variables for graph identification
- A new recursion-theoretic characterization of the polytime functions
- Computing with graph rewriting systems with priorities
- An extension of fixpoint logic with a symmetry-based choice construct
- 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
- Succinctness as a source of complexity in logical formalisms
- Hereditarily-finite sets, data bases and polynomial-time computability
- Context-sensitive transitive closure operators
- Logical and schematic characterization of complexity classes
- The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
- Multiple total stable models are definitely needed to solve unique solution problems
- Querying disjunctive databases through nonmonotonic logics
- On locating cubic subgraphs in bounded-degree connected bipartite graphs
- Non-determinism in logic-based languages
- 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
- 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
- The Kolmogorov expressive power of Boolean query languages
- Gap-languages and log-time complexity classes
- Queries with arithmetical constraints
- -languages for sets and LOGSPACE computable graph transformers
- Reachability and connectivity queries in constraint databases
- A note on first-order projections and games.
- A descriptive complexity approach to the linear hierarchy.
- Incremental recomputation in local languages.
- Local properties of query languages
- Resolution of Hartmanis' conjecture for NL-hard sparse sets
- Programs over semigroups of dot-depth one
- Program schemes, arrays, Lindström quantifiers and zero-one laws
- Logic, semigroups and automata on words
- 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
- Functional queries in datalog
- An operational and denotational approach to non-context-freeness
- The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
- Describing parameterized complexity classes
- Closure properties of locally finite \(\omega\)-languages
- Arithmetical definability and computational complexity
- A double arity hierarchy theorem for transitive closure logic
- Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
- Circuit complexity of linear functions: gate elimination and feeble security
- Non-well-founded deduction for induction and coinduction
- A logic-based approach to incremental reasoning on multi-agent systems
- Integrating induction and coinduction via closure operators and proof cycles
- Cyclic proofs, hypersequents, and transitive closure logic
- A logical characterization of constant-depth circuits over the reals
- Dependence logic with generalized quantifiers: axiomatizations
- Forbidden lifts (NP and CSP for combinatorialists)
- Comparison of expressive power of some query languages for databases
- Arity hierarchies
- An algebra and a logic for \(NC^ 1\)
- On uniformity within \(NC^ 1\)
- Program verification with interacting analysis plugins
- A logic of reachable patterns in linked data-structures
- On the unusual effectiveness of logic in computer science
- Number of variables is equivalent to space
- Generalized hex and logical characterizations of polynomial space
- Languages represented by Boolean formulas
- Logics of finite Hankel rank
- Many Facets of Dualities
- Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates
- Typed monoids -- an Eilenberg-like theorem for non regular languages
- Almost Everywhere Equivalence of Logics in Finite Model Theory
- The algebra of recursive graph transformation language UnCAL: complete axiomatisation and iteration categorical semantics
- The polynomial and linear time hierarchies in V0
- Extensions of an idea of McNaughton
- Reachability is harder for directed than for undirected finite graphs
- Finding Reductions Automatically
- Fixed-point definability and polynomial time on chordal graphs and line graphs
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)
