Relational queries computable in polynomial time
From MaRDI portal
(Redirected from Publication:3753525)
Recommendations
Cited in
(only showing first 100 items - show all)- 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
- Generalized implicit definitions on finite structures
- On the expressibility and the computability of untyped queries
- A systematic study of isomorphism invariants of finite groups via the Weisfeiler-Leman dimension
- Inapproximability of unique games in fixed-point logic with counting
- The alternating fixpoint of logic programs with negation
- Characterizing polynomial Ramsey quantifiers
- Fixed-point definability and polynomial time on chordal graphs and line graphs
- Computing possible and certain answers over order-incomplete data
- A restricted second order logic for finite structures
- Adding for-loops to first-order logic
- Finite-model theory -- A personal perspective
- Quantified computation tree logic
- Canonization for two variables and puzzles on the square
- Some thoughts on computational models: from massive human computing to abstract state machines, and beyond
- A Parameterized Halting Problem
- Positive versions of polynomial time
- An extension of fixpoint logic with a symmetry-based choice construct
- The computational complexity of asymptotic problems. I: Partial orders
- A second-order system for polytime reasoning based on Grädel's theorem.
- Expressiveness of concept expressions in first-order description logics
- Non-determinism in logic-based languages
- On polynomial time computation over unordered structures
- Using automata theory for characterizing the semantics of terminological cycles
- On the equivalence of recursive and nonrecursive Datalog programs
- Number of variables is equivalent to space
- Semantics and expressive power of nondeterministic constructs in deductive databases
- Counting of Teams in First-Order Team Logics
- Polynomial-time computation via local inference relations
- An analysis of the Core-ML language: Expressive power and type reconstruction
- Semantics and expressiveness issues in active databases
- A linear time algorithm for monadic querying of indefinite data over linearly ordered domains
- Traversal-invariant characterizations of logarithmic space
- Finitely representable databases
- Counting modulo quantifiers on finite structures
- A probabilistic view of Datalog parallelization
- Descriptive complexity for counting complexity classes
- Descriptive characterizations of computational complexity
- A uniform method for proving lower bounds on the computational complexity of logical theories
- Infinitary logic for computer science
- Symbioses between mathematical logic and computer science
- Reflective relational machines
- Asymptotic invariants, complexity of groups and related problems.
- Datalog extensions for database queries and updates
- On the expressive power of database queries with intermediate types
- Bounded linear logic: A modular approach to polynomial-time computability
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- Database Theory, Yuri, and Me
- Circumscribing DATALOG: expressive power and complexity
- Symmetric circuits for rank logic
- Ontology-Mediated Query Answering with Data-Tractable Description Logics
- Verification, Model Checking, and Abstract Interpretation
- On winning strategies in Ehrenfeucht-Fraïssé games
- Tailoring recursion for complexity
- Theoretical computer science: computational complexity
- First-order spectra with one variable
- Comparison of expressive power of some query languages for databases
- Quantum first-order logics that capture logarithmic-time/space quantum computability
- Generalized quantifiers and pebble games on finite structures
- Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
- Directions in generalized quantifier theory
- Expressiveness of efficient semi-deterministic choice constructs
- On symmetric circuits and fixed-point logics
- On the complexity of single-rule datalog queries.
- Complexity and undecidability results for logic programming
- 0-1 laws and decision problems for fragments of second-order logic
- Hereditarily-finite sets, data bases and polynomial-time computability
- Parameterized Complexity Classes under Logical Reductions
- On the unusual effectiveness of logic in computer science
- Computing with first-order logic
- Choiceless polynomial time
- Constraint satisfaction, graph isomorphism, and the pebbling comonad
- An optimal lower bound on the number of variables for graph identification
- Context-sensitive transitive closure operators
- Linear algebraic quantifiers
- Inductive definitions over finite structures
- A restricted second order logic for finite structures
- Characterizing strongly first order dependencies: the non-jumping relativizable case
- Games and total Datalog\(^{\lnot}\) queries
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)
