{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T16:55:19Z","timestamp":1773939319047,"version":"3.50.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"DOI":"10.13039\/501100014538","name":"Indonesia Endowment Fund for Education","doi-asserted-by":"crossref","award":["0000156\/SC\/D\/2\/lpdp2016"],"award-info":[{"award-number":["0000156\/SC\/D\/2\/lpdp2016"]}],"id":[{"id":"10.13039\/501100014538","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Federal Ministry of Research, Technology, and Space, Germany"},{"name":"European Research Council","award":["771779"],"award-info":[{"award-number":["771779"]}]},{"name":"BMFTR and DAAD","award":["57616814"],"award-info":[{"award-number":["57616814"]}]},{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["465447331, 318378366 and 427257555"],"award-info":[{"award-number":["465447331, 318378366 and 427257555"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2025,10,31]]},"abstract":"<jats:p>\n                    We establish a generic, model-theoretic characterization of rational belief revision operators implementing the paradigm of minimal change according to the seminal work by Alchourr\u00f3n, G\u00e4rdenfors, and Makinson (AGM). Our characterization applies to all Tarskian logics, that is, all logics with a classical model-theoretic semantics, and hence a wide variety of formalisms were used in knowledge representation and beyond, including many for which a model-theoretic characterization has hitherto been lacking. Our starting point is the approach by Katsuno and Mendelzon (K&amp;M), who provided such a characterization for propositional logic over finite signatures. We generalize K&amp;M\u2019s approach to the setting of AGM-style revision over bases in arbitrary Tarskian logics, where\n                    <jats:italic toggle=\"yes\">base<\/jats:italic>\n                    may refer to one of the various ways of representing an agent\u2019s beliefs (such as belief sets, arbitrary or finite sets of sentences, or single sentences). Our first core result is a representation theorem providing a two-way correspondence between AGM-style revision operators and specific\n                    <jats:italic toggle=\"yes\">assignments<\/jats:italic>\n                    : functions associating every base to a \u201cpreference\u201d relation over interpretations, which must be total but is\u2014in contrast to prior approaches\u2014not always transitive. As our second core contribution, we provide a characterization of all logics for which our result can be strengthened to assignments producing transitive preference relations (as in K&amp;M\u2019s original work). Alongside these main contributions, we discuss diverse variants of our findings as well as ramifications for other areas of belief revision theory.\n                  <\/jats:p>","DOI":"10.1145\/3763234","type":"journal-article","created":{"date-parts":[[2025,8,25]],"date-time":"2025-08-25T13:50:52Z","timestamp":1756129852000},"page":"1-54","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["AGM Belief Revision, Semantically"],"prefix":"10.1145","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7974-9898","authenticated-orcid":false,"given":"Faiq Miftakhul","family":"Falakh","sequence":"first","affiliation":[{"name":"Computational Logic Group, Technische Universit\u00e4t Dresden, Dresden, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1609-2080","authenticated-orcid":false,"given":"Sebastian","family":"Rudolph","sequence":"additional","affiliation":[{"name":"Computational Logic Group, Technische Universit\u00e4t Dresden, Dresden, Germany and Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI), Dresden\/Leipzig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1551-7016","authenticated-orcid":false,"given":"Kai","family":"Sauerwald","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Computer Science, FernUniversitat in Hagen, Hagen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,10,24]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2017.12.002"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.2307\/2274239"},{"key":"e_1_3_4_4_2","volume-title":"Model-Theoretic Logics","author":"Barwise Jon","year":"1985","unstructured":"Jon Barwise and Solomon Feferman. 1985. Model-Theoretic Logics. Cambridge University Press."},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2006.12.001"},{"key":"e_1_3_4_6_2","first-page":"220","volume-title":"Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning (KR \u201918)","author":"Casini Giovanni","year":"2018","unstructured":"Giovanni Casini, Eduardo Ferm\u00e9, Thomas Meyer, and Ivan Varzinczak. 2018. A semantic perspective on belief change in a preferential non-monotonic framework. In Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning (KR \u201918). Michael Thielscher, Francesca Toni, and Frank Wolter (Eds.), AAAI, 220\u2013229."},{"key":"e_1_3_4_7_2","first-page":"929","volume-title":"Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI \u201917)","author":"Casini Giovanni","year":"2017","unstructured":"Giovanni Casini and Thomas Meyer. 2017. Belief change in a preferential non-monotonic framework. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI \u201917). Carles Sierra (Ed.), AAAI Press, 929\u2013935. DOI: 10.24963\/ijcai.2017\/129"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(96)00038-0"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2011.10.001"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2014.08.006"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3203409"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2017.09.001"},{"key":"e_1_3_4_13_2","volume-title":"Belief Revision in Expressive Knowledge Representation Formalisms","author":"Falakh Faiq Miftakhul","year":"2023","unstructured":"Faiq Miftakhul Falakh. 2023. Belief Revision in Expressive Knowledge Representation Formalisms. Ph.D. Dissertation. Dresden University of Technology, Germany. Retrieved from https:\/\/nbn-resolving.org\/urn:nbn:de:bsz:14-qucosa2-828811"},{"key":"e_1_3_4_14_2","volume-title":"Proceedings of the 35th International Workshop on Description Logics (DL \u201922) Co-Located with Federated Logic Conference (FLoC \u201922)CEUR Workshop Proceedings, Vol","volume":"3263","author":"Falakh Faiq Miftakhul","year":"2022","unstructured":"Faiq Miftakhul Falakh and Sebastian Rudolph. 2022. AGM revision in description logics under fixed-domain semantics. In Proceedings of the 35th International Workshop on Description Logics (DL \u201922) Co-Located with Federated Logic Conference (FLoC \u201922). Ofer Arieli, Martin Homola, Jean Christoph Jung, and Marie-Laure Mugnier (Eds.), CEUR Workshop Proceedings, Vol. 3263. Retrieved from https:\/\/ceur-ws.org\/Vol-3263\/paper-8.pdf"},{"key":"e_1_3_4_15_2","first-page":"95","volume-title":"Proceedings of the 6th International Joint Conference on Rules and Reasoning (RuleML+RR \u201922)Lecture Notes in Computer Science, Vol","volume":"13752","author":"Falakh Faiq Miftakhul","year":"2022","unstructured":"Faiq Miftakhul Falakh, Sebastian Rudolph, and Kai Sauerwald. 2022. Semantic characterizations of AGM revision for Tarskian logics. In Proceedings of the 6th International Joint Conference on Rules and Reasoning (RuleML+RR \u201922). Guido Governatori and Anni-Yasmin Turhan (Eds.), Lecture Notes in Computer Science, Vol. 13752, Springer, 95\u2013110. DOI: 10.1007\/978-3-031-21541-4_7"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1005294718935"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-60535-7"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/bf01066356"},{"key":"e_1_3_4_19_2","volume-title":"Knowledge in Flux: Modeling the Dynamics of Epistemic States","author":"G\u00e4rdenfors Peter","year":"1988","unstructured":"Peter G\u00e4rdenfors. 1988. Knowledge in Flux: Modeling the Dynamics of Epistemic States. MIT Press."},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90017-5"},{"key":"e_1_3_4_21_2","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1093\/oso\/9780198537915.003.0002","volume-title":"Handbook of Logic in Artificial Intelligence and Logic Programming","author":"G\u00e4rdenfors Peter","year":"1995","unstructured":"Peter G\u00e4rdenfors and Hans Rott. 1995. Belief revision. In Handbook of Logic in Artificial Intelligence and Logic Programming. Dov M. Gabbay, C. J. Hogger, and J. A. Robinson (Eds.), Vol. 4, Oxford University Press, 35\u2013132."},{"key":"e_1_3_4_22_2","first-page":"325","volume-title":"Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS \u201908)LIPIcs, Vol","volume":"1","author":"Gelade Wouter","year":"2008","unstructured":"Wouter Gelade and Frank Neven. 2008. Succinctness of the complement and intersection of regular expressions. In Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS \u201908). Susanne Albers and Pascal Weil (Eds.), LIPIcs, Vol. 1, Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 325\u2013336. DOI: 10.4230\/LIPIcs.STACS.2008.1354"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00247909"},{"key":"e_1_3_4_24_2","volume-title":"Proceedings of the 2nd Workshop on OWL: Experiences and Directions (OWLED \u201906)CEUR Workshop Proceedings, Vol","volume":"216","author":"Halaschek-Wiener Christian","year":"2006","unstructured":"Christian Halaschek-Wiener and Yarden Katz. 2006. Belief base revision for expressive description logics. In Proceedings of the 2nd Workshop on OWL: Experiences and Directions (OWLED \u201906). Bernardo Cuenca Grau, Pascal Hitzler, Conor Shankey, and Evan Wallace (Eds.), CEUR Workshop Proceedings, Vol. 216. Retrieved from http:\/\/ceur-ws.org\/Vol-216\/submission_21.pdf"},{"issue":"4","key":"e_1_3_4_25_2","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/BF00484979","article-title":"Choice structures and preference relations","volume":"18","author":"Hansson Bengt","year":"1968","unstructured":"Bengt Hansson. 1968. Choice structures and preference relations. Synthese 18, 4 (1968), 443\u2013458. Retrieved from http:\/\/www.jstor.org\/stable\/20114617","journal-title":"Synthese"},{"key":"e_1_3_4_26_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-94-007-0814-3","volume-title":"A Textbook of Belief Dynamics: Theory Change and Database Updating","author":"Hansson Sven Ove","year":"1999","unstructured":"Sven Ove Hansson. 1999. A Textbook of Belief Dynamics: Theory Change and Database Updating. Springer."},{"issue":"2","key":"e_1_3_4_27_2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/s11229-009-9688-4","article-title":"Multiple and iterated contraction reduced to single-step single-sentence contraction","volume":"173","author":"Hansson Sven Ove","year":"2010","unstructured":"Sven Ove Hansson. 2010. Multiple and iterated contraction reduced to single-step single-sentence contraction. Synthese 173, 2 (2010), 153\u2013177.","journal-title":"Synthese"},{"issue":"4","key":"e_1_3_4_28_2","doi-asserted-by":"crossref","first-page":"1581","DOI":"10.2307\/2694963","article-title":"Credibility limited revision","volume":"66","author":"Hansson Sven Ove","year":"2001","unstructured":"Sven Ove Hansson, Eduardo L. Ferm\u00e9, John Cantwell, and Marcelo A. Falappa. 2001. Credibility limited revision. Journal of Symbolic Logic 66, 4 (2001), 1581\u20131596.","journal-title":"Journal of Symbolic Logic"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44761-X"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(91)90069-V"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jal.2016.11.033"},{"key":"e_1_3_4_32_2","first-page":"484","volume-title":"Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI \u201905)","volume":"19","author":"Konieczny S\u00e9bastien","year":"2005","unstructured":"S\u00e9bastien Konieczny, J\u00e9r\u00f4me Lang, and Pierre Marquis. 2005. Reasoning under inconsistency: The forgotten connective. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI \u201905). Menno van Zaanen, Tim Oates, Georgios Paliouras, and Colin de la Higuera (Eds.), Vol. 19, 484\u2013490."},{"key":"e_1_3_4_33_2","volume-title":"Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning (KR \u201925)","author":"Kontinen Juha","year":"2025","unstructured":"Juha Kontinen, Arne Meier, and Kai Sauerwald. 2025. On the complexity and properties of preferential propositional dependence logic. In Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning (KR \u201925). Magdalena Ortiz, Renata Wassermann, and Torsten Schaub (Eds.)."},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(90)90101-5"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.2307\/2694923"},{"key":"e_1_3_4_36_2","first-page":"707","article-title":"Binary codes capable of correcting deletions","volume":"10","author":"Levenshtein Vladimir Iosifovich","year":"1966","unstructured":"Vladimir Iosifovich Levenshtein. 1966. Binary codes capable of correcting deletions. Insertions and Reversals. Soviet Physics Doklady 10 (1966), 707\u2013709.","journal-title":"Insertions and Reversals. Soviet Physics Doklady"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.2307\/2273738"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0018421"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1023\/a:1008308620177"},{"key":"e_1_3_4_40_2","first-page":"81","volume-title":"Proceedings of the 13th Conference of the Spanish Association for Artificial Intelligence (CAEPIA \u201909)LNCS, Vol","volume":"5988","author":"Pardo Pere","year":"2009","unstructured":"Pere Pardo, Pilar Dellunde, and Lluis Godo. 2009. Base belief change for finitary monotonic logics. In Proceedings of the 13th Conference of the Spanish Association for Artificial Intelligence (CAEPIA \u201909). Pedro Meseguer, Lawrence Mandow, and Rafael M. Gasca (Eds.), LNCS, Vol. 5988, Springer, 81\u201390. DOI: 10.1007\/978-3-642-14264-2_9"},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/14.3.355"},{"key":"e_1_3_4_42_2","first-page":"386","volume-title":"Proceedings of the 10th European Conference of Logics in Artificial Intelligence (JELIA \u201906), LNCS, Vol","volume":"4160","author":"Qi Guilin","year":"2006","unstructured":"Guilin Qi, Weiru Liu, and David A. Bell. 2006. Knowledge base revision in description logics. In Proceedings of the 10th European Conference of Logics in Artificial Intelligence (JELIA \u201906), Michael Fisher, Wiebe van der Hoek, Boris Konev, and Alexei Lisitsa (Eds.), LNCS, Vol. 4160, Springer, 386\u2013398. DOI: 10.1007\/11853886_32"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-4186-0"},{"key":"e_1_3_4_44_2","volume-title":"Proceedings of the 14th International Conference of Principles of Knowledge Representation and Reasoning (KR \u201914)","author":"Ribeiro M\u00e1rcio Moretto","year":"2014","unstructured":"M\u00e1rcio Moretto Ribeiro and Renata Wassermann. 2014. Minimal change in AGM revision for non-classical logics. In Proceedings of the 14th International Conference of Principles of Knowledge Representation and Reasoning (KR \u201914). Chitta Baral, Giuseppe De Giacomo, and Thomas Eiter (Eds.), AAAI Press."},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2013.06.001"},{"key":"e_1_3_4_46_2","doi-asserted-by":"publisher","DOI":"10.3233\/DAI352"},{"key":"e_1_3_4_47_2","first-page":"429","volume-title":"Proceedings of the 16th International Conference on Scalable Uncertainty Management (SUM \u201924)","author":"Sauerwald Kai","year":"2024","unstructured":"Kai Sauerwald. 2024. Credibility-limited revision for epistemic spaces. In Proceedings of the 16th International Conference on Scalable Uncertainty Management (SUM \u201924). S\u00e9bastien Destercke, Maria Vanina Martinez, and Giuseppe Sanfilippo (Eds.), Springer, 429\u2013444. DOI: 10.1007\/978-3-031-76235-2_32"},{"key":"e_1_3_4_48_2","first-page":"665","volume-title":"Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning (KR \u201924)","author":"Sauerwald Kai","year":"2024","unstructured":"Kai Sauerwald and Matthias Thimm. 2024. The realizability of revision and contraction operators in epistemic spaces. In Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning (KR \u201924), 665\u2013670. DOI: 10.24963\/kr.2024\/62"},{"key":"e_1_3_4_49_2","first-page":"320","volume-title":"Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning","author":"Schwind Nicolas","year":"2022","unstructured":"Nicolas Schwind, S\u00e9bastien Konieczny, and Ram\u00f3n Pino P\u00e9rez. 2022. On the representation of Darwiche and Pearl\u2019s epistemic states for iterated belief revision. In Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning, 320\u2013330. DOI: 10.24963\/kr.2022\/32"},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","DOI":"10.2307\/2296384"},{"key":"e_1_3_4_51_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1004904401346"},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.04.003"},{"key":"e_1_3_4_53_2","volume-title":"Logic Semantics, Metamathematics Papers From 1923 to 1938. Translated by J.H. Woodger","author":"Tarski Alfred","year":"1956","unstructured":"Alfred Tarski. 1956. Logic Semantics, Metamathematics Papers From 1923 to 1938. Translated by J.H. Woodger. Clarendon Press."},{"key":"e_1_3_4_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02943527"},{"key":"e_1_3_4_55_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.11337"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763234","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T10:37:51Z","timestamp":1761302271000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763234"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,24]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,10,31]]}},"alternative-id":["10.1145\/3763234"],"URL":"https:\/\/doi.org\/10.1145\/3763234","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,24]]},"assertion":[{"value":"2024-04-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-24","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}