The IRMA Community
Newsletters
Research IRM
Click a keyword to search titles using our InfoSci-OnDemand powered search:
|
On the Implementation of a Logic Language for NP Search and Optimization Problems
|
|
Author(s): Sergio Greco (University of Calabria, Italy), Cristian Molinaro (University of Calabria, Italy), Irina Trubitsyna (University of Calabria, Italy)and Ester Zumpano (University of Calabria, Italy)
Copyright: 2009
Pages: 7
Source title:
Handbook of Research on Innovations in Database Technologies and Applications: Current and Future Trends
Source Author(s)/Editor(s): Viviana E. Ferraggine (UNICEN, Argentina), Jorge Horacio Doorn (UNICEN, Argentina)and Laura C. Rivero (UNICEN, Argentina)
DOI: 10.4018/978-1-60566-242-8.ch084
Purchase
|
Abstract
It is well known that NP search and optimization problems can be formulated as DATALOG¬ (datalog with unstratified negation; Abiteboul, Hull, & Vianu, 1994) queries under nondeterministic stable-model semantics so that each stable model corresponds to a possible solution (Gelfond & Lifschitz, 1988; Greco & Saccà, 1997; Kolaitis & Thakur, 1994). Although the use of (declarative) logic languages facilitates the process of writing complex applications, the use of unstratified negation allows programs to be written that in some cases are neither intuitive nor efficiently valuable. This article presents the logic language NP Datalog, a restricted version of DATALOG¬ that admits only controlled forms of negation, such as stratified negation, exclusive disjunction, and constraints. NP Datalog has the same expressive power as DATALOG¬, enables a simpler and intuitive formulation for search and optimization problems, and can be easily translated into other formalisms. The example below shows how the vertex cover problem can be expressed in NP Datalog.
Related Content
|
Renjith V. Ravi, Mangesh M. Ghonge, P. Febina Beevi, Rafael Kunst.
© 2022.
24 pages.
|
|
Manimaran A., Chandramohan Dhasarathan, Arulkumar N., Naveen Kumar N..
© 2022.
20 pages.
|
|
Ram Singh, Rohit Bansal, Sachin Chauhan.
© 2022.
19 pages.
|
|
Subhodeep Mukherjee, Manish Mohan Baral, Venkataiah Chittipaka.
© 2022.
17 pages.
|
|
Vladimir Nikolaevich Kustov, Ekaterina Sergeevna Selanteva.
© 2022.
23 pages.
|
|
Krati Reja, Gaurav Choudhary, Shishir Kumar Shandilya, Durgesh M. Sharma, Ashish K. Sharma.
© 2022.
18 pages.
|
|
Nwosu Anthony Ugochukwu, S. B. Goyal.
© 2022.
23 pages.
|
|
|