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

research-article

Stratification in Approximation Fixpoint Theory and Its Application to Active Integrity Constraints

Authors:

Luís Cruz-FilipeAuthors Info & Claims

ACM Transactions on Computational Logic (TOCL), Volume 22, Issue 1

Article No.: 6, Pages 1 - 19

https://doi.org/10.1145/3430750

Published: 05 January 2021 Publication History

Abstract

Approximation fixpoint theory (AFT) is an algebraic study of fixpoints of lattice operators that unifies various knowledge representation formalisms. In AFT, stratification of operators has been studied, essentially resulting in a theory that specifies when certain types of fixpoints can be computed stratum per stratum. Recently, novel types of fixpoints related to groundedness have been introduced in AFT. In this article, we study how those fixpoints behave under stratified operators.

One recent application domain of AFT is the field of active integrity constraints (AICs). We apply our extended stratification theory to AICs and find that existing notions of stratification in AICs are covered by this general algebraic definition of stratification. As a result, we obtain stratification results for a large variety of semantics for AICs.

References

[1]

Serge Abiteboul. 1988. Updates, a new frontier. In Proceedings of the 2nd International Conference on Database Theory. (Lecture Notes in Computer Science), Marc Gyssens, Jan Paredaens, and Dirk Van Gucht (Eds.), Vol. 326. Springer, 1--18.

[2]

Christian Antic, Thomas Eiter, and Michael Fink. 2013. Hex semantics via approximation fixpoint theory. In Proceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’13). (LNCS), Pedro Cabalar and Tran Cao Son (Eds.), Vol. 8148. Springer, 102--115.

Digital Library

[3]

Bart Bogaerts. 2015. Groundedness in Logics with a Fixpoint Semantics. Ph.D. Dissertation. Department of Computer Science, KU Leuven. Retrieved from https://lirias.kuleuven.be/handle/123456789/496543.

[4]

Bart Bogaerts and Luís Cruz-Filipe. 2018. Fixpoint semantics for active integrity constraints. Artif. Intell. 255 (2018), 43--70.

[5]

Bart Bogaerts, Joost Vennekens, and Marc Denecker. 2015a. Grounded fixpoints and their applications in knowledge representation. Artif. Intell. 224 (2015), 51--71.

Digital Library

[6]

Bart Bogaerts, Joost Vennekens, and Marc Denecker. 2015b. Partial grounded fixpoints. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI’15), Qiang Yang and Michael Wooldridge (Eds.). AAAI Press, 2784--2790. Retrieved from http://ijcai.org/papers15/Abstracts/IJCAI15-394.html.

Digital Library

[7]

Bart Bogaerts, Joost Vennekens, and Marc Denecker. 2016. On well-founded set-inductions and locally monotone operators. ACM Trans. Comput. Logic 17, 4 (Sept. 2016).

Digital Library

[8]

Bart Bogaerts, Joost Vennekens, and Marc Denecker. 2018. Safe inductions and their applications in knowledge representation. Artif. Intell. 259 (2018), 167--185.

[9]

Luciano Caroprese, Sergio Greco, Cristina Sirangelo, and Ester Zumpano. 2006. Declarative semantics of production rules for integrity maintenance. In Proceedings of the International Conference on Logic Programming (ICLP 2006). (LNCS), Sandro Etalle and Mirosław Truszczyński (Eds.), Vol. 4079. Springer, 26--40.

Digital Library

[10]

Luciano Caroprese and Mirosław Truszczyński. 2011. Active integrity constraints and revision programming. Theor. Pract. Log. Prog. 11, 6 (2011), 905--952.

Digital Library

[11]

Angelos Charalambidis, Panos Rondogiannis, and Ioanna Symeonidou. 2018. Approximation fixpoint theory and the well-founded semantics of higher-order logic programs. CoRR abs/1804.08335 (2018).

[12]

Keith L. Clark. 1978. Negation as failure. In Logic and Data Bases. Plenum Press, 293--322.

[13]

Luís Cruz-Filipe. 2014. Optimizing computation of repairs from active integrity constraints. In Proceedings of the 8th International Symposium on Foundations of Information and Knowledge Systems (FoIKS’14). (Lecture Notes in Computer Science), Christoph Beierle and Carlo Meghini (Eds.), Vol. 8367. Springer, 361--380.

