2009/11/14 by Sergio Greco, Greco, Sergio, Cristian Molinaro +5
Computer Science · #AI-based Problem Solving and Planning #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #cs.LO
paper · pdf · doi:10.48550/arxiv.0911.2785
To appear in Theory and Practice of Logic Programming (TPLP)
arxiv created 2009/11/14 · openalex publication_date 2009/11/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper presents a logic language for expressing NP search and optimization problems. Specifically, first a language obtained by extending (positive) Datalog with intuitive and efficient constructs (namely, stratified negation, constraints and exclusive disjunction) is introduced. Next, a further restricted language only using a restricted form of disjunction to define (non-deterministically) subsets (or partitions) of relations is investigated. This language, called NP Datalog, captures the power of Datalog with unstratified negation in expressing search and optimization problems. A system prototype implementing NP Datalog is presented. The system translates NP Datalog queries into OPL programs which are executed by the ILOG OPL Development Studio. Our proposal combines easy formulation of problems, expressed by means of a declarative logic language, with the efficiency of the ILOG System. Several experiments show the effectiveness of this approach.