Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-24T16:10:03.713Z Has data issue: false hasContentIssue false
  • English
  • Français

An algebraic characterization of equivalent preferential models

Published online by Cambridge University Press:  12 March 2014

Zhaohui Zhu  and
Rong Zhang
Zhaohui Zhu
Affiliation:
Department of Computer Science, Nanjing University of Aeronautics and Astronautics, Nanjing, 210016., P. R. China Shanghai Key Lab of Intelligent Information Processing, Fudan University, Shanghai, 200433, P.R. China. E-mail: [email protected]
Rong Zhang
Affiliation:
State Key Lab of Novel Software Technology, Nanjing University, Nanjing, 210093, P. R. China Shanghai Key Lab of Intelligent Information Processing, Fudan University, Shanghai, 200433, P.R. China. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Preferential models is one of the important semantical structures in nonmonotonic logic. This paper aims to establish an isomorphism theorem for preferential models, which gives us a purely algebraic characterization of the equivalence of preferential models. To this end, we present the notions of local similarity and local simulation. Based on these notions, two operators Δ(•) and μ(•) over preferential models are introduced and explored respectively. Together with other two existent operators ρ(•) and ΠD(•), we introduce an operator ∂D(•). Then the isomorphism theorem is obtained in terms of ∂D(•), which asserts that for any two preferential models M1 and M2, they generate the same preferential inference if and only if ∂D(M1) and ∂D(M2) are isomorphic. Based on ∂D(•), we also get an alternative model-theoretical characterization of the well-known postulate Weaken Disjunctive Rationality. Moreover, in the finite language framework, we show that Δ(μ(•)) is competent for the task of eliminating redundancy, and provide a representation result for k-relations.

Keywords

