Relational queries computable in polynomial time
From MaRDI portal
Publication:3753525
Recommendations
Cited in
(only showing first 100 items - show all)- Expressive equivalence of least and inflationary fixed-point logic
- Finite-model theory -- A personal perspective
- On the equivalence of recursive and nonrecursive Datalog programs
- Capturing complexity classes by fragments of second-order logic
- Axiomatizing first order consequences in inclusion logic
- Choiceless polynomial time
- Negation in rule-based database languages: A survey
- Describing parameterized complexity classes
- Quantified computation tree logic
- The invariant problem for binary string structures and the parallel complexity theory of queries
- Implicit definability and infinitary logic in finite model theory (extended abstract)
- Parametrization over inductive relations of a bounded number of variables
- Polynomial queries to relational data bases
- On dependence logic
- Generalized quantifiers and pebble games on finite structures
- On polynomial time computation over unordered structures
- When is arithmetic possible?
- Infinitary logic for computer science
- Canonization for two variables and puzzles on the square
- On the relative expressiveness of description logics and predicate logics
- Datalog extensions for database queries and updates
- Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
- The complexity of evaluating relational queries
- Context-sensitive transitive closure operators
- Counting modulo quantifiers on finite structures
- Directions in generalized quantifier theory
- An optimal lower bound on the number of variables for graph identification
- The expressive power of stratified logic programs
- Finitely representable databases
- Inductive definitions over finite structures
- How to define a linear order on finite models
- Bounded linear logic: A modular approach to polynomial-time computability
- Arithmetizing uniform \(NC\)
- Computing with infinitary logic
- On the expressive power of counting
- A simple proof on the decidability of equivalence between recursive and nonrecursive Datalog programs
- On the expressive power of database queries with intermediate types
- A probabilistic view of Datalog parallelization
- Structure and complexity of relational queries
- 0-1 laws and decision problems for fragments of second-order logic
- Verification, Model Checking, and Abstract Interpretation
- Expressive power and abstraction in Essence
- On the unusual effectiveness of logic in computer science
- Existential fixed-point logic, universal quantifiers, and topoi
- Almost Everywhere Equivalence of Logics in Finite Model Theory
- A closed-form evaluation for Datalog queries with integer (gap)-order constraints
- The computational complexity of asymptotic problems. I: Partial orders
- A restricted second order logic for finite structures
- Expressiveness of concept expressions in first-order description logics
- Comparison of expressive power of some query languages for databases
- First-order spectra with one variable
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- The expressive power of stratified logic programs with value invention
- Reachability is harder for directed than for undirected finite graphs
- On uniformity within \(NC^ 1\)
- Extensions of an idea of McNaughton
- Positive versions of polynomial time
- The alternating fixpoint of logic programs with negation
- Polynomial-time computation via local inference relations
- Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
- Computing on structures
- On the complexity of single-rule datalog queries.
- The complexity of higher-order queries
- A comparison between algebraic query languages for flat and nested databases
- Why not negation by fixpoint?
- Complexity and undecidability results for logic programming
- Computing with first-order logic
- Using automata theory for characterizing the semantics of terminological cycles
- Horn clause queries and generalizations
- An algorithm for handling many relational calculus queries efficiently.
- Games and total Datalog\(^{\lnot}\) queries
- The expressive power of the bounded-iteration construct
- A uniform method for proving lower bounds on the computational complexity of logical theories
- Mathematical logic and quantum finite state automata
- On winning strategies in Ehrenfeucht-Fraïssé games
- Infinitary logics and 0-1 laws
- Expressiveness of efficient semi-deterministic choice constructs
- Metafinite model theory
- Querying spatial databases via topological invariants
- Procedural languages for database queries and updates
- On the Descriptive Complexity of Linear Algebra
- An algebra for pomsets.
- scientific article; zbMATH DE number 219206 (Why is no real title available?)
- On the expressibility and the computability of untyped queries
- Characterizing polynomial Ramsey quantifiers
- The arity hierarchy in the polyadic \(\mu\)-calculus
- Clocked population protocols
- The parallel complexity of single rule logic programs
- An algebra and a logic for \(NC^ 1\)
- Permutation dependency in datalog programs
- An extension of fixpoint logic with a symmetry-based choice construct
- The expressive power of higher-order Datalog
- Symmetric circuits for rank logic
- Constraint satisfaction, graph isomorphism, and the pebbling comonad
- Some thoughts on computational models: from massive human computing to abstract state machines, and beyond
- Capturing bisimulation-invariant exponential-time complexity classes
- Finite Variable Logics in Descriptive Complexity Theory
- Semantics and expressive power of nondeterministic constructs in deductive databases
- Logics which capture complexity classes over the reals
- A query language for NC
This page was built for publication: Relational queries computable in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3753525)
