Why are there so many loop formulas?

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Why are there so many loop formulas?

Full text

Pdf (91 KB)

Source

ACM Transactions on Computational Logic (TOCL) archive
Volume 7 , Issue 2 (April 2006) table of contents

Pages: 261 - 268

Year of Publication: 2006

ISSN:1529-3785

Authors

Vladimir Lifschitz	University of Texas at Austin, Austin, TX
Alexander Razborov	Institute for Advanced Study, Princeton, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 39, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1131313.1131316 What is a DOI?

ABSTRACT

A theorem by Lin and Zhao shows how to turn any nondisjunctive logic program, understood in accordance with the answer set semantics, into an equivalent set of propositional formulas. The set of formulas generated by this process can be significantly larger than the original program. In this article we show (assuming P ⊈ NC¹ / poly, a conjecture from the theory of computational complexity that is widely believed to be true) that this is inevitable: any equivalent translation from logic programs to propositional formulas involves a significant increase in size.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Clark, K. 1978. Negation as failure. In Logic and Data Bases. H. Gallaire and J. Minker, eds. Plenum Press, New York, 293--322.
	2	Cook, S. A. 1974. An observation on time-storage trade-off. J. Comput. System Sciences 9, 3, 308--316.
	3	Thomas Eiter , Georg Gottlob, Complexity results for disjunctive logic programming and application to nonmonotonic logics, Proceedings of the 1993 international symposium on Logic programming, p.266-278, December 1993, Vancouver, British Columbia, Canada
	4	Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proceedings of the International Logic Programming Conference and Symposium. R. Kowalski and K. Bowen, eds. 1070--1080.
	5	Gogic, G., Kautz, H., Papadimitriou, C., and Selman, B. 1995. The comparative linguistics of knowledge representation. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 862--869.
	6	Raymond Greenlaw , H. James Hoover , Walter L. Ruzzo, Limits to parallel computation: P-completeness theory, Oxford University Press, Inc., New York, NY, 1995
	7	Inoue, K. and Sakama, C. 1998. Negation as failure in the head. J. Logic Programming 35, 39--78.
	8	Jones, N. D. 1975. Space-Bounded reducibility among combinatorial problems. J. Comput. System Sciences 11, 68--85.
	9	Lee, J. and Lifschitz, V. 2003. Loop formulas for disjunctive logic programs. In Proceedings of the International Conference on Logic Programming (ICLP). 451--465.
	10	Vladimir Lifschitz , Lappoon R. Tang , Hudson Turner, Nested expressions in logic programs, Annals of Mathematics and Artificial Intelligence, v.25 n.3-4, p.369-389, 1999
	11	Lin, F. and Zhao, J. 2003. On tight logic programs and yet another translation from normal logic programs and propositional logic. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 853--864.
	12	Fangzhen Lin , Yuting Zhao, ASSAT: computing answer sets of a logic program by SAT solvers, Eighteenth national conference on Artificial intelligence, p.112-117, July 28-August 01, 2002, Edmonton, Alberta, Canada
	13	Wiktor Marek , Mirosław Truszczyński, Autoepistemic logic, Journal of the ACM (JACM), v.38 n.3, p.587-618, July 1991 [doi>10.1145/116825.116836]
	14	Patrik Simons , Ilkka Niemelá , Timo Soininen, Extending and implementing the stable model semantics, Artificial Intelligence, v.138 n.1-2, p.181-234, June 2002 [doi>10.1016/S0004-3702(02)00187-X ]
	15	Reiter, R. 1980. A logic for default reasoning. Artificial Intelligence 13, 81--132.
	16	Spira, P. M. 1971. On time-hardware complexity tradeoffs for Boolean functions. In Proceedings of the 4th Hawaii Symposium on System Sciences. Western Periodicals Company, North Hollywood, 525--527.