{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T09:42:45Z","timestamp":1762508565869},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[2021,8,17]],"date-time":"2021-08-17T00:00:00Z","timestamp":1629158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,17]],"date-time":"2021-08-17T00:00:00Z","timestamp":1629158400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"FernUniversit\u00e4t in Hagen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Conditionals are defeasible rules of the form <jats:italic>If A then usually B<\/jats:italic>, and they play a central role in many approaches to nonmonotonic reasoning. Normal forms of conditional knowledge bases consisting of a set of such conditionals are useful to create, process, and compare the knowledge represented by them. In this article, we propose several new normal forms for conditional knowledge bases. Compared to the previously introduced antecedent normal form, the <jats:italic>reduced antecedent normal form<\/jats:italic> (RANF) represents conditional knowledge with significantly fewer conditionals by taking nonmonotonic entailments licenced by system P into account. The <jats:italic>renaming normal form<\/jats:italic><jats:italic>(\u03c1NF)<\/jats:italic> addresses equivalences among conditional knowledge bases induced by renamings of the underlying signature. Combining the concept of renaming normal form with other normal forms yields the <jats:italic>renaming antecedent normal form<\/jats:italic> (<jats:italic>\u03c1<\/jats:italic> ANF) and the <jats:italic>renaming reduced antecedent normal form<\/jats:italic> (<jats:italic>\u03c1<\/jats:italic> RANF). For all newly introduced normal forms, we show their key properties regarding, existence, uniqueness, model equivalence, and inferential equivalence, and we develop algorithms transforming every conditional knowledge base into an equivalent knowledge base being in the respective normal form. For the most succinct normal form, the <jats:italic>\u03c1<\/jats:italic> RANF, we present an algorithm <jats:italic>K<\/jats:italic><jats:italic>B<\/jats:italic><jats:sup><jats:italic>\u03c1<\/jats:italic><jats:italic>r<\/jats:italic><jats:italic>a<\/jats:italic><\/jats:sup> systematically generating knowledge bases over a given signature in <jats:italic>\u03c1<\/jats:italic> RANF. We show that the generated knowledge bases are consistent, pairwise not antecedentwise equivalent, and pairwise not equivalent under signature renaming. Furthermore, the algorithm is complete in the sense that, when taking signature renamings and model equivalence into account, every consistent knowledge base is generated. Observing that normalizing the set of all knowledge bases over a signature <jats:italic>\u03a3<\/jats:italic> to <jats:italic>\u03c1<\/jats:italic> RANF yields exactly the same result as <jats:italic>K<\/jats:italic><jats:italic>B<\/jats:italic><jats:sup><jats:italic>\u03c1<\/jats:italic><jats:italic>r<\/jats:italic><jats:italic>a<\/jats:italic><\/jats:sup> (<jats:italic>\u03a3<\/jats:italic>), highlights the interrelationship between normal form transformations on the one hand and systematically generating knowledge bases in normal form on the other hand.<\/jats:p>","DOI":"10.1007\/s10472-021-09745-3","type":"journal-article","created":{"date-parts":[[2021,8,17]],"date-time":"2021-08-17T11:03:08Z","timestamp":1629198188000},"page":"149-179","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Normal forms of conditional knowledge bases respecting system P-entailments and signature renamings"],"prefix":"10.1007","volume":"90","author":[{"given":"Christoph","family":"Beierle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonas","family":"Haldimann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,17]]},"reference":[{"issue":"1","key":"9745_CR1","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/321250.321253","volume":"12","author":"JA Robinson","year":"1965","unstructured":"Robinson, J.A.: A machine oriented logic based on the resolution principle. J. ACM 12(1), 23\u201341 (1965)","journal-title":"J. ACM"},{"key":"9745_CR2","unstructured":"Robinson, J A, Voronkov, A (eds.): Handbook of automated reasoning (in 2 volumes). Elsevier and MIT Press (2001)"},{"key":"9745_CR3","doi-asserted-by":"crossref","unstructured":"Adams, E.W.: The Logic of Conditionals: An Application of Probability to Deductive Logic. Synthese Library. Springer Science+Business Media, Dordrecht (1975)","DOI":"10.1007\/978-94-015-7622-2"},{"key":"9745_CR4","volume-title":"Counterfactuals","author":"D Lewis","year":"1973","unstructured":"Lewis, D.: Counterfactuals. Harvard University Press, Cambridge (1973)"},{"key":"9745_CR5","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0004-3702(90)90101-5","volume":"44","author":"S Kraus","year":"1990","unstructured":"Kraus, S., Lehmann, D., Magidor, M.: Nonmonotonic reasoning, preferential models and cumulative logics. Artif. Intell. 44, 167\u2013207 (1990)","journal-title":"Artif. Intell."},{"key":"9745_CR6","unstructured":"Pearl, J.: System Z: A natural ordering of defaults with tractable applications to nonmonotonic reasoning. In: Parikh, R. (ed.) Proceedings of the 3rd conference on Theoretical aspects of reasoning about knowledge (TARK1990), pp 121\u2013135. Morgan Kaufmann Publishers Inc., San Francisco (1990)"},{"key":"9745_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0004-3702(92)90041-U","volume":"55","author":"D Lehmann","year":"1992","unstructured":"Lehmann, D., Magidor, M.: What does a conditional knowledge base entail?. Artif. Intell. 55, 1\u201360 (1992)","journal-title":"Artif. Intell."},{"issue":"12","key":"9745_CR8","doi-asserted-by":"publisher","first-page":"1724","DOI":"10.1109\/21.328930","volume":"24","author":"D Dubois","year":"1994","unstructured":"Dubois, D., Prade, H.: Conditional objects as nonmonotonic consequence relationships. IEEE Trans. Syst. Man Cybern. Spec. Issue Cond. Event Algebra 24(12), 1724\u20131740 (1994)","journal-title":"IEEE Trans. Syst. Man Cybern. Spec. Issue Cond. Event Algebra"},{"key":"9745_CR9","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0004-3702(95)00090-9","volume":"84","author":"M Goldszmidt","year":"1996","unstructured":"Goldszmidt, M., Pearl, J.: Qualitative probabilities for default reasoning, belief revision, and causal modeling. Artif. Intell. 84, 57\u2013112 (1996)","journal-title":"Artif. Intell."},{"issue":"6","key":"9745_CR10","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1093\/logcom\/9.6.873","volume":"9","author":"S Benferhat","year":"1999","unstructured":"Benferhat, S., Dubois, D., Prade, H.: Possibilistic and standard probabilistic semantics of conditional knowledge bases. J. Log. Comput. 9(6), 873\u2013895 (1999)","journal-title":"J. Log. Comput."},{"key":"9745_CR11","doi-asserted-by":"crossref","unstructured":"Kern-Isberner, G.: Conditionals in nonmonotonic reasoning and belief revision. LNAI, vol. 2087. Springer, Berlin (2001)","DOI":"10.1007\/3-540-44600-1"},{"key":"9745_CR12","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1023\/A:1026110129951","volume":"40(1-2)","author":"G Kern-Isberner","year":"2004","unstructured":"Kern-Isberner, G.: A thorough axiomatization of a principle of conditional preservation in belief revision. Ann. Math. Artif. Intell. 40(1-2), 127\u2013164 (2004)","journal-title":"Ann. Math. Artif. Intell."},{"key":"9745_CR13","doi-asserted-by":"publisher","unstructured":"Beierle, C., Eichhorn, C., Kern-Isberner, G., Kutsch, S.: Properties and interrelationships of skeptical, weakly skeptical, and credulous inference induced by classes of minimal models. Artif. Intell. 297. https:\/\/doi.org\/10.1016\/j.artint.2021.103489. (in press, online 2 Mar 2021) (2021)","DOI":"10.1016\/j.artint.2021.103489"},{"key":"9745_CR14","doi-asserted-by":"crossref","unstructured":"Beierle, C., Eichhorn, C., Kern-Isberner, G.: A transformation system for unique minimal normal forms of conditional knowledge bases. In: ECSQARU 2017, LNCS 10369, pp. 236\u2013245. Springer, Berlin (2017)","DOI":"10.1007\/978-3-319-61581-3_22"},{"key":"9745_CR15","doi-asserted-by":"crossref","unstructured":"Beierle, C., Eichhorn, C., Kern-Isberner, G.: On transformations and normal forms of conditional knowledge bases. In: Benferhat, S., Tabia, K., Ali, M. (eds.) Advances in Artificial Intelligence: From Theory to Practice, LNCS, vol. 10350, pp 488\u2013494. Springer (2017)","DOI":"10.1007\/978-3-319-60042-0_53"},{"key":"9745_CR16","doi-asserted-by":"crossref","unstructured":"Beierle, C.: Inferential equivalence, normal forms, and isomorphisms of knowledge bases in institutions of conditional logics. In: Hung, C.-C., Papadopoulos, G.A. (eds.) The 34th ACM\/SIGAPP Symposium on Applied Computing (SAC \u201919), April 8\u201312, 2019, Limassol, Cyprus, pp 1131\u20131138. ACM, New York (2019)","DOI":"10.1145\/3297280.3297391"},{"key":"9745_CR17","doi-asserted-by":"crossref","unstructured":"Beierle, C., Kutsch, S.: On the antecedent normal form of conditional knowledge bases. In: Kern-Isberner, G., Ognjanovi\u0107, Z. (eds.) Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 15th European Conference, ECSQARU 2019, Lecture Notes in Computer Science, vol. 11762, pp 175\u2013186. Springer (2019)","DOI":"10.1007\/978-3-030-29765-7_15"},{"issue":"1","key":"9745_CR18","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1145\/147508.147524","volume":"39","author":"J Goguen","year":"1992","unstructured":"Goguen, J., Burstall, R.: Institutions: Abstract model theory for specification and programming. J. ACM 39(1), 95\u2013146 (1992)","journal-title":"J. ACM"},{"key":"9745_CR19","doi-asserted-by":"crossref","unstructured":"Beierle, C., Haldimann, J.: Normal forms of conditional knowledge bases respecting system P-entailments. In: Herzig, A, Kontinen, J (eds.) FoIKS 2020, LNCS, vol. 12012, pp 22\u201341. Springer (2020)","DOI":"10.1007\/978-3-030-39951-1_2"},{"key":"9745_CR20","unstructured":"Beierle, C., Haldimann, J.: Transforming conditional knowledge bases into renaming normal form. In: Bart\u00e1k, R., Bell, E. (eds.) Proceedings of the 33rd International Florida Artificial Intelligence Research Society Conference, FLAIRS 2020, pp 563\u2013568. AAAI Press (2020)"},{"key":"9745_CR21","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199697502.001.0001","volume-title":"The Laws of Belief: Ranking Theory and Its Philosophical Applications","author":"W Spohn","year":"2012","unstructured":"Spohn, W.: The Laws of Belief: Ranking Theory and Its Philosophical Applications. Oxford U. Press, Oxford (2012)"},{"key":"9745_CR22","volume-title":"Probabilistic reasoning in intelligent systems","author":"J Pearl","year":"1988","unstructured":"Pearl, J.: Probabilistic reasoning in intelligent systems. Morgan Kaufmann, San Mateo (1988)"},{"key":"9745_CR23","doi-asserted-by":"crossref","unstructured":"Beierle, C., Kutsch, S.: Systematic generation of conditional knowledge bases up to renaming and equivalence. In: Calimeri, F., Leone, N., Manna, M. (eds.) Logics in Artificial Intelligence - 16th European Conference, JELIA 2019, Rende, Proceedings, LNAI, vol. 11468, pp 279\u2013286. Springer (2019)","DOI":"10.1007\/978-3-030-19570-0_18"},{"key":"9745_CR24","unstructured":"Agrawal, R., Mannila, H., Srikant, R., Toivonen, H., Verkamo, A.I.: Fast discovery of association rules. In: Fayyad, U.M., Piatetsky-Shapiro, G., Smyth, P., Uthurusamy, R. (eds.) Advances in knowledge discovery and data mining, pp 307\u2013328. MIT Press, Cambridge (1996)"},{"issue":"1","key":"9745_CR25","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s13218-016-0453-9","volume":"31","author":"C Beierle","year":"2017","unstructured":"Beierle, C., Eichhorn, C., Kutsch, S.: A practical comparison of qualitative inferences with preferred ranking models. KI \u2013 K\u00fcnstliche Intell. 31(1), 41\u201352 (2017)","journal-title":"KI \u2013 K\u00fcnstliche Intell."},{"key":"9745_CR26","unstructured":"Kutsch, S.: InfOCF-Lib: A Java library for OCF-based conditional inference. In: Beierle, C., Ragni, M., Stolzenburg, F., Thimm, M. (eds.) Proceedings of the 8th Workshop on Dynamics of Knowledge and Belief (DKB-2019) and the 7th Workshop KI & Kognition (KIK-2019) co-located with 44nd German Conference on Artificial Intelligence (KI 2019), CEUR Workshop Proceedings, vol. 2445, pp 47\u201358. CEUR-WS.org, Kassel (2019)"},{"key":"9745_CR27","doi-asserted-by":"crossref","unstructured":"Beierle, C., Haldimann, J., Kutsch, S.: A complete map of conditional knowledge bases in different normal forms and their induced system P inference relations over small signatures. In: Proceedings of the 34th International Florida Artificial Intelligence Research Society Conference, FLAIRS 2021 (2021)","DOI":"10.32473\/flairs.v34i1.128467"},{"key":"9745_CR28","doi-asserted-by":"crossref","unstructured":"Britz, K., Casini, G., Meyer, T., Varzinczak, I.: A KLM perspective on defeasible reasoning for description logics. In: Lutz, C., Sattler, U., Tinelli, C., Turhan, A.-Y., Wolter, F. (eds.) Description Logic, Theory Combination, and All That - Essays Dedicated to Franz Baader on the Occasion of His 60th Birthday, LNCS, vol. 11560, pp 147\u2013173. Springer (2019)","DOI":"10.1007\/978-3-030-22102-7_7"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-021-09745-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10472-021-09745-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-021-09745-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,31]],"date-time":"2022-01-31T02:06:44Z","timestamp":1643594804000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10472-021-09745-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,17]]},"references-count":28,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["9745"],"URL":"https:\/\/doi.org\/10.1007\/s10472-021-09745-3","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,17]]},"assertion":[{"value":"22 April 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 August 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}