Digital Library

[14]

Luís Cruz-Filipe. 2016. Grounded fixpoints and active integrity constraints. In Proceedings of the Technical Communications of the 32nd International Conference on Logic Programming (ICLP’16). (OASIcs), Manuel Carro, Andy King, Marina De Vos, and Neda Saeedloei (Eds.), Vol. 52. Schloss Dagstuhl, 11:1--11:14.

[15]

Luís Cruz-Filipe, Michael Franz, Artavazd Hakhverdyan, Marta Ludovico, Isabel Nunes, and Peter Schneider-Kamp. 2015. repAIrC: A tool for ensuring data consistency. In Proceedings of the International Conference on Knowledge Management (KMIS’15) and Information Sharing, part of the 7th International Joint Conference on Knowledge Discovery, Knowledge Engineering and Knowledge Management (IC3K’15), Volume 3, Ana L. N. Fred, Jan L. G. Dietz, David Aveiro, Kecheng Liu, and Joaquim Filipe (Eds.). SciTePress, 17--26.

Digital Library

[16]

Luís Cruz-Filipe, Graça Gaspar, Patrícia Engrácia, and Isabel Nunes. 2013. Computing repairs from active integrity constraints. In Proceedings of the 7th International Symposium on Theoretical Aspects of Software Engineering (TASE’13). IEEE Computer Society, 183--190.

Digital Library

[17]

Marc Denecker, Maurice Bruynooghe, and Joost Vennekens. 2012. Approximation fixpoint theory and the semantics of logic and answers set programs. In Correct Reasoning, Esra Erdem, Joohyung Lee, Yuliya Lierler, and David Pearce (Eds.). (LNCS), Vol. 7265. Springer, 178--194.

[18]

Marc Denecker, Victor Marek, and Mirosław Truszczyński. 2000. Approximations, stable operators, well-founded fixpoints and applications in nonmonotonic reasoning. In Logic-based Artificial Intelligence, Jack Minker (Ed.). The Springer International Series in Engineering and Computer Science, Vol. 597. Springer US, 127--144.

[19]

Marc Denecker, Victor Marek, and Mirosław Truszczyński. 2003. Uniform semantic treatment of default and autoepistemic logics. Artif. Intell. 143, 1 (2003), 79--122. Retrieved from http://dx.doi.org/10.1016/S0004-3702(02)00293-X.

Digital Library

[20]

Marc Denecker, Victor Marek, and Mirosław Truszczyński. 2004. Ultimate approximation and its application in nonmonotonic knowledge representation systems. Inf. Comput. 192, 1 (July 2004), 84--121.

Digital Library

[21]

Marc Denecker, Victor Marek, and Mirosław Truszczyński. 2011. Reiter’s default logic is a logic of autoepistemic reasoning and a good one, too. In Nonmonotonic Reasoning--Essays Celebrating Its 30th Anniversary, Gerd Brewka, Victor Marek, and Mirosław Truszczyński (Eds.). College Publications, 111--144. Retrieved from http://arxiv.org/abs/1108.3278.

[22]

Marc Denecker and Joost Vennekens. 2007. Well-founded semantics and the algebraic theory of non-monotone inductive definitions. In Proceedings of the International Conference on Logic Programming and Non-monotonic Reasoning (LPNMR’07). (Lecture Notes in Computer Science), Chitta Baral, Gerhard Brewka, and John S. Schlipf (Eds.), Vol. 4483. Springer, 84--96.

[23]

Thomas Eiter, Georg Gottlob, and Heikki Mannila. 1997. Disjunctive datalog. ACM Trans. Datab. Syst. 22, 3 (1997), 364--418.

Digital Library

[24]

Melvin Fitting. 1985. A Kripke-Kleene semantics for logic programs. J. Log. Prog. 2, 4 (1985), 295--312.

[25]

Sergio Flesca, Sergio Greco, and Ester Zumpano. 2004. Active integrity constraints. In Proceedings of the 6th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, Eugenio Moggi and David Scott Warren (Eds.). ACM, 98--107.

Digital Library

