Abstract
Recently Modular Nonmonotonic Logic Programs (MLP) have been introduced which incorporate a call-by-value mechanism and allow for unrestricted calls between modules, including mutual and self recursion, as an approach to provide module constructs akin to those in conventional programming in Nonmonotonic Logic Programming under Answer Set Semantics. This paper considers MLPs in a Datalog setting and provides characterizations of their answers sets in terms of classical (Herbrand) models of a first-order formula, extending a line of research for ordinary logic programs. To this end, we lift the well-known loop formulas method to MLPs, and we also consider the recent ordered completion approach that avoids explicit construction of loop formulas using auxiliary predicates. Independent of computational perspectives, the novel characterizations widen our understanding of MLPs and they may prove useful for semantic investigations.
This research has been supported by the Austrian Science Fund (FWF) project P20841 and the Vienna Science and Technology Fund (WWTF) project ICT-08 20.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Apt, K., Blair, H., Walker, A.: Towards a Theory of Declarative Knowledge. In: Foundations of Deductive Databases and Logic Programming, pp. 89–148. Morgan Kaufmann, San Francisco (1988)
Arni, F., et al.: The deductive database system LDL++. Theor. Pract. Log. Prog. 3(1), 61–94 (2003)
Asuncion, V., Lin, F., Zhang, Y., Zhou, Y.: Ordered completion for first-order logic programs on finite structures. In: AAAI 2010, pp. 249–254. AAAI Press, Menlo Park (2010)
Chen, X., Ji, J., Lin, F.: Computing loops with at most one external support rule for disjunctive logic programs. In: Hill, P.M., Warren, D.S. (eds.) ICLP 2009. LNCS, vol. 5649, pp. 130–144. Springer, Heidelberg (2009)
Clark, K.L.: Negation as failure. In: Logic and Data Bases, pp. 293–322 (1978)
Dao-Tran, M., Eiter, T., Fink, M., Krennwallner, T.: Modular Nonmonotonic Logic Programming Revisited. In: Hill, P.M., Warren, D.S. (eds.) ICLP 2009. LNCS, vol. 5649, pp. 145–159. Springer, Heidelberg (2009)
Eiter, T., Gottlob, G., Mannila, H.: Disjunctive Datalog. ACM T. Database Syst. 22(3), 364–417 (1997)
Eiter, T., Gottlob, G., Veith, H.: Modular Logic Programming and Generalized Quantifiers. In: Fuhrbach, U., Dix, J., Nerode, A. (eds.) LPNMR 1997. LNCS, vol. 1265, pp. 290–309. Springer, Heidelberg (1997)
Eiter, T., Leone, N., Saccà, D.: On the Partial Semantics for Disjunctive Deductive Databases. Ann. Math. Artif. Intell. 19(1/2), 59–96 (1997)
Faber, W.: Unfounded sets for disjunctive logic programs with arbitrary aggregates. In: Baral, C., Greco, G., Leone, N., Terracina, G. (eds.) LPNMR 2005. LNCS (LNAI), vol. 3662, pp. 40–52. Springer, Heidelberg (2005)
Faber, W., Leone, N., Pfeifer, G.: Semantics and complexity of recursive aggregates in answer set programming. Artif. Intell. 175(1), 278–298 (2011)
Ferraris, P., Lee, J., Lifschitz, V.: A generalization of the Lin-Zhao theorem. Ann. Math. Artif. Intell. 47(1-2), 79–101 (2006)
Gaifman, H., Shapiro, E.: Fully abstract compositional semantics for logic programs. In: POPL 1989, pp. 134–142. ACM, New York (1989)
Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Generat. Comput. 9(3-4), 365–385 (1991)
Janhunen, T., Oikarinen, E., Tompits, H., Woltran, S.: Modularity Aspects of Disjunctive Stable Models. J. Artif. Intell. Res. 35, 813–857 (2009)
Lee, J., Lifschitz, V.: Loop formulas for disjunctive logic programs. In: Palamidessi, C. (ed.) ICLP 2003. LNCS, vol. 2916, pp. 451–465. Springer, Heidelberg (2003)
Lee, J., Meng, Y.: On reductive semantics of aggregates in answer set programming. In: Erdem, E., Lin, F., Schaub, T. (eds.) LPNMR 2009. LNCS, vol. 5753, pp. 182–195. Springer, Heidelberg (2009)
Lifschitz, V., Turner, H.: Splitting a Logic Program. In: ICLP 1994, pp. 23–38. MIT-Press, Cambridge (1994)
Lin, F., Zhao, Y.: ASSAT: computing answer sets of a logic program by SAT solvers. Artif. Intell. 157(1-2), 115–137 (2004)
Ross, K.: Modular Stratification and Magic Sets for Datalog Programs with Negation. J. ACM 41(6), 1216–1267 (1994)
Truszczyński, M.: Reducts of propositional theories, satisfiability relations, and generalizations of semantics of logic programs. Artif. Intell. 174(16-17), 1285–1306 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dao-Tran, M., Eiter, T., Fink, M., Krennwallner, T. (2011). First-Order Encodings for Modular Nonmonotonic Datalog Programs. In: de Moor, O., Gottlob, G., Furche, T., Sellers, A. (eds) Datalog Reloaded. Datalog 2.0 2010. Lecture Notes in Computer Science, vol 6702. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24206-9_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-24206-9_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24205-2
Online ISBN: 978-3-642-24206-9
eBook Packages: Computer ScienceComputer Science (R0)