{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:43:46Z","timestamp":1750308226136,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2005,4,1]],"date-time":"2005-04-01T00:00:00Z","timestamp":1112313600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2005,4]]},"abstract":"<jats:p>Recently, several approaches to updating knowledge bases modeled as extended logic programs have been introduced, ranging from basic methods to incorporate (sequences of) sets of rules into a logic program, to more elaborate methods which use an update policy for specifying how updates must be incorporated. In this article, we introduce a framework for reasoning about evolving knowledge bases, which are represented as extended logic programs and maintained by an update policy. We first describe a formal model which captures various update approaches, and we define a logical language for expressing properties of evolving knowledge bases. We then investigate semantical and computational properties of our framework, where we focus on properties of knowledge states with respect to the canonical reasoning task of whether a given formula holds in a given evolving knowledge base. In particular, we present finitary characterizations of the evolution for certain classes of framework instances, which can be exploited for obtaining decidability results. In more detail, we characterize the complexity of reasoning for some meaningful classes of evolving knowledge bases, ranging from polynomial to double exponential space complexity.<\/jats:p>","DOI":"10.1145\/1055686.1055693","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"389-440","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Reasoning about evolving nonmonotonic knowledge bases"],"prefix":"10.1145","volume":"6","author":[{"given":"Thomas","family":"Eiter","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Fink","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuliana","family":"Sabbatini","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hans","family":"Tompits","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275507"},{"volume-title":"Proceedings of the 6th International Conference on Principles of Knowledge Representation and Reasoning (KR'98)","author":"Alferes J.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(99)00065-5"},{"volume":"1730","volume-title":"Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'99)","author":"Alferes J.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00183-2"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Balc\u00e1zar J. Diaz J. and Gabarr\u00f3 J. 1988. Structural Complexity I. 2nd ed. Springer-Verlag New York.]] Balc\u00e1zar J. Diaz J. and Gabarr\u00f3 J. 1988. Structural Complexity I. 2nd ed. Springer-Verlag New York.]]","DOI":"10.1007\/978-3-642-97062-7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00043-6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622737.1622739"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3006433.3006438"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/210197.210200"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s100090050046"},{"key":"e_1_2_1_12_1","unstructured":"Clarke E. Grumberg O. and Peled D. 1999. Model Checking. MIT Press Cambridge Mass.]] Clarke E. Grumberg O. and Peled D. 1999. Model Checking. MIT Press Cambridge Mass.]]"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/646332.687483"},{"volume-title":"Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI'01)","author":"Eiter T.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068401001247"},{"key":"e_1_2_1_17_1","first-page":"85","article-title":"Declarative update policies for nonmonotonic knowledge bases. In Logics for Emerging Applications of Databases, J. Chomicki, R. van der Meyden, and G. Saake, Eds. Springer-Verlag, New York","volume":"3","author":"Eiter T.","year":"2003","journal-title":"Chapt."},{"volume-title":"Handbook of Theoretical Computer Science","author":"Emerson E.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Fagin R. Halpern J. Moses Y. and Vardi M. 1995. Reasoning about Knowledge. MIT Press Cambridge Mass.]] Fagin R. Halpern J. Moses Y. and Vardi M. 1995. Reasoning about Knowledge. MIT Press Cambridge Mass.]]","DOI":"10.7551\/mitpress\/5803.001.0001"},{"volume-title":"Belief Change","year":"1998","author":"Gabbay D.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"},{"volume-title":"Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI'95)","author":"Inoue K.","key":"e_1_2_1_22_1"},{"volume":"1730","volume-title":"Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'99)","author":"Inoue K..","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/645378.651221"},{"key":"e_1_2_1_25_1","unstructured":"Leite J. 2002. Evolving knowledge bases---Specification and semantics. Ph.D. dissertation Universidade Nova de Lisboa Lisbon Portugal.]] Leite J. 2002. Evolving knowledge bases---Specification and semantics. Ph.D. dissertation Universidade Nova de Lisboa Lisbon Portugal.]]"},{"key":"e_1_2_1_26_1","unstructured":"Leite J. 2003. Evolving Knowledge Bases. IOS Press.]] Leite J. 2003. Evolving Knowledge Bases. IOS Press.]]"},{"volume-title":"Proceedings of the 8th International Conference on Principles of Knowledge Representation and Reasoning (KR'02)","year":"2002","author":"Lin F.","key":"e_1_2_1_27_1"},{"volume-title":"Proceedings of the 16th National Conference on Artificial Intelligence and 11th Conference on Innovative Applications of Artificial Intelligence (AAAI \/ IAAI'99). AAAI Press \/ MIT Press, 291--298","author":"Lobo J.","key":"e_1_2_1_28_1"},{"volume":"838","volume-title":"Proceedings of the 4th European Workshop on Logics in Artificial Intelligence (JELIA'94)","author":"Marek V.","key":"e_1_2_1_29_1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00092-3"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"McMillan K. 1993. Symbolic Model Checking: An Approach to the State Explosion Problem. Kluwer Academic.]] McMillan K. 1993. Symbolic Model Checking: An Approach to the State Explosion Problem. Kluwer Academic.]]","DOI":"10.1007\/978-1-4615-3190-6"},{"volume":"2258","volume-title":"Proceedings of the 10th Portuguese Conference on Artificial Intelligence (EPIA'01)","author":"Pearce D.","key":"e_1_2_1_32_1"},{"volume-title":"Proceedings of the 10th European Conference on Artificial Intelligence (ECAI'92)","author":"Pereira L.","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223844"},{"volume-title":"Proceedings of the AAAI 2001 Spring Symposium on Answer Set Programming: Towards Efficient and Scalable Knowledge Representation and Reasoning, A. Provetti and T. C. Son, Eds. AAAI Press, 210--216","author":"Son T.","key":"e_1_2_1_35_1"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Winslett M. 1990. Updating Logical Databases. Cambridge University Press Cambridge Mass.]] Winslett M. 1990. Updating Logical Databases. Cambridge University Press Cambridge Mass.]]","DOI":"10.1017\/CBO9780511663109"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Wooldridge M. 2000a. Reasoning about Rational Agents. MIT Press Cambridge Mass.]] Wooldridge M. 2000a. Reasoning about Rational Agents. MIT Press Cambridge Mass.]]","DOI":"10.7551\/mitpress\/5804.001.0001"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/518904.878877"},{"volume-title":"Proceedings of the Int. Logic Programming Symposium. MIT Press, 69--83","author":"Zhang Y.","key":"e_1_2_1_39_1"},{"volume-title":"Proceedings of the 13th European Conference on Artificial Intelligence (ECAI'98)","author":"Zhang Y.","key":"e_1_2_1_40_1"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1055686.1055693","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1055686.1055693","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:31:28Z","timestamp":1750264288000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1055686.1055693"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,4]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,4]]}},"alternative-id":["10.1145\/1055686.1055693"],"URL":"https:\/\/doi.org\/10.1145\/1055686.1055693","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2005,4]]},"assertion":[{"value":"2005-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}