Relational queries computable in polynomial time
From MaRDI portal
Publication:3753525
DOI10.1016/S0019-9958(86)80029-8zbMath0612.68086MaRDI QIDQ3753525
Publication date: 1986
Published in: Information and Control (Search for Journal in Brave)
relational calculusfinite model theoryleast fixed point operatorpolynomial time computable queriesfixed point query hierarchy
Related Items
Describing parameterized complexity classes, On symmetric circuits and fixed-point logics, Expressive equivalence of least and inflationary fixed-point logic, Symbioses between mathematical logic and computer science, Generalized quantifiers and pebble games on finite structures, A Parameterized Halting Problem, Semantic Restrictions over Second-Order Logic, Parameterized Complexity Classes under Logical Reductions, An algebra and a logic for \(NC^ 1\), Inductive definitions over finite structures, On uniformity within \(NC^ 1\), Non-determinism in logic-based languages, Canonization for two variables and puzzles on the square, Directions in generalized quantifier theory, The computational complexity of asymptotic problems. I: Partial orders, How to define a linear order on finite models, Finitely representable databases, A query language for NC, Hierarchies in transitive closure logic, stratified Datalog and infinitary logic, Descriptive complexity of deterministic polylogarithmic time and space, Descriptive characterizations of computational complexity, Using automata theory for characterizing the semantics of terminological cycles, Polynomial-time computable stable models, Metafinite model theory, Circumscribing DATALOG: expressive power and complexity, Complexity and undecidability results for logic programming, A probabilistic view of Datalog parallelization, Conjunctive and Boolean grammars: the true general case of the context-free grammars, On the relative expressiveness of description logics and predicate logics, \(\Delta\)-languages for sets and LOGSPACE computable graph transformers, Bounded fixpoints for complex objects, SO F : A Semantic Restriction over Second-Order Logic and Its Polynomial-Time Hierarchy, On the complexity of single-rule datalog queries., Fixpoint logics over hierarchical structures, First-order spectra with one variable, Ontology-Mediated Query Answering with Data-Tractable Description Logics, A second-order system for polytime reasoning based on Grädel's theorem., A uniform method for proving lower bounds on the computational complexity of logical theories, Parametrization over inductive relations of a bounded number of variables, Linear ordering on graphs, anti-founded sets and polynomial time computability, Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus, 0-1 laws and decision problems for fragments of second-order logic, When is arithmetic possible?, Arithmetizing uniform \(NC\), Datalog extensions for database queries and updates, Why not negation by fixpoint?, On the expressive power of database queries with intermediate types, A comparison between algebraic query languages for flat and nested databases, An analysis of fixed-point queries on binary trees, Expressive power and abstraction in Essence, The expressive power of the bounded-iteration construct, On the expressive power of counting, Computing with infinitary logic, The complexity of higher-order queries, A simple proof on the decidability of equivalence between recursive and nonrecursive Datalog programs, On the Unusual Effectiveness of Logic in Computer Science, On the equivalence of recursive and nonrecursive Datalog programs, The invariant problem for binary string structures and the parallel complexity theory of queries, Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates, Capturing complexity classes by fragments of second-order logic, Infinitary logics and 0-1 laws, Bounded linear logic: A modular approach to polynomial-time computability, The alternating fixpoint of logic programs with negation, Finite-model theory -- A personal perspective, A closed-form evaluation for Datalog queries with integer (gap)-order constraints, The parallel complexity of single rule logic programs, Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs, An optimal lower bound on the number of variables for graph identification, Number of variables is equivalent to space, Permutation dependency in datalog programs, Comparison of expressive power of some query languages for databases, Clocked population protocols, Mathematical logic and quantum finite state automata, Procedural languages for database queries and updates, Negation in rule-based database languages: A survey, On winning strategies in Ehrenfeucht-Fraïssé games, An extension of fixpoint logic with a symmetry-based choice construct, Reflective relational machines, A restricted second order logic for finite structures, Semantics and expressiveness issues in active databases, The expressive power of stratified logic programs with value invention, Positive versions of polynomial time, Games and total Datalog\(^{\lnot}\) queries, Structure and complexity of relational queries, Computing possible and certain answers over order-incomplete data, Almost Everywhere Equivalence of Logics in Finite Model Theory, Querying spatial databases via topological invariants, Lower bounds for invariant queries in logics with counting., An algebra for pomsets., Counting modulo quantifiers on finite structures, Equivalence and normal forms for the restricted and bounded fixpoint in the nested algebra, Adding for-loops to first-order logic, Linear time and the power of one first-order universal quantifier, Hereditarily-finite sets, data bases and polynomial-time computability, The expressive power of stratified logic programs, Quantified computation tree logic, Asymptotic invariants, complexity of groups and related problems, Context-sensitive transitive closure operators, Expressiveness of concept expressions in first-order description logics, Some thoughts on computational models: from massive human computing to abstract state machines, and beyond, Finite Variable Logics in Descriptive Complexity Theory, Unnamed Item, The dimension of the negation of transitive closure, Extensions of an idea of McNaughton, Reachability is harder for directed than for undirected finite graphs, Unnamed Item, Tailoring recursion for complexity, A query language for NC (extended abstract), The Expressive Power of Higher-Order Datalog, Capturing the polynomial hierarchy by second-order revised Krom logic, On the Descriptive Complexity of Linear Algebra, Axiomatizing first order consequences in inclusion logic, Unnamed Item, Unnamed Item, The expressive power of fixed-point logic with counting, Unnamed Item, Computing on structures, An analysis of the Core-ML language: Expressive power and type reconstruction, Expressiveness of efficient semi-deterministic choice constructs, Implicit definability and infinitary logic in finite model theory, A restricted second order logic for finite structures, Metafinite model theory, Complexity and expressive power of second‐order extended Horn logic, On the expressibility and the computability of untyped queries, Database Theory, Yuri, and Me, Existential Fixed-Point Logic, Universal Quantifiers, and Topoi, A Logic for PTIME and a Parameterized Halting Problem, Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs, Choiceless Computation and Symmetry, Unnamed Item, Semantics and expressive power of nondeterministic constructs in deductive databases, Infinitary logic for computer science, Expressivity and Complexity of Dependence Logic, Complexity thresholds in inclusion logic, Counting of Teams in First-Order Team Logics, On Dependence Logic, On fixed-point logic with counting, Logics which capture complexity classes over the reals, On polynomial time computation over unordered structures