nonmonotonic logicpreferential modelmodel-theoretical properties
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 72 , Issue 3 , September 2007 , pp. 803 - 833
Copyright
Copyright © Association for Symbolic Logic 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Adams, E., The logic of conditionals, D. Reidel Publishing Co., Dordrecht, Netherlands, 1975.CrossRefGoogle Scholar
[2] Alchourrón, C. E., Gärdenfors, P., and Makinson, D., On the logic of theory change: partial meet contraction and revision functions, this Journal, vol. 50 (1985), no. 2, pp. 510–530.Google Scholar
[3] Bezzazi, H., Makinson, D., and Pérez, R. Pino, Beyond rational monotony: some strong non-Horn rules for nonmonotonic inference relations, Journal of Logic and Computation, vol. 7 (1997), pp. 605–631.CrossRefGoogle Scholar
[4] Blackburn, P., de Rijke, M., and Venema, Y., Modal logic, Cambridge University Press, Cambridge, 2001.CrossRefGoogle Scholar
[5] Bochman, A., Belief contraction as nonmonotonic inference, this Journal, vol. 65 (2000), no. 2, pp. 605–626.Google Scholar
[6] Bochman, A., Contraction of epistemic states: a general theory, Frontiers in belief revision (Rott, H. and Williams, M. A., editors), vol. 22, Kluwer Academic Publishers, 2001, pp. 195–220.CrossRefGoogle Scholar
[7] Bochman, A., Two paradigms of nonmonotonic reasoning, Ninth International Symposium on Artificial Intelligence and Mathematics, Fort Lauderdale, Florida, 01 4–6, 2006, (download: http://anytime.cs.umass.edu/aimath06/proceedings/SO1a.pdf).Google Scholar
[8] Bochman, A., A logical theory of nonmonotonic inference and belief change. Springer-Verlag, Berlin, 06, 2001.CrossRefGoogle Scholar
[9] Chang, C. C. and Keisler, H. J., Model theory, second ed., North-Holland Publishing Company, Amsterdam, 1977.Google Scholar
[10] Dubois, D. and Prade, H., Possibilistic logic, preferential models, non-monotonicity and related issues, Proceedings of the Twelfth International Joint Conference on Artificial Intelligence (IJCAI '91), Morgan Kaufmann, San Francisco, 1991, pp. 419–424.Google Scholar
[11] Freund, M., Infective models and disjunctive relations, Journal of Logic and Computation, vol. 3 (1993), pp. 231–247.CrossRefGoogle Scholar
[12] Friedman, N. and Halpern, J. Y., Plausibility measures and default reasoning, Journal of the ACM, vol. 48 (2001), no. 4, pp. 648–685.Google Scholar
[13] Gabbay, D., Theoretical foundations for non-monotonic reasoning in expert systems, Logics and models of concurrent systems, Springer-Verlag New York Inc., New York, 1989.Google Scholar
[14] Geffner, H., High probabilities, model preference and default arguments, Mind and Machines, vol. 2 (1992), pp. 51–70.Google Scholar
[15] Goldszmidt, M. and Pearl, J., Rank-based systems: A simple approach to belief revision, belief update and reasoning about evidence and actions, Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning (KR '92), Morgan Kaufmann, San Francisco, 1992, pp. 661–672.Google Scholar
[16] Hansson, S. O., A textbook of belief dynamics, Kluwer Academic Publishers, Dordrecht, 1999.CrossRefGoogle Scholar
[17] Kraus, S., Lehmann, D., and Magidor, M., Nonmonotonic reasoning, preferential models and cumulative logics, Artificial Intelligence, vol. 44 (1990), no. 1-2, pp. 167–207.CrossRefGoogle Scholar
[18] Lehmann, D. and Magidor, M., What does a conditional knowledge base entaill. Artificial Intelligence, vol. 55 (1992). pp. 1–60.CrossRefGoogle Scholar
[19] Makinson, D., General patterns in nonmonotonic reasoning, Handbook of logic in artificial intelligence and logic programming, vol. 3, Oxford University Press, New York, 1994, pp. 35–110.Google Scholar
[20] Makinson, D., Bridges from classical to nonmonotonic logic, Texts in Computing, vol. 5, King's College Publications, London, 2005.Google Scholar
[21] Milner, R., Communicating and mobile systems: the π-calculus, Cambridge University Press, New York, 1999.Google Scholar
[22] Park, D., Concurrency and automata on infinite sequences, Proceeding of the 5th GI Conference (Deussen, P., editor), Lecture Notes in Computer Science, vol. 104, Springer-Verlag, pp. 167–183.Google Scholar
[23] Pearl, J., Probabilistic semantics for nonmonotonic reasoning: a survey, Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning (San Mateo, CA), Morgan Kaufmann, 1989, pp. 505–516.Google Scholar
[24] Pérez, R. Pino and Uzcátegui, C., On representation theorems for nonmonotonic inference relations, this Journal, vol. 65 (2000), no. 3, pp. 1321–1337.Google Scholar
[25] Rott, H., Change, choice and inferences study of belief revision and nonmonotonic reasoning, University of Regensburg, Germany, 2001.CrossRefGoogle Scholar
[26] Schlechta, K., Coherent systems, Studies in Logic and Practical Reasoning, vol. 2, Elsevier B. V, Amsterdam, 2004.Google Scholar
[27] Shoham, Y., A semantical approach to nonmonotonic logics, Readings in nonmonotonic reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987, pp. 227–250.Google Scholar
[28] Spohn, W., Ordinal conditional functions: a dynamic theory of epistemic states. Causation in decision, belief change, and statistics (Harper, W. and Skyrms, B., editors), vol. 2, Reidel, Dordrecht, Netherlands, 1988, pp. 105–134.Google Scholar
[29] Zhu, Zhaohui, Similarity between preferential models, Theoretical Computer Science, vol. 353 (2006), no. 1-3, pp. 26–52.CrossRefGoogle Scholar
[30] Zhu, Zhaohui, Pan, Zhenghua, and Chen, Shifu, Valuation structure, this Journal, vol. 67 (2002), no. 1, pp. 1–23.Google Scholar
[31] Zhu, Zhaohui, Xiao, Xi'an, and Zhou, Yong, Normal conditions for inference relations and injective models, Theoretical Computer Science, vol. 309 (2003), pp. 287–311.CrossRefGoogle Scholar
[32] Zhu, Zhaohui, Zhang, Rong, and Lu, Shan, A characterization theorem for injective model classes axiomatized by general rules, Theoretical Computer Science, vol. 360 (2006), pp. 147–171.CrossRefGoogle Scholar