Vladimir Lifschitz
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 ⊈ NC1 / 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.
- Clark, K. 1978. Negation as failure. In Logic and Data Bases. H. Gallaire and J. Minker, eds. Plenum Press, New York, 293--322.Google Scholar
- Cook, S. A. 1974. An observation on time-storage trade-off. J. Comput. System Sciences 9, 3, 308--316.Google ScholarDigital Library
- Eiter, T. and Gottlob, G. 1993. Complexity results for disjunctive logic programming and application to nonmonotonic logics. In Proceedings of the International Logic Programming Symposium (ILPS), D. Miller, ed. 266--278. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. 1995. Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Google ScholarDigital Library
- Inoue, K. and Sakama, C. 1998. Negation as failure in the head. J. Logic Programming 35, 39--78.Google ScholarCross Ref
- Jones, N. D. 1975. Space-Bounded reducibility among combinatorial problems. J. Comput. System Sciences 11, 68--85.Google ScholarDigital Library
- Lee, J. and Lifschitz, V. 2003. Loop formulas for disjunctive logic programs. In Proceedings of the International Conference on Logic Programming (ICLP). 451--465.Google Scholar
- Lifschitz, V., Tang, L. R., and Turner, H. 1999. Nested expressions in logic programs. Ann. Math. Artificial Intelligence 25, 369--389. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Lin, F. and Zhao, Y. 2002. ASSAT: Computing answer sets of a logic program by SAT solvers. In Proceedings of the National Conference on Artificial Intelligence (AAAI). 112--117. Google ScholarDigital Library
- Marek, V. and Truszczyński, M. 1991. Autoepistemic logic. J. ACM 38, 588--619. Google ScholarDigital Library
- Niemelä, I., Simons, P., and Soininen, T. 2002. Extending and implementing the stable model semantics. Artificial Intelligence 138, 181--234. Google ScholarDigital Library
- Reiter, R. 1980. A logic for default reasoning. Artificial Intelligence 13, 81--132.Google ScholarDigital Library
- 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.Google Scholar
Index Terms
- Why are there so many loop formulas?
Recommendations
Loop formulas for circumscription
Clark's completion is a simple nonmonotonic formalism and a special case of several nonmonotonic logics. Recently there has been work on extending completion with ''loop formulas'' so that general cases of nonmonotonic logics such as logic programs (...
Loop Formulas for Alog Answer Set Programs
CSAI '17: Proceedings of the 2017 International Conference on Computer Science and Artificial IntelligenceLogic programming based on answer set semantics, coined Answer Set Programming, is an important declarative problem solving paradigm. It has been widely used in various fields, such as artificial intelligence, bioinformatics, linguistics and so forth. ...
Loop formulas for description logic programs
Description Logic Programs (dl-programs) proposed by Eiter et al. constitute an elegant yet powerful formalism for the integration of answer set programming with description logics, for the Semantic Web. In this paper, we generalize the notions of ...
Comments