More Web Proxy on the site http://driver.im/

article

Bringing existential variables in answer set programming and bringing non-monotony in existential rules: two sides of the same coin

Authors:

Jean-François Baget,

Laurent Garcia,

Fabien Garreau,

Claire Lefèvre,

Igor StéphanAuthors Info & Claims

Annals of Mathematics and Artificial Intelligence, Volume 82, Issue 1-3

Pages 3 - 41

https://doi.org/10.1007/s10472-017-9563-9

Published: 01 March 2018 Publication History

Abstract

This article deals with the combination of ontologies and rules by means of existential rules and answer set programming. Existential rules have been proposed for representing ontological knowledge, specifically in the context of Ontology- Based Data Access. Furthermore Answer Set Programming (ASP) is an appropriate formalism to represent various problems issued from Artificial Intelligence and arising when available information is incomplete. The combination of the two formalisms requires to extend existential rules with nonmonotonic negation and to extend ASP with existential variables. In this article, we present the syntax and semantics of Existential Non Monotonic Rules (ENM-rules) using skolemization which join together the two frameworks. We formalize its links with standard ASP. Moreover, since entailment with existential rules is undecidable, we present conditions that ensure the termination of a breadth-first forward chaining algorithm known as the chase and we discuss extension of these results in the nonmonotonic case.

References

[1]

Ahmetaj, S., Ortiz, M., Simkus, M.: Polynomial datalog rewritings for expressive description logics with closed predicates. In: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, pp. 878---885. New York (2016)

[2]

Alviano, M., Morak, M., Pieris, A.: Stable model semantics for tuple-generating dependencies revisited. In: Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, pp. 377---388. Chicago (2017)

[3]

Baader, F., Brandt, S., Lutz, C.: Pushing the el envelope. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI'05, pp. 364---369. Morgan Kaufmann Publishers Inc, San Francisco (2005)

Digital Library

[4]

Baget, J.-F., Leclère, M., Mugnier, M.-L., Salvat, E.: On rules with existential variables: walking the decidability line. Artif. Intell. 175(9---10), 1620---1654 (2011)

[5]

Baget, J.-F., Mugnier, M.-L.: The complexity of rules and constraints. J. Artif. Intell. Res. (JAIR) 16, 425---465 (2002)

Digital Library

[6]

Baget, J.-F.: Ontologies and large databases: Querying algorithms for the Web of Data. Invited Talk, Artificial Intelligence meets the Web of Data. ESWC'13 Workshop (2013)

[7]

Baget, J.-F.: Improving the forward chaining algorithm for conceptual graphs rules. In: Principles of Knowledge Representation and Reasoning: Proceedings of the Ninth International Conference (KR2004), pp. 407---414. Whistler (2004)

Digital Library

[8]

Baget, J.-F., Garreau, F., Mugnier, M.-L., Rocher, S.: Extending acyclicity notions for existential rules. In: ECAI 2014 - 21st European Conference on Artificial Intelligence, pp. 39---44. Prague (2014)

[9]

Baget, J.-F., Garreau, F., Mugnier, M.-L., Rocher, S.: Revisiting chase termination for existential rules and their extension to nonmonotonic negation. In: Konieczny, S., Tompits, H. (eds.) NMR'2014: 15th International Workshop on Non-Monotonic Reasoning, Volume INFSYS Research Report Series, Vienna (2014)

[10]

Baget, J.-F., Leclère, M., Mugnier, M.-L., Salvat, E.: Extending decidable cases for rules with existential variables. In: IJCAI'09: 21st International Joint Conference on Artificial Intelligence, pp. 677---682. AAAI, Pasadena (2009)

[11]

Baral, C.: Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press (2003)

[12]

Beeri, C., Vardi, M.Y.: The implication problem for data dependencies. In: Automata, Languages and Programming, 8th Colloquium, Acre (Akko). Proceedings, pp. 73---85. Israel (1981)

[13]

Calì, A., Gottlob, G., Kifer, M.: Taming the infinite chase: Query answering under expressive relational constraints. In: KR'08, pp. 70---80 (2008)

[14]

Calì, A., Gottlob, G., Lukasiewicz, T.: A general datalog-based framework for tractable query answering over ontologies. In: PODS'09, pp. 77---86 (2009)

Digital Library

[15]

Calì, A., Gottlob, G., Lukasiewicz, T.: Tractable query answering over ontologies with datalog+/-. In: Proceedings of the 22nd International Workshop on Description Logics (DL-2009) (2009)

[16]

