Relational queries computable in polynomial time
From MaRDI portal
Publication:3753525
DOI10.1016/S0019-9958(86)80029-8zbMATH Open0612.68086MaRDI QIDQ3753525FDOQ3753525
Authors: Neil Immerman 
Publication date: 1986
Published in: Information and Control (Search for Journal in Brave)
Recommendations
finite model theoryrelational calculusleast fixed point operatorpolynomial time computable queriesfixed point query hierarchy
Cited In (only showing first 100 items - show all)
- The expressive power of stratified logic programs
- Arithmetizing uniform \(NC\)
- Extensions of an idea of McNaughton
- A closed-form evaluation for Datalog queries with integer (gap)-order constraints
- 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?
- The expressive power of the bounded-iteration construct
- Infinitary logics and 0-1 laws
- The alternating fixpoint of logic programs with negation
- A restricted second order logic for finite structures
- Finite-model theory -- A personal perspective
- Quantified computation tree logic
- Canonization for two variables and puzzles on the square
- Positive versions of polynomial time
- On polynomial time computation over unordered structures
- The computational complexity of asymptotic problems. I: Partial orders
- Expressiveness of concept expressions in first-order description logics
- Polynomial-time computation via local inference relations
- Using automata theory for characterizing the semantics of terminological cycles
- On the equivalence of recursive and nonrecursive Datalog programs
- Infinitary logic for computer science
- Counting modulo quantifiers on finite structures
- Finitely representable databases
- A probabilistic view of Datalog parallelization
- A uniform method for proving lower bounds on the computational complexity of logical theories
- Datalog extensions for database queries and updates
- Bounded linear logic: A modular approach to polynomial-time computability
- On the expressive power of database queries with intermediate types
- Verification, Model Checking, and Abstract Interpretation
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- On winning strategies in Ehrenfeucht-Fraïssé games
- Comparison of expressive power of some query languages for databases
- First-order spectra with one variable
- Expressiveness of efficient semi-deterministic choice constructs
- Generalized quantifiers and pebble games on finite structures
- Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
- Directions in generalized quantifier theory
- 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
- On the unusual effectiveness of logic in computer science
- Computing with first-order logic
- Choiceless polynomial time
- Context-sensitive transitive closure operators
- An optimal lower bound on the number of variables for graph identification
- Inductive definitions over finite structures
- On Dependence Logic
- Games and total Datalog\(^{\lnot}\) queries
- Querying spatial databases via topological invariants
- Capturing complexity classes by fragments of second-order logic
- Structure and complexity of relational queries
- Implicit definability and infinitary logic in finite model theory
- On uniformity within \(NC^ 1\)
- The complexity of evaluating relational queries
- Metafinite model theory
- Describing parameterized complexity classes
- On the relative expressiveness of description logics and predicate logics
- Expressive equivalence of least and inflationary fixed-point logic
- Negation in rule-based database languages: A survey
- Parametrization over inductive relations of a bounded number of variables
- When is arithmetic possible?
- Computing on structures
- How to define a linear order on finite models
- The complexity of higher-order queries
- Mathematical logic and quantum finite state automata
- Polynomial queries to relational data bases
- Horn clause queries and generalizations
- Axiomatizing first order consequences in inclusion logic
- Existential fixed-point logic, universal quantifiers, and topoi
- Almost Everywhere Equivalence of Logics in Finite Model Theory
- Expressive power and abstraction in Essence
- Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
- The invariant problem for binary string structures and the parallel complexity theory of queries
- Reachability is harder for directed than for undirected finite graphs
- The expressive power of stratified logic programs with value invention
- Computing with infinitary logic
- On the expressive power of counting
- A simple proof on the decidability of equivalence between recursive and nonrecursive Datalog programs
- Procedural languages for database queries and updates
- Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
- Expressivity and Complexity of Dependence Logic
- Title not available (Why is that?)
- 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
- Metafinite model theory
- Capturing the polynomial hierarchy by second-order revised Krom logic
- Bounded fixed-point definability and tabular recognition of languages
- First order logic, fixed point logic and linear order
- Generalized implicit definitions on finite structures
- \(\Delta\)-languages for sets and LOGSPACE computable graph transformers
- On the expressibility and the computability of untyped queries
- Inapproximability of unique games in fixed-point logic with counting
- Fixed-point definability and polynomial time on chordal graphs and line graphs
- Computing possible and certain answers over order-incomplete data
- Semantic Restrictions over Second-Order Logic
- Adding for-loops to first-order logic
- Some thoughts on computational models: from massive human computing to abstract state machines, and beyond
- Title not available (Why is that?)
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)
