Parallel complexity of logical query programs

No abstract is available for this paper.

• Publication year

  1986

• Venue

  27th Annual Symposium on Foundations of Computer Science (sfcs 1986)

• Publication date

  1986-10-27

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1007/BF01762108
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Negation as Failure using Tight Derivations for General Logic Programs

  1988cited by this paper
• The parallel complexity of simple chain queries

  1987influential reference
• Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits

  1986cited by this paper
• Parallel tree contraction and its application

  1985cited by this paper
• Querying logical databases

  1985cited by this paper
• Solving tree problems on a mesh-connected processor array

  1985cited by this paper
• A Taxonomy of Problems with Fast Parallel Algorithms

  1985cited by this paper
• Parallel evaluation of recursive rule queries

  1985influential reference
• Simulation of Parallel Random Access Machines by Circuits

  1984cited by this paper
• Alternation and the Computational Complexity of Logic Programs

  1984cited by this paper
• Fast Parallel Computation of Polynomials Using Few Processors

  1983cited by this paper
• Contributions to the Theory of Logic Programming

  1982cited by this paper
• Structure and complexity of relational queries

  1980cited by this paper
• J.E.Hopcroft, J.D. Ullman 著, "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley, A5変形版, X+418, \6,670, 1979

  1980cited by this paper
• The Universality of Data Retrieval Languages

  1979cited by this paper
• Tree-size bounded alternation(Extended Abstract)

  1979influential reference
• Introduction to Automata Theory, Languages and Computation

  1979cited by this paper
• The Semantics of Predicate Logic as a Programming Language

  1976cited by this paper
• Review: Sheila Greibach, A Note on Undecidable Properties of Formal Languages

  1975cited by this paper
• Complete problems for deterministic polynomial time

  1974cited by this paper
• An observation on time-storage trade off

  1973cited by this paper
• The Hardest Context-Free Language

  1973cited by this paper
• Finite-Turn Pushdown Automata

  1966cited by this paper
• SParallel Complexity of Logical Query Programs

  year unknowncited by this paper

• Synthesizing Recursive Logic Programs by Inverting General Resolution

  2025cites this paper
• Circuits and Formulas for Datalog over Semirings

  2025cites this paper
• Evaluating Datalog over Semirings: A Grounding-based Approach

  2024cites this paper
• Evaluating Datalog via Structure-Aware Rewriting

  2024cites this paper
• The Fine-Grained Complexity of CFL Reachability

  2023cites this paper
• Rational Index of Languages Defined by Grammars with Bounded Dimension of Parse Trees

  2023cites this paper
• Reasoning in Knowledge Graphs

  2022cites this paper
• Rational index of bounded-oscillation languages

  2020influential citation
• A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom

  2020cites this paper
• Recognising FO-rewritability of Ontology-Mediated Queries in Linear Temporal Logic

  2020cites this paper
• A tetrachotomy of ontology-mediated queries with a covering axiom

  2020cites this paper
• On the Use of Quasiorders in Formal Language Theory

  2020cites this paper
• Checking the Data Complexity of Ontology-Mediated Queries: A Case Study with Non-uniform CSPs and Polyanna

  2019cites this paper
• Distribution Policies for Datalog

  2019cites this paper
• Regular Expression Search on Compressed Text

  2019cites this paper
• Towards a Data Complexity Classification of Ontology-Mediated Queries with Covering

  2018cites this paper
• Title Logspace Bounded Alternation and Logical Query Programs

  2018cites this paper
• From Knowledge Graph Embedding to Ontology Embedding? An Analysis of the Compatibility between Vector Space Representations and Rules

  2018cites this paper
• Regular Expression Search in Compressed Text Extended Abstract

  2018cites this paper
• An Ordinal-free Proof of the Complete Cut-elimination Theorem for \Pi^1_1-CA+BI with the omega-rule

  2017cites this paper
• Newtonian Program Analysis via Tensor Product

  2017cites this paper
• Efficient exact paths for dyck and semi-dyck labeled path reachability (extended abstract)

  2017cites this paper
• Parsing and Generation as Datalog Query Evaluation.

  2017cites this paper
• A Datalog Framework for Modeling Relationship-based Access Control Policies

  2017cites this paper
• University of Dundee Exploiting parallelism in coalgebraic logic programming

  2016influential citation
• Datalog and Logic Databases

  2015cites this paper
• Query Processing for Massively Parallel Systems

  2015cites this paper
• On the Complexity of L-reachability

  2014cites this paper
• The Complexity of Flow Analysis in Higher-Order Languages

  2013cites this paper
• Exploiting Parallelism in Coalgebraic Logic Programming

  2013influential citation
• On implementing provenance-aware regular path queries with relational query engines

  2013cites this paper
• Coalgebraic logic programming: from Semantics to Implementation

  2013influential citation
• Transitive closure and recursive Datalog implemented on clusters

  2012cites this paper
• Coalgebraic Logic Programming : implicit versus explicit resource handling

  2012cites this paper