[26]

Michael Gelfond and Vladimir Lifschitz. 1988. The stable model semantics for logic programming. In Proceedings of the International Conference on Logic Programming (ICLP’88) and Symposium on Logic Programming Conference (SLP’88), Robert A. Kowalski and Kenneth A. Bowen (Eds.). The MIT Press, 1070--1080. Retrieved from http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.6050.

[27]

Joseph Y. Halpern and Yoram Moses. 1985. Towards a theory of knowledge and ignorance: Preliminary report. In Logics and Models of Concurrent Systems. (NATO ASI Series), Krzysztof R. Apt (Ed.), Vol. 13. Springer Berlin, 459--476.

[28]

Stephen Cole Kleene. 1938. On notation for ordinal numbers. J. Symbol. Log. 3, 4 (1938), 150--155. Retrieved from http://www.jstor.org/stable/2267778.

[29]

Kurt Konolige. 1988. On the relation between default and autoepistemic logic. Artif. Intell. 35, 3 (1988), 343--382.

Digital Library

[30]

Vladimir Lifschitz and Hudson Turner. 1994. Splitting a logic program. In Proceedings of the 11th International Conference on Logic Programming, Pascal Van Hentenryck (Ed.). The MIT Press, 23--37.

[31]

Fangfang Liu, Yi Bi, Md. Solimul Chowdhury, Jia-Huai You, and Zhiyong Feng. 2016. Flexible approximators for approximating fixpoint theory. In Proceedings of the 29th Canadian Conference on Artificial Intelligence (Canadian AI’16). (Lecture Notes in Computer Science), Richard Khoury and Christopher Drummond (Eds.), Vol. 9673. Springer, 224--236.

Digital Library

[32]

V. Wiktor Marek and Miroslaw Truszczynski. 1998. Revision programming. Theor. Comput. Sci. 190, 2 (1998), 241--277.

Digital Library

[33]

Wolfgang May and Bertram Ludäscher. 2002. Understanding the global semantics of referential actions using logic rules. ACM Trans. Datab. Syst. 27, 4 (2002), 343--397.

Digital Library

[34]

Robert C. Moore. 1985. Semantical considerations on nonmonotonic logic. Artif. Intell. 25, 1 (1985), 75--94.

Digital Library

[35]

Norman W. Paton and Oscar Díaz. 1999. Active database systems. ACM Comput. Surv. 31, 1 (1999), 63--103.

Digital Library

[36]

Nikolay Pelov, Marc Denecker, and Maurice Bruynooghe. 2007. Well-founded and stable semantics of logic programs with aggregates. Theor. Pract. Log. Prog. 7, 3 (2007), 301--353.

Digital Library

[37]

Teodor C. Przymusinski. 1988. On the declarative semantics of deductive databases and logic programs. In Foundations of Deductive Databases and Logic Programming., Jack Minker (Ed.). Morgan Kaufmann, 193--216.

[38]

Teodor C. Przymusinski and Hudson Turner. 1997. Update by means of inference rules. J. Log. Prog. 30, 2 (1997), 125--143.

[39]

Raymond Reiter. 1980. A logic for default reasoning. Artif. Intell. 13, 1--2 (1980), 81--132.

Digital Library

[40]

Hannes Strass. 2013. Approximating operators and semantics for abstract dialectical frameworks. Artif. Intell. 205 (2013), 39--70.

Digital Library

[41]

Hannes Strass and Johannes Peter Wallner. 2015. Analyzing the computational complexity of abstract dialectical frameworks via approximation fixpoint theory. Artif. Intell. 226 (2015), 34--74.

Digital Library

[42]

Ernest Teniente and Antoni Olivé. 1995. Updating knowledge bases while maintaining their consistency. VLDB J. 4, 2 (1995), 193--241. Retrieved from http://www.vldb.org/journal/VLDBJ4/P193.pdf.

Digital Library

[43]

Mirosław Truszczyński. 2006. Strong and uniform equivalence of nonmonotonic theories—An algebraic approach. Ann. Math. Artif. Intell. 48, 3--4 (2006), 245--265.

Digital Library

[44]

