Abstract
Normal forms of conditional knowledge bases are useful to create, process and compare the knowledge represented by them. In this paper, we propose the reduced antecedent normal form (RANF) for conditional knowledge bases. Compared to the antecedent normal form, it represents conditional knowledge with significantly fewer conditionals. A set of transformation rules maps every knowledge base to a model equivalent knowledge base in RANF. The new notion of renaming normal form (\(\rho \)NF) of a conditional knowledge base takes signature renamings into account. We develop an algorithm for systematically generating conditional knowledge bases over a given signature that are both in RANF and in \(\rho \)NF. 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, taking signature renamings and model equivalence into account, every consistent knowledge base is generated.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adams, E.W.: The Logic of Conditionals: An Application of Probability to Deductive Logic. Synthese Library. Springer, Dordrecht (1975). https://doi.org/10.1007/978-94-015-7622-2
Agrawal, R., Mannila, H., Srikant, R., Toivonen, H., Verkamo, A.: Fast discovery of association rules. In: Fayyad, U., Piatetsky-Shapiro, G., Smyth, P., Uthurusamy, R. (eds.) Advances in Knowledge Discovery and Data Mining, pp. 307–328. MIT Press, Cambridge (1996)
Beierle, C.: Inferential equivalence, normal forms, and isomorphisms of knowledge bases in institutions of conditional logics. In: Hung, C., Papadopoulos, G.A. (eds.) The 34th ACM/SIGAPP Symposium on Applied Computing (SAC 2019), pp. 1131–1138. ACM, New York (2019)
Beierle, C., Eichhorn, C., Kern-Isberner, G.: A transformation system for unique minimal normal forms of conditional knowledge bases. In: Antonucci, A., Cholvy, L., Papini, O. (eds.) ECSQARU 2017. LNCS (LNAI), vol. 10369, pp. 236–245. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-61581-3_22
Beierle, C., Eichhorn, C., Kutsch, S.: A practical comparison of qualitative inferences with preferred ranking models. KI - Künstliche Intelligenz 31(1), 41–52 (2017)
Beierle, C., Kutsch, S.: Computation and comparison of nonmonotonic skeptical inference relations induced by sets of ranking models for the realization of intelligent agents. Appl. Intell. 49(1), 28–43 (2019)
Beierle, C., Kutsch, S.: On the antecedent normal form of conditional knowledge bases. In: Kern-Isberner, G., Ognjanović, Z. (eds.) ECSQARU 2019. LNCS (LNAI), vol. 11726, pp. 175–186. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-29765-7_15
Beierle, C., Kutsch, S.: Systematic generation of conditional knowledge bases up to renaming and equivalence. In: Calimeri, F., Leone, N., Manna, M. (eds.) JELIA 2019. LNCS (LNAI), vol. 11468, pp. 279–286. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-19570-0_18
Benferhat, S., Dubois, D., Prade, H.: Possibilistic and standard probabilistic semantics of conditional knowledge bases. J. Logic Comput. 9(6), 873–895 (1999)
Dubois, D., Prade, H.: Conditional objects as nonmonotonic consequence relationships. IEEE Trans. Syst. Man Cybern. 24(12), 1724–1740 (1994). Special Issue on Conditional Event Algebra
Goldszmidt, M., Pearl, J.: Qualitative probabilities for default reasoning, belief revision, and causal modeling. Artif. Intell. 84, 57–112 (1996)
Kern-Isberner, G.: Conditionals in Nonmonotonic Reasoning and Belief Revision. LNCS (LNAI), vol. 2087. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44600-1
Kraus, S., Lehmann, D., Magidor, M.: Nonmonotonic reasoning, preferential models and cumulative logics. Artif. Intell. 44, 167–207 (1990)
Lehmann, D., Magidor, M.: What does a conditional knowledge base entail? Artif. Intell. 55, 1–60 (1992)
Lewis, D.: Counterfactuals. Harvard University Press, Cambridge (1973)
Pearl, J.: Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, San Mateo (1988)
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 (TARK 1990), pp. 121–135. Morgan Kaufmann Publishers Inc., San Francisco (1990)
Robinson, J.A., Voronkov, A. (eds.): Handbook of Automated Reasoning (in 2 Volumes). Elsevier and MIT Press, Cambridge (2001)
Spohn, W.: The Laws of Belief: Ranking Theory and Its Philosophical Applications. Oxford University Press, Oxford (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Beierle, C., Haldimann, J. (2020). Normal Forms of Conditional Knowledge Bases Respecting Entailments and Renamings. In: Herzig, A., Kontinen, J. (eds) Foundations of Information and Knowledge Systems. FoIKS 2020. Lecture Notes in Computer Science(), vol 12012. Springer, Cham. https://doi.org/10.1007/978-3-030-39951-1_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-39951-1_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-39950-4
Online ISBN: 978-3-030-39951-1
eBook Packages: Computer ScienceComputer Science (R0)