• 1 Coalgebraic Derivations in Logic Programming

  2011cites this paper
• Map-reduce extensions and recursive queries

  2011influential citation
• Coalgebraic Derivations in Logic Programming

  2011cites this paper
• Unification neural networks: unification by error-correction learning

  2011cites this paper
• Realizable paths and the NL vs L problem

  2011influential citation
• Coalgebraic Semantics for Logic Programming

  2010cites this paper
• Coalgebraic Semantics for Parallel Derivation Strategies in Logic Programming

  2010cites this paper
• Realizable Paths and the NL vs L Problem

  2010cites this paper
• Parsing and Generation as Datalog Queries

  2007influential citation
• Improving the Predictive Power of Rules Learned for Robot Navigation

  2007cites this paper
• Linearizability on Datalog Programs ?

  2007cites this paper
• Coinductive Logic Programming

  2006cites this paper
• Information Preservation in XML-to-Relational Mappings

  2004cites this paper
• On the Graph Traversal and Linear Binary-Chain Programs

  2003cites this paper
• Linearisability on datalog programs

  2003cites this paper
• Inherent Complexity of Recursive Queries

  2002cites this paper
• The Branching-Time Transformation Technique for Chain Datalog Programs

  2001cites this paper
• Static analysis in datalog extensions

  2001cites this paper
• A Complete Neural Network Algorithm for Horn-Sat

  2000cites this paper
• Interconvertibility of a class of set constraints and context-free-language reachability

  2000influential citation
• On the complexity of single-rule datalog queries

  1999cites this paper
• Answering Queries Using Materialized Views with Disjunctions

  1999cites this paper
• The Dynamic Parallel Complexity of Computational Circuits

  1999cites this paper
• Grammars and Automata to Optimize Chain Logic Queries

  1999cites this paper
• Optimizing chain datalog programs and their inference procedures

  1999cites this paper
• Inherent complexity of recursive queries

  1999influential citation
• Interconvertibility of a Class of Set Constraints and Context-free-language Reachability 1

  1998influential citation
• OLDTNF-based evaluation method for handling recursive queries in deductive databases

  1998cites this paper
• Program analysis via graph reachability

  1997cites this paper
• On the Parallel Complexity of Loops

  1997cites this paper
• Complexity and expressive power of logic programming

  1997cites this paper
• Chain Queries Expressible by Linear Datalog Programs

  1997cites this paper
• Learning Acyclic First-Order Horn Sentences from Entailment

  1997cites this paper
• Restructuring Chain Datalog Programs (Preliminary Report)

  1996influential citation
• Shruti's Ontology is Representational

  1996cites this paper
• On Transformations into Linear Database Logic Programs

  1996influential citation
• Parallel reasoning in structured connectionist networks: Signatures versus temporal synchrony

  1996cites this paper
• Temporal synchrony, dynamic bindings, and Shruti: A representational but nonclassical model of reflexive reasoning

  1996cites this paper
• Limits to Parallel Computation: P-Completeness Theory

  1995cites this paper
• The PushDown Method to Optimize Chain Logic Programs (Extended Abstract)

  1995cites this paper
• Perspectives on database theory

  1995cites this paper
• Practical Behavior of Parallelization Strategies for Datalog

  1995cites this paper
• On Decompositions of Chain Datalog Programs into P (left-)linear 1-rule Components

  1995cites this paper
• Constraint Query Languages

  1995influential citation
• On symbolic scheduling and parallel complexity of loops

  1995cites this paper
• Undecidable Boundedness Problems for Datalog Programs

  1995cites this paper
• Linearizing Some Recursive Logic Programs

  1995influential citation
• Universal finiteness and satisfiability (extended abstract)

  1994cites this paper
• On the parallel complexity of model checking in the modal mu-calculus

  1994influential citation
• Universal Finiteness and Satissability

  1994cites this paper
• On the Parallel Complexity of Solving Recurrence Equations

  1994cites this paper
• Parallel Computational Complexity and Date-Transfer Complexity of Supercomputing

  1994cites this paper
• Must we solve the binding problem in neural hardware?

  1993cites this paper
• Not all reflexive reasoning is deductive

  1993cites this paper
• On the artificial intelligence paradox

  1993cites this paper
• Self-organizing neural models of categorization, inference and synchrony

  1993cites this paper
• Useful ideas for exploiting time to engineer representations

  1993cites this paper
• A step toward modeling reflexive reasoning

  1993cites this paper
• Making a middling mousetrap

  1993cites this paper
• Could static binding suffice?

  1993cites this paper
• From simple associations to systematic reasoning: A connectionist representation of rules, variables and dynamic bindings using temporal synchrony

  1993cites this paper
• Logical Query Optimization by Proff-Tree Transformation

  1993cites this paper
• Phase logic is biologically relevant logic

  1993cites this paper
• Plausible inference and implicit representation

  1993cites this paper
• Toward a unified behavioral and brain science

  1993cites this paper
• What we know and the LTKB

  1993cites this paper