Maarten H. van Emden and Robert A. Kowalski. 1976. The semantics of predicate logic as a programming language. J. ACM 23, 4 (1976), 733--742.

Digital Library

[45]

Allen Van Gelder, Kenneth A. Ross, and John S. Schlipf. 1991. The well-founded semantics for general logic programs. J. ACM 38, 3 (1991), 620--650.

Digital Library

[46]

Joost Vennekens, David Gilis, and Marc Denecker. 2006. Splitting an operator: Algebraic modularity results for logics with fixpoint semantics. ACM Trans. Comput. Log. 7, 4 (2006), 765--797.

Digital Library

[47]

Jennifer Widom and Stefano Ceri (Eds.). 1996. Active Database Systems: Triggers and Rules for Advanced Database Processing. Morgan Kaufmann.

[48]

Marianne Winslett. 1990. Updating Logical Databases. (Cambridge Tracts in Theoretical Computer Science), Vol. 9. Cambridge University Press.

Cited By

Marynissen SBogaerts BDenecker M(2024)Embedding justification theory in approximation fixpoint theoryArtificial Intelligence10.1016/j.artint.2024.104112331:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.artint.2024.104112
Bogaerts BCruz-Filipe L(2024)Approximation Fixpoint Theory in CoqLogics and Type Systems in Theory and Practice10.1007/978-3-031-61716-4_5(84-99)Online publication date: 22-May-2024
https://doi.org/10.1007/978-3-031-61716-4_5
Bienvenu MBourgaux CMarquis PSon TKern-Isberner G(2023)Inconsistency handling in prioritized databases with universal constraintsProceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning10.24963/kr.2023/10(97-106)Online publication date: 2-Sep-2023
https://dl.acm.org/doi/10.24963/kr.2023/10
Show More Cited By

Index Terms

Stratification in Approximation Fixpoint Theory and Its Application to Active Integrity Constraints

Recommendations

A fixpoint theory for non-monotonic parallelism

This paper studies parallel recursion. The trace specification language used in this paper incorporates sequentially, nondeterminism, reactiveness (including infinite traces), three forms of parallelism (including conjunctive, fair-interleaving and ...
Approximation fixpoint theory and the semantics of logic and answers set programs
Correct Reasoning

Approximation Fixpoint Theory was developed as a fixpoint theory of lattice operators that provides a uniform formalization of four main semantics of three major nonmonotonic reasoning formalisms. This paper clarifies how this fixpoint theory can define ...
Hex Semantics via Approximation Fixpoint Theory
LPNMR 2013: Proceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning - Volume 8148

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-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computational Logic

ACM Transactions on Computational Logic Volume 22, Issue 1

January 2021

262 pages

ISSN:1529-3785

EISSN:1557-945X

DOI:10.1145/3436816

Editor:
Orna Kupferman
School of Computer Science and Engineering, Hebrew University, Israel

Issue’s Table of Contents

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 January 2021

Accepted: 01 October 2020

Revised: 01 September 2020

Received: 01 June 2019

Published in TOCL Volume 22, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Danish Council for Independent Research, Natural Sciences

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
70
Total Downloads

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

Reflects downloads up to 04 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Marynissen SBogaerts BDenecker M(2024)Embedding justification theory in approximation fixpoint theoryArtificial Intelligence10.1016/j.artint.2024.104112331:COnline publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1016/j.artint.2024.104112
Bogaerts BCruz-Filipe L(2024)Approximation Fixpoint Theory in CoqLogics and Type Systems in Theory and Practice10.1007/978-3-031-61716-4_5(84-99)Online publication date: 22-May-2024
https://doi.org/10.1007/978-3-031-61716-4_5
Bienvenu MBourgaux CMarquis PSon TKern-Isberner G(2023)Inconsistency handling in prioritized databases with universal constraintsProceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning10.24963/kr.2023/10(97-106)Online publication date: 2-Sep-2023
https://dl.acm.org/doi/10.24963/kr.2023/10
Bogaerts BJakubowski M(2021)Fixpoint Semantics for Recursive SHACLElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.345.14345(41-47)Online publication date: 17-Sep-2021
https://doi.org/10.4204/EPTCS.345.14

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Figures

Tables

Media

View Issue’s Table of Contents