Calimeri, F., Cozza, S., Ianni, G., Leone, N.: Computable functions in ASP: Theory and implementation. In: Logic Programming, 24th International Conference, ICLP 2008. Proceedings, pp. 407---424. Udine (2008)

[17]

Calvanese, D., Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: The dl-lite family. J. Autom. Reas. 39(3), 385---429 (2007)

Digital Library

[18]

Chandra, A.K., Lewis, H.R., Makowsky, J.A.: Embedded implicational dependencies and their inference problem. In: Proceedings of the 13th Annual ACM Symposium on Theory of Computing, pp. 342---354. Milwaukee (1981)

[19]

de Bruijn, J., Pearce, D., Polleres, A., Valverde, A.: A semantical framework for hybrid knowledge bases. Knowl. Inf. Syst. 25(1), 81---104 (2010)

Digital Library

[20]

Deutsch, A., Nash, A., Remmel, J.B.: The chase revisited. In: PODS'08, pp. 149---158 (2008)

Digital Library

[21]

Eiter, T., Ianni, G., Lukasiewicz, T., Schindlauer, R., Tompits, H.: Combining answer set programming with description logics for the semantic web. Artif. Intell. 172(12---13), 1495---1539 (2008)

[22]

Fagin, R., Kolaitis, P.G., Miller, R.J., Popa, L.: Data exchange: Semantics and query answering. Theor. Comput. Sci. 336(1), 89---124 (2005)

Digital Library

[23]

Fagin, R., Kolaitis, P.G., Miller, R.J., Popa, L.: Data exchange: Semantics and query answering. In: Database Theory - ICDT 2003, 9th International Conference. Proceedings, pp. 207---224. Siena (2003)

[24]

Ferraris, P., Lee, J., Lifschitz, V.: Stable models and circumscription. Artif. Intell. 175, 236---263 (2011)

Digital Library

[25]

