Relational queries computable in polynomial time
From MaRDI portal
(Redirected from Publication:3753525)
Recommendations
Cited in
(only showing first 100 items - show all)- Mathematical logic and quantum finite state automata
- Polynomial queries to relational data bases
- The computational complexity of asymptotic problems. I: Partial orders
- Descriptive characterizations of computational complexity
- Choiceless polynomial time
- Circumscribing DATALOG: expressive power and complexity
- 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
- The expressive power of the bounded-iteration construct
- The invariant problem for binary string structures and the parallel complexity theory of queries
- 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 parallel complexity of single rule logic programs
- An optimal lower bound on the number of variables for graph identification
- Permutation dependency in datalog programs
- 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
- Hereditarily-finite sets, data bases and polynomial-time computability
- Context-sensitive transitive closure operators
- Non-determinism in logic-based languages
- Canonization for two variables and puzzles on the square
- How to define a linear order on finite models
- Finitely representable databases
- A query language for NC
- Using automata theory for characterizing the semantics of terminological cycles
- Polynomial-time computable stable models
- Metafinite model theory
- A probabilistic view of Datalog parallelization
- -languages for sets and LOGSPACE computable graph transformers
- Bounded fixpoints for complex objects
- On the complexity of single-rule datalog queries.
- A second-order system for polytime reasoning based on Grädel's theorem.
- Games and total Datalog\(^{\lnot}\) queries
- Querying spatial databases via topological invariants
- Quantified computation tree logic
- Expressiveness of concept expressions in first-order description logics
- Structure and complexity of relational queries
- 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
- An algorithm for handling many relational calculus queries efficiently.
- Describing parameterized complexity classes
- Expressive equivalence of least and inflationary fixed-point logic
- A linear time algorithm for monadic querying of indefinite data over linearly ordered domains
- Computing with first-order logic
- Generalized quantifiers and pebble games on finite structures
- Directions in generalized quantifier theory
- Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
- Complexity and undecidability results for logic programming
- Linear ordering on graphs, anti-founded sets and polynomial time computability
- Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
- Clocked population protocols
- Some thoughts on computational models: from massive human computing to abstract state machines, and beyond
- Computing possible and certain answers over order-incomplete data
- On symmetric circuits and fixed-point logics
- Fixpoint logics over hierarchical structures
- Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
- Comparison of expressive power of some query languages for databases
- Symbioses between mathematical logic and computer science
- An algebra and a logic for \(NC^ 1\)
- Inductive definitions over finite structures
- On uniformity within \(NC^ 1\)
- Descriptive complexity of deterministic polylogarithmic time and space
- On the relative expressiveness of description logics and predicate logics
- On the unusual effectiveness of logic in computer science
- Number of variables is equivalent to space
- A Parameterized Halting Problem
- Ontology-Mediated Query Answering with Data-Tractable Description Logics
- Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates
- Almost Everywhere Equivalence of Logics in Finite Model Theory
- Asymptotic invariants, complexity of groups and related problems.
- Parameterized Complexity Classes under Logical Reductions
- \(\mathrm{SO}^F\): a semantic restriction over second-order logic and its polynomial-time hierarchy
- The complexity of evaluating relational queries
- Semantic restrictions over second-order logic
- Extensions of an idea of McNaughton
- Reachability is harder for directed than for undirected finite graphs
- On the Descriptive Complexity of Linear Algebra
- 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
- Horn clause queries and generalizations
- scientific article; zbMATH DE number 3976395 (Why is no real title available?)
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- Finite Variable Logics in Descriptive Complexity Theory
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)
