The parallel complexity of simple logic programs

ABSTRACT

We consider logic programs with a single recursive rules, whose right-hand side consists of binary relations forming a chain. We give a complete characterization of all programs of this form that are computable in NC (assuming that P ≠ ). Our proof uses ideas from automata and language theory, and the combinatorics of strings.

REFERENCES

• 1: ~BABES, E. AND PAGOURTZIS, A. Parallel Complexity of Logic Programs. Diploma Thesis, ~National Technical University of Athens, Athens, Greece, 1989, pp. 280-293.
• 2: S Cosmadakis , P Kanellakis, Parallel evaluation of recursive rule queries, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.280-293, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15421]
• 3: ~GAIFMAN, E., MAIRSON, H., SAGIV, Y., AND VARDI, M. Undecidable optimization problems ~for database logic programs. In Proceedings os~ the 1987 Symposium oil Logic in Computer ~Sctence. IEEE, New York, 1987, pp. 106-115.
• 4: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 5: Neil Immerman, Relational queries computable in polynomial time, Information and Control, v.68 n.1-3, p.86-104, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80029-8]
• 6: ~KANELLAKIS, P. C. AND PAPADIMITRIOU, C.H. unpubhshed manuscript, 1987.
• 7: Harry R. Lewis , Christos H. Papadimitriou , Christos Papadimitriou, Elements of the Theory of Computation, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 8: ~PAPADIMITRIOU, C.H. On the expressive power of PROLOG. Bull EATCS. June 1985.
• 9: ~ULLM~,N, J. D. AND VAN GELDER, A. Parallel complexity of logical query programs. ,4Igonth- ~mica 3, I (1988), 5-42.
• 10: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming; Recursive function theory

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

General Terms:
Algorithms, Languages, Theory

Keywords:
NC, P-completeness, automaton, polynomial fringe, polynomial stock, pushdown