Relational queries computable in polynomial time
From MaRDI portal
(Redirected from Publication:3753525)
Recommendations
Cited in
(only showing first 100 items - show all)- On fixed-point logic with counting
- Capturing complexity classes by fragments of second-order logic
- Querying spatial databases via topological invariants
- Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates
- Logical characterizations of weighted complexity classes
- Clocked population protocols
- The expressive power of fixed-point logic with counting
- Tameness in least fixed-point logic and McColm's conjecture
- On the Descriptive Complexity of Linear Algebra
- scientific article; zbMATH DE number 3976395 (Why is no real title available?)
- The arity hierarchy in the polyadic -calculus
- Quantum first-order logics and quantum natural deduction
- Structure and complexity of relational queries
- Guarded hybrid team logics
- scientific article; zbMATH DE number 1531039 (Why is no real title available?)
- The dimension of the negation of transitive closure
- On uniformity within \(NC^ 1\)
- On the descriptive complexity of groups without abelian normal subgroups
- The complexity of evaluating relational queries
- Complexity thresholds in inclusion logic
- \(\mathrm{SO}^F\): a semantic restriction over second-order logic and its polynomial-time hierarchy
- Metafinite model theory
- An analysis of fixed-point queries on binary trees
- Describing parameterized complexity classes
- Limits of symmetric computation (invited talk)
- Insignificant choice polynomial time. A logic capturing PTIME
- On the relative expressiveness of description logics and predicate logics
- Counting of teams in first-order team logics
- scientific article; zbMATH DE number 219206 (Why is no real title available?)
- Expressive equivalence of least and inflationary fixed-point logic
- Declarative PTIME queries for relational databases using quantifier elimination
- On the parallel complexity of group isomorphism via Weisfeiler-Leman
- Polynomial-time computable stable models
- Negation in rule-based database languages: A survey
- Parametrization over inductive relations of a bounded number of variables
- When is arithmetic possible?
- Capturing bisimulation-invariant exponential-time complexity classes
- An algebra for pomsets.
- Regular representations of uniform TC^0
- An abstract fixed-point theorem for Horn formula equations
- How to define a linear order on finite models
- Computing on structures
- The complexity of higher-order queries
- Finite variable counting logics with restricted requantification
- Descriptive complexity and weighted Turing machines
- Mathematical logic and quantum finite state automata
- Semantic restrictions over second-order logic
- Linear ordering on graphs, anti-founded sets and polynomial time computability
- The parallel complexity of single rule logic programs
- Polynomial queries to relational data bases
- Permutation dependency in datalog programs
- Finite Variable Logics in Descriptive Complexity Theory
- A query language for NC (extended abstract)
- On dependence logic
- Logics which capture complexity classes over the reals
- Finite-State Map-Reduce Computation and Relational Algebra Queries
- Horn clause queries and generalizations
- A logic for PTIME and a parameterized halting problem
- Expressive power and abstraction in Essence
- Axiomatizing first order consequences in inclusion logic
- Almost Everywhere Equivalence of Logics in Finite Model Theory
- Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
- Existential fixed-point logic, universal quantifiers, and topoi
- Descriptive complexity of deterministic polylogarithmic time and space
- The invariant problem for binary string structures and the parallel complexity theory of queries
- A query language for NC
- Bounded fixpoints for complex objects
- Fixpoint logics over hierarchical structures
- The expressive power of stratified logic programs with value invention
- The expressive power of higher-order Datalog
- Choiceless computation and symmetry
- Reachability is harder for directed than for undirected finite graphs
- 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 descriptive complexity of groups without abelian normal subgroups (extended abstract)
- Complexity and expressive power of second-order extended Horn logic
- An algebra and a logic for \(NC^ 1\)
- Procedural languages for database queries and updates
- Arithmetizing uniform NC
- The Relational Polynomial-Time Hierarchy and Second-Order Logic
- The expressive power of stratified logic programs
- Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
- Lower bounds for invariant queries in logics with counting.
- Equivalence and normal forms for the restricted and bounded fixpoint in the nested algebra
- Linear time and the power of one first-order universal quantifier
- Expressivity and Complexity of Dependence Logic
- Extensions of an idea of McNaughton
- A closed-form evaluation for Datalog queries with integer (gap)-order constraints
- Metafinite model theory
- -languages for sets and LOGSPACE computable graph transformers
- An algorithm for handling many relational calculus queries efficiently.
- A comparison between algebraic query languages for flat and nested databases
- Why not negation by fixpoint?
- Capturing the polynomial hierarchy by second-order revised Krom logic
- The expressive power of the bounded-iteration construct
- Implicit definability and infinitary logic in finite model theory (extended abstract)
- Infinitary logics and 0-1 laws
- Bounded fixed-point definability and tabular recognition of languages
- First order logic, fixed point logic and linear order
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)
