{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T19:46:33Z","timestamp":1773690393746,"version":"3.50.1"},"reference-count":80,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T00:00:00Z","timestamp":1683676800000},"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":[[2023,7,31]]},"abstract":"<jats:p>Several forms of iterable belief change exist, differing in the kind of change and its strength: some operators introduce formulae, others remove them; some add formulae unconditionally, others only as additions to the previous beliefs; some only relative to the current situation, others in all possible cases. A sequence of changes may involve several of them: for example, the first step is a revision, the second a contraction and the third a refinement of the previous beliefs. The ten operators considered in this article are shown to be all reducible to three: lexicographic revision, refinement, and severe withdrawal. In turn, these three can be expressed in terms of lexicographic revision at the cost of restructuring the sequence. This restructuring needs not to be done explicitly: an algorithm that works on the original sequence is shown. The complexity of mixed sequences of belief change operators is also analyzed. Most of them require only a polynomial number of calls to a satisfiability checker, some are even easier.<\/jats:p>","DOI":"10.1145\/3583071","type":"journal-article","created":{"date-parts":[[2023,2,9]],"date-time":"2023-02-09T13:45:29Z","timestamp":1675950329000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Mixed Iterated Revisions: Rationale, Algorithms, and Complexity"],"prefix":"10.1145","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5355-3766","authenticated-orcid":false,"given":"Paolo","family":"Liberatore","sequence":"first","affiliation":[{"name":"Sapienza University of Rome, Rome, Italy"}]}],"member":"320","published-online":{"date-parts":[[2023,5,10]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.2307\/2274239"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-9817-0_13"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.10641"},{"key":"e_1_3_1_5_2","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/978-94-015-9817-0_5","volume-title":"Frontiers in Belief Revision","author":"Benferhat S.","year":"2001","unstructured":"S. Benferhat, D. Dubois, and H. Prade. 2001. A computational model for belief change and fusing ordered belief bases. In Frontiers in Belief Revision, M. Williams and H. Rott (Eds.). Springer, 109\u2013134."},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/1550723"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2019.103171"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103289"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/1622559.1622563"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exm091"},{"key":"e_1_3_1_11_2","first-page":"230","volume-title":"Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201906)","author":"Booth R.","year":"2006","unstructured":"R. Booth, T. A. Meyer, and K. Wong. 2006. A bad day surfing is better than a good day working: How to revise a total preorder. In Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201906). AAAI Press\/The MIT Press, 230\u2013238."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)00097-2"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00248151"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90075-D"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/1622262.1622263"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1755-2567.1997.tb00740.x"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5541"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/2887965.2888049"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(96)00038-0"},{"key":"e_1_3_1_20_2","first-page":"210","volume-title":"Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201906)","author":"Delgrande J. P.","year":"2006","unstructured":"J. P. Delgrande, D. Dubois, and J. Lang. 2006. Iterated revision as prioritized merging. In Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201906). 210\u2013220."},{"key":"e_1_3_1_21_2","volume-title":"Complexity Results for Disjunctive Logic Programming and Application to Nonmonotonic Logics","author":"Eiter T.","year":"1992","unstructured":"T. Eiter and G. Gottlob. 1992. Complexity Results for Disjunctive Logic Programming and Application to Nonmonotonic Logics. Technical Report CD-TR 92\/41. Technische Universit\u00e4t Wien, Vienna Austria, Christian Doppler Labor f\u00fcr Expertensysteme."},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(92)90018-S"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(92)90018-S"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0083"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0036168"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/8.5.645"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1755020313000105"},{"issue":"6","key":"e_1_3_1_28_2","first-page":"835","article-title":"A brief note about Rott contraction","volume":"6","author":"Ferm\u00e9 E.","year":"1998","unstructured":"E. Ferm\u00e9 and R. Rodriguez. 1998. A brief note about Rott contraction. J. Interest Group Pure Appl. Logic 6, 6 (1998), 835\u2013842.","journal-title":"J. Interest Group Pure Appl. Logic"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2004.04.007"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/13.1.3"},{"key":"e_1_3_1_31_2","volume-title":"Knowledge in Flux: Modeling the Dynamics of Epistemic States","author":"G\u00e4rdenfors P.","year":"1988","unstructured":"P. G\u00e4rdenfors. 1988. Knowledge in Flux: Modeling the Dynamics of Epistemic States. Bradford Books, MIT Press, Cambridge, MA."},{"key":"e_1_3_1_32_2","first-page":"83","volume-title":"Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge (TARK\u201988)","author":"G\u00e4rdenfors P.","year":"1988","unstructured":"P. G\u00e4rdenfors and D. Makinson. 1988. Revision of knowledge systems using epistemic entrenchment. In Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge (TARK\u201988). 83\u201395."},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66902-1_8"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1005398707330"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1004781319263"},{"key":"e_1_3_1_36_2","first-page":"157","article-title":"Two modellings for theory change","author":"Grove A.","year":"1988","unstructured":"A. Grove. 1988. Two modellings for theory change. J. Philos. Logic (1988), 157\u2013170.","journal-title":"J. Philos. Logic"},{"key":"e_1_3_1_37_2","volume-title":"The Stanford Encyclopedia of Philosophy","author":"Hanson S. O.","year":"2011","unstructured":"S. O. Hanson. 2011. Logic of belief revision. In The Stanford Encyclopedia of Philosophy, E. N. Zalta (Ed.). Metaphysics Research Lab, Stanford University."},{"issue":"1","key":"e_1_3_1_38_2","first-page":"134","article-title":"In praise of full meet contraction","volume":"26","author":"Hansson S. O.","year":"2006","unstructured":"S. O. Hansson. 2006. In praise of full meet contraction. An\u00e1lisis filos\u00f3fico 26, 1 (2006), 134\u2013146.","journal-title":"An\u00e1lisis filos\u00f3fico"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10992-015-9381-7"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90025-1"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.3132"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.4558"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/209"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2006.11.002"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(91)90069-V"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jal.2016.11.033"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/11252.003.0034"},{"key":"e_1_3_1_48_2","volume-title":"Operators with Memory for Iterated Revision","author":"Konieczny S.","year":"1998","unstructured":"S. Konieczny. 1998. Operators with Memory for Iterated Revision. Technical Report IT-314. Laboratoire d\u2019Informatique Fondamentale de Lille."},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1080\/11663081.2000.10511003"},{"key":"e_1_3_1_50_2","first-page":"177","volume-title":"Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201908)","author":"Konieczny S.","year":"2008","unstructured":"S. Konieczny and R. Pino P\u00e9rez. 2008. Improvement operators. In Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201908). AAAI Press\/The MIT Press, 177\u2013187."},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67582-4_25"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90039-6"},{"key":"e_1_3_1_53_2","first-page":"466","volume-title":"Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI\u201908)","author":"Langlois M.","year":"2008","unstructured":"M. Langlois, R. H. Sloan, B. Sz\u00f6r\u00e9nyi, and G. Tur\u00e1n. 2008. Horn complements: Towards Horn-to-Horn belief revision. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI\u201908). 466\u2013471."},{"key":"e_1_3_1_54_2","first-page":"1534","volume-title":"Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI\u201995)","author":"Lehmann D.","year":"1995","unstructured":"D. Lehmann. 1995. Belief revision, revised. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI\u201995). 1534\u20131540."},{"key":"e_1_3_1_55_2","first-page":"68","volume-title":"Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI\u201997)","author":"Liberatore P.","year":"1997","unstructured":"P. Liberatore. 1997. The complexity of belief update. In Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI\u201997). 68\u201373."},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.5555\/645502.656098"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/2818645"},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00016-7"},{"key":"e_1_3_1_59_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1698"},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45683-X_88"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01130759"},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(03)00017-1"},{"key":"e_1_3_1_63_2","volume-title":"Belief Change\u2014Handbook of Defeasible Reasoning and Uncertainty Management Systems","author":"Nebel B.","year":"1998","unstructured":"B. Nebel. 1998. How hard is it to revise a belief base? In Belief Change\u2014Handbook of Defeasible Reasoning and Uncertainty Management Systems, Vol. 3, D. Dubois and H. Prade (Eds.). Kluwer Academic."},{"key":"e_1_3_1_64_2","series-title":"Applied Logic Series","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/978-94-015-9817-0_14","volume-title":"Frontiers in Belief Revision","author":"Papini O.","year":"2001","unstructured":"O. Papini. 2001. Iterated revision operations stemming from the history of an agent\u2019s observations. In Frontiers in Belief Revision. Applied Logic Series, Vol. 22. Springer, 279\u2013301."},{"key":"e_1_3_1_65_2","doi-asserted-by":"publisher","DOI":"10.3233\/978-1-58603-891-5-85"},{"key":"e_1_3_1_66_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-48758-8_26"},{"key":"e_1_3_1_67_2","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/13.1.111"},{"key":"e_1_3_1_68_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.01.011"},{"key":"e_1_3_1_69_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4020-9084-4_14"},{"key":"e_1_3_1_70_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10992-011-9206-2"},{"key":"e_1_3_1_71_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1004344003217"},{"key":"e_1_3_1_72_2","first-page":"455","volume-title":"Proceedings of the International Conference on Fifth Generation Computer Systems (FGCS\u201988)","author":"Satoh K.","year":"1988","unstructured":"K. Satoh. 1988. Nonmonotonic reasoning by minimal belief revision. In Proceedings of the International Conference on Fifth Generation Computer Systems (FGCS\u201988). 455\u2013462."},{"key":"e_1_3_1_73_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-58285-2_15"},{"key":"e_1_3_1_74_2","doi-asserted-by":"publisher","DOI":"10.3233\/FAIA200180"},{"key":"e_1_3_1_75_2","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_3_1_76_2","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1039182247"},{"key":"e_1_3_1_77_2","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/978-94-009-2865-7_6","volume-title":"Causation in Decision, Belief Change, and Statistics","author":"Spohn W.","year":"1988","unstructured":"W. Spohn. 1988. Ordinal conditional functions: A dynamic theory of epistemic states. In Causation in Decision, Belief Change, and Statistics. Kluwer Academics, 105\u2013134."},{"key":"e_1_3_1_78_2","volume-title":"Internet Festschrift for Peter G\u00e4rdenfors","author":"Spohn W.","year":"1999","unstructured":"W. Spohn. 1999. Ranking functions, AGM style. In Internet Festschrift for Peter G\u00e4rdenfors, B. Hansson, S. Halld\/en, N.-E. Sahlin, and W. Rabinowicz (Eds.)."},{"key":"e_1_3_1_79_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-55665-8_22"},{"key":"e_1_3_1_80_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90049-1"},{"key":"e_1_3_1_81_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-4832-1452-8.50152-4"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583071","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583071","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:47Z","timestamp":1750182527000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583071"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,10]]},"references-count":80,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,7,31]]}},"alternative-id":["10.1145\/3583071"],"URL":"https:\/\/doi.org\/10.1145\/3583071","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,10]]},"assertion":[{"value":"2022-02-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}