language: en

Greedy Algorithms in Datalog with Choice and Negation

Sergio Greco Carlo Zaniolo
Dip: Elettr: Informatica Sist: Computer Science Dept: Universita della Calabria Univ: of California at Los Angeles
87030 Rende; Italy LosAngeles; CA 90024
greco@si:deis:unical:it zaniolo@cs:ucla:edu

Abstract In the design of algorithms, the greedy paradigm provides a powerful tool for solving efficiently classical computational problems, within the framework of procedural languages. However, expressing these algorithms within the declarative framework of logic-based languages has proved to be a difficult research challenge. In this paper, we extend the framework of Datalog-like languages to obtain simple declarative formulations for such problems, and propose effective implementation techniques to ensure computational complexities comparable to those of procedural formulations. These advances are achieved through the use of the choice construct, that has semantics reducible to that of programs with negation under stable model semantics. Then we extend the fixpoint-based semantics of choice programs with preference annotations to guide search strategies and simple logic-based formulations of classical greedy algorithms.

1 Introduction