Garreau, F., Garcia, L., Lefèvre, C., Stéphan, I.: ?-asp. In: Proceedings of the Ontologies and Logic Programming for Query Answering workshop (ONTOLP'15). Buenos Aires (2015)

[26]

Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: Kowalski, R.A., Bowen, K. (eds.) Proceedings of the Fifth International Conference and Symposium on Logic Programming (ICLP'88), pp. 1070---1080. The MIT Press, Cambridge (1988)

[27]

Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. Gen. Comput. 9(3/4), 365---386 (1991)

[28]

Gottlob, G., Hernich, A., Kupke, C., Lukasiewicz, T.: Equality-friendly well-founded semantics and applications to description logics. In: Hoffmann, J., Selman, B. (eds.) Proceedings of the 26th National Conference on Artificial Intelligence, AAAI 2012. AAAI Press, Toronto (2012)

[29]

Grau, B.C., Horrocks, I., Krötzsch, M., Kupke, C., Magka, D., Motik, B., Wang, Z.: Acyclicity conditions and their application to query answering in description logics. In: Brewka, G., Eiter, T., McIlraith, S.A. (eds.) Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, KR 2012. AAAI Press, Rome (2012)

[30]

Grau, B.C., Horrocks, I., Kro?tzsch, M., Kupke, C., Magka, D., Motik, B., Wang, Z.: Acyclicity notions for existential rules and their application to query answering in ontologies. J. Artif. Intell. Res. (JAIR) 47, 741---808 (2013)

Digital Library

[31]

Heymans, S., Nieuwenborgh, D.V., Vermeir, D.: Open answer set programming for the semantic web. J. Appl. Logic 5(1), 144---169 (2007). Questions and Answers: Theoretical and Applied Perspectives

[32]

Ianni, G., Eiter, T., Tompits, H., Schindlauer, R.: Nlp-dl: A kr system for coupling nonmonotonic logic programs with description logics. In: The Forth International Semantic Web Conference (ISWC2005) (2005)

[33]

Kro?tzsch, M., Rudolph, S.: Extending decidable existential rules by joining acyclicity and guardedness. In: IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, pp. 963---968. Barcelona (2011)

[34]

Lee, J., Palla, R.: Integrating rules and ontologies in the first-order stable model semantics (preliminary report). In: Logic Programming and Nonmonotonic Reasoning - 11th International Conference, LPNMR 2011. Proceedings, pp. 248---253. Vancouver (2011)

[35]

Lefèvre, C., Nicolas, P.: A first order forward chaining approach for answer set computing. In: Proceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09), volume 5753 of LNCS, pp. 196---208. Springer (2009)

[36]

Lefă?vre, C., Bă?atrix, C., Stă?phan, I., Garcia, L.: ASPeRiX, a first order forward chaining approach for answer set computing. In: Theory and Practice of Logic Programming, vol. 17, no. 3, pp. 266---310 (2017)

[37]

Leone, N., Manna, M., Terracina, G., Veltri, P.: Efficiently computable datalog? programs. In: Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, KR 2012. Rome (2012)

[38]

Lierler, Y., Lifschitz, V.: One more decidable class of finitely ground programs. In: Logic Programming, 25th International Conference, ICLP 2009. Proceedings, pp. 489---493. Pasadena (2009)

[39]

Liu, L., Pontelli, E., Son, T.C., Truszczynski, M.: Logic programs with abstract constraint atoms: The role of computations. Artif. Intell. 174(3-4), 295---315 (2010)

Digital Library

[40]

Magka, D., Kro?tzsch, M., Horrocks, I.: Computing stable models for nonmonotonic existential rules. In: IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence. Beijing (2013)

[41]

Marnette, B.: Generalized schema-mappings: From termination to tractability. In: PODS, pp. 13---22 (2009)

Digital Library

[42]

Motik, B., Rosati, R.: Reconciling description logics and rules. J. ACM, 57(5) (2010)

Digital Library

[43]

Mugnier, M.-L.: Ontological query answering with existential rules. In: Web Reasoning and Rule Systems - 5th International Conference, RR 2011Proceedings, pp. 2---23. Galway (2011)

[44]

Rocher, S.: Querying Existential Rule Knowledge Bases: Decidability and Complexity. PhD thesis, Université de Montpellier, France (2016)

[45]

Rosati, R.: Dl+log: Tight integration of description logics and disjunctive datalog. In: Proceedings, Tenth International Conference on Principles of Knowledge Representation and Reasoning, pp. 68---78. Lake District of the United Kingdom (2006)

[46]

Salvat, E., Mugnier, M.-L.: Sound and complete forward and backward chainingd of graph rules. In: Eklund, P.W., Ellis, G., Mann, G. (eds.) Conceptual Structures: Knowledge Representation as Interlingua, 4th International Conference on Conceptual Structures, ICCS '96. Proceedings, Volume 1115 of Lecture Notes in Computer Science, pp. 248---262. Springer, Sydney (1996)

[47]

Wan, H., Zhang, H., Xiao, P., Huang, H., Zhang, Y.: Query answering with inconsistent existential rules under stable model semantics. In: Schuurmans, D., Wellman, M.P. (eds.) Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pp. 1095---1101. AAAI Press, Phoenix (2016)

Cited By

Gottlob GHernich AKupke CLukasiewicz T(2021)Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and ComplexityJournal of the ACM10.1145/344750868:5(1-87)Online publication date: 22-Oct-2021
https://dl.acm.org/doi/10.1145/3447508
Garcia LLefèvre CPapini OStéphan IWürbel É(2018)Possibilistic ASP base revision by certain inputProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304889.3304912(1824-1830)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304889.3304912

Bringing existential variables in answer set programming and bringing non-monotony in existential rules: two sides of the same coin
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
2. Theory of computation
  1. Logic

Recommendations

Evaluating epistemic negation in answer set programming

Epistemic negation not along with default negation plays a key role in knowledge representation and nonmonotonic reasoning. However, the existing epistemic approaches such as those by Gelfond 13,15,14, Truszczynski 33 and Kahl et al. 18 behave not ...
From answer set logic programming to circumscription via logic of GK

We first embed Pearce's equilibrium logic and Ferraris's propositional general logic programs in Lin and Shoham's logic of GK, a nonmonotonic modal logic that has been shown to include as special cases both Reiter's default logic in the propositional ...
Combining answer set programming with description logics for the Semantic Web

We propose a combination of logic programming under the answer set semantics with the description logics SHIF(D) and SHOIN(D), which underly the Web ontology languages OWL Lite and OWL DL, respectively. To this end, we introduce description logic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Annals of Mathematics and Artificial Intelligence

Annals of Mathematics and Artificial Intelligence Volume 82, Issue 1-3

March 2018

182 pages

ISSN:1012-2443

Issue’s Table of Contents

Copyright © Copyright © 2018 Springer International Publishing AG, part of Springer Nature.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 March 2018

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gottlob GHernich AKupke CLukasiewicz T(2021)Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and ComplexityJournal of the ACM10.1145/344750868:5(1-87)Online publication date: 22-Oct-2021
https://dl.acm.org/doi/10.1145/3447508
Garcia LLefèvre CPapini OStéphan IWürbel É(2018)Possibilistic ASP base revision by certain inputProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304889.3304912(1824-1830)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304889.3304912

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents