NDLI: Predicate-calculus-based logics for modeling and solving search problems

Please wait, while we are loading the content...

Predicate-calculus-based logics for modeling and solving search problems

Content Provider	ACM Digital Library
Author	Truszczyński, Miroslaw East, Deborah
Copyright Year	2006
Abstract	The answer-set programming (ASP) paradigm is a way of using logic to solve search problems. Given a search problem, to solve it one designs a logic theory so that $\textit{models}$ of this theory represent problem solutions. To compute a solution to the problem, one computes a model of the theory. Several answer-set programming formalisms have been developed on the basis of logic programming with the semantics of answer sets. In this article we show that predicate logic also gives rise to effective implementations of the ASP paradigm, similar in spirit to logic programming with the answer-set semantics and with a similar scope of applicability. Specifically, we propose two logics based on predicate calculus as formalisms for encoding search problems. We show that the expressive power of these logics is given by the class NPMV. We demonstrate their use in programming and discuss computational approaches to model finding. To address this latter issue, we follow a two-pronged approach. On the one hand, we show that the problem can be reduced to that of computing models of propositional theories and, more generally, of collections of $\textit{pseudo-Boolean}$ constraints. Consequently, programs (solvers) developed in the areas of propositional and pseudo-Boolean satisfiability can be used to compute models of theories in our logics. On the other hand, we develop native solvers designed specifically to exploit features of our formalisms. We present experimental results demonstrating the computational effectiveness of the overall approach.
Starting Page	38
Ending Page	83
Page Count	46
File Format	PDF
ISSN	15293785
e-ISSN	1557945X
DOI	10.1145/1119439.1119441
Volume Number	7
Issue Number	1
Journal	ACM Transactions on Computational Logic (TOCL)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2006-01-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Satisfiability Constraints Predicate logic Pseudo-Boolean constraints Search problems
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Logic Computational Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Resource-distribution via Boolean constraints

Predicate-calculus based logics for modeling and solving search problems (2004).

Boolean satisfiability with transitivity constraints

Predicate-calculus based logics for modeling and solving search problems (2006)

Satisfiability Testing of Boolean Combinations of Pseudo-Boolean Constraints using Local-search Techniques

Tableau calculus for preference-based conditional logics: PCL and its extensions

Graded computation tree logic

Proof search specifications of bisimulation and modal logics for the π-calculus

B-Cubing: New Possibilities for Efficient SAT-Solving

Predicate-calculus-based logics for modeling and solving search problems

Similar Documents

Resource-distribution via Boolean constraints

Predicate-calculus based logics for modeling and solving search problems (2004).

Boolean satisfiability with transitivity constraints

Predicate-calculus based logics for modeling and solving search problems (2006)

Satisfiability Testing of Boolean Combinations of Pseudo-Boolean Constraints using Local-search Techniques

Tableau calculus for preference-based conditional logics: PCL and its extensions

Graded computation tree logic

Proof search specifications of bisimulation and modal logics for the π-calculus

B-Cubing: New Possibilities for Efficient SAT-Solving

Predicate-calculus-based logics for modeling and solving search problems