Greedy by choice

ABSTRACT

The greedy paradigm of algorithm design is a well known tool used for efficiently solving many classical computational problems within the framework of procedural languages. However, it is very difficult to express these algorithms within the declarative framework of logic-based languages. In this paper, we extend the framework of Datalog-like languages to provide simple and declarative formulations of such problems, with computational complexities comparable to those of procedural formulations. This is achieved through the use of constructs, such as least and choice, that have semantics reducible to that of negative programs under stable model semantics. Therefore, we show that the formulation of greedy algorithms using these constructs lead to a syntactic class of programs, called stage-stratified programs, that are easily recognized at compile time. The fixpoint-based implementation of these recursive programs is very efficient and, combined with suitable storage structures, yields asymptotic complexities comparable to those obtained using procedural languages.

REFERENCES

• 1: Sumit Ganguly , Sergio Greco , Carlo Zaniolo, Minimum and maximum predicates in logic programming, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.154-163, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113427]
• 2: S. Ganguly, S. Greco, and C. Zaniolo. Greedy algorithms in deductive databsases. Research report, in preparation, UCLA, 1992.
• 3: M. Gelfond and V. Lifschitz. The stable model semantics of logic programming. In Proceedings of the Fifth Intern. Conference on Logic Programming, pages 1070-1080, 1988.
• 4: F. Giannotti, D. Pedreschi, D. Sacc~, and C. Zaniolo. Nondeterminism in deductive databases. In Proc. 2nd Int. Conf. on Deductive and Object- Oriented Databases, 1991.
• 5: P. Helmann, B.M.E. Moret, and H.D. Shapiro. Exact caracterization of greedy structures. Research Report CS89-11, Univ. of New Mexico, 1989.
• 6: B. Korte and L. Lovhsz. Greedoids- a structural framework for the greedy algorithm, in W. R. Pulleyblank, editor, Progress in Combinatorial Optimization, pages 221-243. Academic Press, 1984.
• 7: R. Krishnamurthy and S. Naqvi. Non-deterministic choice in Datalog. In Proceedings of the 3rd International Conference on Data and Knowledge Bases, 1988.
• 8: T. C. Przymusinski, On the declarative semantics of deductive databases and logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 9: Domenico Sacca , Carlo Zaniolo, Stable models and non-determinism in logic programs with negation, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.205-217, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298572]
• 10: D. Sacck and C. Zaniolo. Deterministic versus nondeterministics semantics in deductive databases. In Submitted for Pubblication, 1991.
• 11: Allen Van Gelder , Kenneth A. Ross , John S. Schlipf, The well-founded semantics for general logic programs, Journal of the ACM (JACM), v.38 n.3, p.619-649, July 1991 [doi>10.1145/116825.116838]
• 12: D.J.A. Welsh, editor. Matroid Theory. Academic Press, 1976.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Languages