Abstract
Approximation Fixpoint Theory (AFT) is an algebraic framework for studying fixpoints of possibly nonmonotone lattice operators, and thus extends the fixpoint theory of Tarski and Knaster. In this paper, we uniformly define 2-, and 3-valued (ultimate) answer-set semantics, and well-founded semantics of disjunction-free Hex programs by applying AFT. In the case of disjunctive Hex programs, AFT is not directly applicable. However, we provide a definition of 2-valued (ultimate) answer-set semantics based on non-deterministic approximations and show that answer sets are minimal, supported, and derivable in terms of bottom-up computations. Finally, we extensively compare our semantics to closely related semantics, including constructive dl-program semantics. Since Hex programs are a generic formalism, our results are applicable to a wide range of formalisms.
This work was supported by the Austrian Science Fund (FWF) grant P24090.
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
Antić, C.: Uniform approximation-theoretic semantics for logic programs with external atoms. Master’s thesis, TU Vienna (2012), http://www.ub.tuwien.ac.at/dipl/2012/AC07814506.pdf
Baselice, S., Bonatti, P.A., Criscuolo, G.: On finitely recursive programs. TPLP 9(2), 213–238 (2009)
Cohen, R.S., Gold, A.Y.: ω-computations on Turing machines. TCS 6, 1–23 (1978)
Denecker, M., Bruynooghe, M., Vennekens, J.: Approximation fixpoint theory and the semantics of logic and answers set programs. In: Erdem, E., Lee, J., Lierler, Y., Pearce, D. (eds.) Correct Reasoning. LNCS, vol. 7265, pp. 178–194. Springer, Heidelberg (2012)
Denecker, M., Marek, V., Truszczyński, M.: Approximations, stable operators, well-founded fixpoints and applications in nonmonotonic reasoning. In: Minker, J. (ed.) Logic-Based Artificial Intelligence, pp. 127–144. Kluwer (2000)
Denecker, M., Marek, V., Truszczyński, M.: Uniform semantic treatment of default and autoepistemic logics. Artificial Intelligence, 79–122 (2003)
Denecker, M., Marek, V., Truszczyński, M.: Ultimate approximation and its application in nonmonotonic knowledge representation systems. Inf. Comp. 192(1), 84–121 (2004)
Eiter, T., Brewka, G., Dao-Tran, M., Fink, M., Ianni, G., Krennwallner, T.: Combining nonmonotonic knowledge bases with external sources. In: Ghilardi, S., Sebastiani, R. (eds.) FroCoS 2009. LNCS, vol. 5749, pp. 18–42. Springer, Heidelberg (2009)
Eiter, T., Ianni, G., Lukasiewicz, T., Schindlauer, R.: Well-founded semantics for description logic programs in the semantic web. ACM TOCL 12(2), 11:1–11:41 (2011)
Eiter, T., Ianni, G., Schindlauer, R., Tompits, H.: A uniform integration of higher-order reasoning and external evaluations in answer-set programming. In: Proc. IJCAI 2005, pp. 90–96 (2005)
Faber, W., Leone, N., Pfeifer, G.: Recursive aggregates in disjunctive logic programs: Semantics and complexity. In: Alferes, J.J., Leite, J. (eds.) JELIA 2004. LNCS (LNAI), vol. 3229, pp. 200–212. Springer, Heidelberg (2004)
Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Generation Computing 9(3-4), 365–385 (1991)
Lobo, J., Minker, J., Rajasekar, A.: Foundations of Disjunctive Logic Programming. MIT Press (1992)
Marek, V.W., Niemelä, I., Truszczyński, M.: Logic programs with monotone cardinality atoms. In: Lifschitz, V., Niemelä, I. (eds.) LPNMR 2004. LNCS (LNAI), vol. 2923, pp. 154–166. Springer, Heidelberg (2003)
Pelov, N., Truszczyński, M.: Semantics of disjunctive programs with monotone aggreggates - an operator-based approach. In: Proc. NMR 2004, pp. 327–334 (2004)
Pelov, N., Denecker, M., Bruynooghe, M.: Well-founded and stable semantics of logic programs with aggregates. Theory and Practice of Logic Programming 7(3), 301–353 (2007)
Przymusinski, T.: Well-founded semantics coincides with the three-valued stable semantics. Fundamenta Informaticae 13(4), 445–463 (1990)
Shen, Y.D.: Well-supported semantics for description logic programs. In: Proc. IJCAI 2011, pp. 1081–1086. AAAI Press (2011)
Smyth, M.B.: Power domains. Journal of Computer and System Sciences 16, 23–36 (1978)
Truszczyński, M.: Strong and uniform equivalence of nonmonotonic theories – an algebraic approach. Annals of Mathematics and Artificial Intelligence 48(3-4), 245–265 (2006)
Van Gelder, A., Ross, K.A., Schlipf, J.S.: The well-founded semantics for general logic programs. Journal of the ACM 38(3), 619–649 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Antić, C., Eiter, T., Fink, M. (2013). Hex Semantics via Approximation Fixpoint Theory. In: Cabalar, P., Son, T.C. (eds) Logic Programming and Nonmonotonic Reasoning. LPNMR 2013. Lecture Notes in Computer Science(), vol 8148. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40564-8_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-40564-8_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40563-1
Online ISBN: 978-3-642-40564-8
eBook Packages: Computer ScienceComputer Science (R0)