Abstract
Open answer set programming (OASP) is an extension of answer set programming where one may ground a program with an arbitrary superset of the program’s constants. We define a fixed point logic (FPL) extension of Clark’s completion such that open answer sets correspond to models of FPL formulas and identify a syntactic subclass of programs, called (loosely) guarded programs. Whereas reasoning with general programs in OASP is undecidable, the FPL translation of (loosely) guarded programs falls in the decidable (loosely) guarded fixed point logic (μ(L)GF).
Moreover, we reduce normal closed ASP to loosely guarded OASP, enabling a characterization of an answer set semantics by μLGF formulas. Finally, we relate guarded OASP to Datalog LITE, thus linking an answer set semantics to a semantics based on fixed point models of extended stratified Datalog programs. From this correspondence, we deduce 2-EXPTIME-completeness of satisfiability checking w.r.t. (loosely) guarded programs.
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
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)
Andréka, H., Németi, I., Van Benthem, J.: Modal Languages and Bounded Fragments of Predicate Logic. J. of Philosophical Logic 27(3), 217–274 (1998)
Baral, C.: Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge Press, Cambridge (2003)
Van Benthem, J.: Dynamic Bits and Pieces. ILLC research report. University of Amsterdam (1997)
Chandra, A.K., Harel, D.: Horn Clauses and the Fixpoint Query Hierarchy. In: Proc. of PODS 1982, pp. 158–163. ACM Press, New York (1982)
Clark, K.L.: Negation as Failure. In: Readings in Nonmonotonic Reasoning, pp. 311–325. Kaufmann, San Francisco (1987)
Dantsin, E., Eiter, T., Gottlob, G., Voronkov, A.: Complexity and Expressive Power of Logic Programming. ACM Comput. Surv. 33(3), 374–425 (2001)
Emerson, E.A., Clarke, E.M.: Using Branching Time Temporal Logic to Synthesize Synchronization Skeletons. Sciene of Computer Programming 2(3), 241–266 (1982)
Faber, W., Leone, N., Pfeifer, G.: Pushing Goal Derivation in DLP Computations. In: Gelfond, M., Leone, N., Pfeifer, G. (eds.) LPNMR 1999. LNCS (LNAI), vol. 1730, pp. 177–191. Springer, Heidelberg (1999)
Gelfond, M., Lifschitz, V.: The Stable Model Semantics for Logic Programming. In: Proc. of ICLP 1988, pp. 1070–1080. MIT Press, Cambridge (1988)
Gelfond, M., Przymusinska, H.: Reasoning in Open Domains. In: Logic Programming and Non-Monotonic Reasoning, pp. 397–413. MIT Press, Cambridge (1993)
Gottlob, G., Grädel, E., Veith, H.: Datalog LITE: A deductive query language with linear time model checking. ACM Transactions on Computational Logic 3(1), 1–35 (2002)
Grädel, E.: On the Restraining Power of Guards. Journal of Symbolic Logic 64(4), 1719–1742 (1999)
Grädel, E., Walukiewicz, I.: Guarded Fixed Point Logic. In: Proc. of LICS 1999, pp. 45–54. IEEE Computer Society, Los Alamitos (1999)
Heymans, S., Van Nieuwenborgh, D., Vermeir, D.: Guarded Open Answer Set Programming. Technical report, http://tinf2.vub.ac.be/~sheymans/tech/guarded-oasp.ps.gz
Heymans, S., Van Nieuwenborgh, D., Vermeir, D.: Semantic Web Reasoning with Conceptual Logic Programs. In: Antoniou, G., Boley, H. (eds.) RuleML 2004. LNCS, vol. 3323, pp. 113–127. Springer, Heidelberg (2004)
Heymans, S., Van Nieuwenborgh, D., Vermeir, D.: Nonmonotonic Ontological and Rule-Based Reasoning with Extended Conceptual Logic Programs. In: Gómez-Pérez, A., Euzenat, J. (eds.) ESWC 2005. LNCS, vol. 3532, pp. 392–407. Springer, Heidelberg (2005)
Kozen, D.: Results on the Propositional μ-calculus. Theor. Comput. Sci. 27, 333–354 (1983)
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)
Lifschitz, V., Pearce, D., Valverde, A.: Strongly Equivalent Logic Programs. ACM Transactions on Computational Logic 2(4), 526–541 (2001)
Lin, F., Zhao, Y.: ASSAT: Computing Answer Sets of a Logic Program by SAT Solvers. In: Proc. of 18th National Conference on Artificial Intelligence, pp. 112–117. AAAI, Menlo Park (2002)
Syrjänen, T.: Omega-restricted Logic Programs. In: Eiter, T., Faber, W., Truszczyński, M. (eds.) LPNMR 2001. LNCS (LNAI), vol. 2173, pp. 267–279. Springer, Heidelberg (2001)
Syrjänen, T., Niemelä, I.: The smodels System. In: Eiter, T., Faber, W., Truszczyński, M. (eds.) LPNMR 2001. LNCS (LNAI), vol. 2173, pp. 434–438. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Heymans, S., Van Nieuwenborgh, D., Vermeir, D. (2005). Guarded Open Answer Set Programming. In: Baral, C., Greco, G., Leone, N., Terracina, G. (eds) Logic Programming and Nonmonotonic Reasoning. LPNMR 2005. Lecture Notes in Computer Science(), vol 3662. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11546207_8
Download citation
DOI: https://doi.org/10.1007/11546207_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28538-0
Online ISBN: 978-3-540-31827-9
eBook Packages: Computer ScienceComputer Science (R0)