×

A characterization theorem for injective model classes axiomatized by general rules. (English) Zbl 1096.03027

Summary: We continue the work of Z. Zhu, X. Xiao, Y. Zhou and W. Zhu [“Normal conditions for inference relations and injective models”, Theor. Comput. Sci. 309, 287–311 (2003; Zbl 1049.03024)]. A class \(\Omega\) of strict partial order structures (posets, for short) is said to be axiomatizable if the class of all injective preferential models from \(\Omega\) can be characterized in terms of general rules. This paper aims to obtain some characteristics of axiomatizable classes. To do this, a monadic second-order frame language is presented. The relationship between \(\aleph_{0}\)-axiomatizability and second-order definability is explored. Then a notion of admissible set is introduced. Based on this notion, we show that any preferential model which does not contain any four-node substructure must be a reduct of some injective model. Furthermore, we give a necessary and sufficient condition for the axiomatizability of classes of injective preferential models using general rules. Finally, we show that, in some sense, the class of all posets without any four-node substructure is the largest among the axiomatizable classes.

MSC:

03B60 Other nonclassical logic
03C64 Model theory of ordered structures; o-minimality
03C85 Second- and higher-order model theory
68T27 Logic in artificial intelligence

Citations:

Zbl 1049.03024
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bezzazi, H.; Makinson, D.; Pino Pérez, R., Beyond rational monotonicity: some strong non-Horn rules for nonmonotonic inference relations, J. Logic. Comput., 7, 605-631 (1997) · Zbl 0937.03036
[2] Blackburn, P.; de Rijke, M.; Venema, Y., Modal Logic (2001), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0988.03006
[3] Bochman, A., Belief contraction as nonmonotonic inference, J. Symbolic Logic, 65, 2, 605-626 (2000) · Zbl 0959.03009
[4] Bochman, A., Contraction of epistemic states: a general theory, (Rott, H.; Williams, M. A., Frontiers of belief revision (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 195-221 · Zbl 1005.03019
[5] Bochman, A., A Logical Theory of Nonmonotonic Inference and Belief Change (2001), Springer: Springer Berlin · Zbl 0977.03001
[6] Chang, C. C.; Keisler, H. J., Model Theory (1977), North-Holland: North-Holland Amsterdam · Zbl 0697.03022
[7] Freund, M., Injective models and disjunctive relations, J. Logic Comput., 3, 231-247 (1993) · Zbl 0788.03032
[8] Freund, M., Supracompact inference operations, Studia Logica, 52, 457-481 (1993) · Zbl 0792.03014
[9] Freund, M.; Lehmann, D., On negation rationality, J. Logic Comput., 6, 2, 263-269 (1996) · Zbl 0854.68092
[10] D.M. Gabbay, Theoretical foundation for nonmonotonic reasoning in expert systems, in: K.R. Apr (Eds.), Proc. NATO Advance Study Institute on Logics and Models of Concurrent Systems, LaColle-sur-loup, France, Springer, Berlin, 1985, pp. 439-457.; D.M. Gabbay, Theoretical foundation for nonmonotonic reasoning in expert systems, in: K.R. Apr (Eds.), Proc. NATO Advance Study Institute on Logics and Models of Concurrent Systems, LaColle-sur-loup, France, Springer, Berlin, 1985, pp. 439-457.
[11] Kraus, S.; Lehmann, D.; Magidor, M., Nonmonotonic reasoning, preferential models and cumulative logics, Artif. Intell., 44, 1-2, 167-207 (1990) · Zbl 0782.03012
[12] Lehmann, D.; Magidor, M., What does a conditional knowledge base entail?, Artif. Intell., 55, 1-60 (1992) · Zbl 0762.68057
[13] D. Makinson, General patterns in nonmonotonic reasoning, Handbook of Logic in Artificial Intelligence and Logic Programming, Vol. III, Clarendon Press, Oxford, 1993 (Chapter 2).; D. Makinson, General patterns in nonmonotonic reasoning, Handbook of Logic in Artificial Intelligence and Logic Programming, Vol. III, Clarendon Press, Oxford, 1993 (Chapter 2).
[14] D. Makinson, Bridges from Classical to Nonmonotonic Logic, Texts in Computing, Vol. 5, King’s College Publications, London, 2005.; D. Makinson, Bridges from Classical to Nonmonotonic Logic, Texts in Computing, Vol. 5, King’s College Publications, London, 2005. · Zbl 1084.03001
[15] Pérez, R. P.; Uzcátegui, C., On representation theorems for nonmonotonic inference relation, J. Symbolic Logic, 65, 3, 1321-1337 (2000) · Zbl 0971.03030
[16] Rott, H., Belief contraction in the context of the general theory of rational choice, J. Symbolic Logic, 58, 4, 1426-1450 (1993) · Zbl 0796.03036
[17] Zhu, Z., Similarity between preferential models, Theoret. Comput. Sci., 353, 26-52 (2006) · Zbl 1088.68136
[18] Z. Zhu, B. Li, S. Chen, Valuation-ranked preferential model, in: A. Cohn, F. Giunchilia, B. Selman (Eds.), The Seventh Internat. Conf. on Principle of Knowledge Representation and Reasoning (KR’2000), Breckenridge, Colorado, USA, Morgan Kaufmann Publishers, Los Altos, CA, April 11-15, 2000, 647-653.; Z. Zhu, B. Li, S. Chen, Valuation-ranked preferential model, in: A. Cohn, F. Giunchilia, B. Selman (Eds.), The Seventh Internat. Conf. on Principle of Knowledge Representation and Reasoning (KR’2000), Breckenridge, Colorado, USA, Morgan Kaufmann Publishers, Los Altos, CA, April 11-15, 2000, 647-653.
[19] Zhu, Z.; Li, B.; Xiao, X., A representation theorem for recovering contraction relations satisfying WCI, Theoret. Comput. Sci., 290, 1, 545-564 (2003) · Zbl 1019.68106
[20] Zhu, Z.; Pan, Z.; Chen, S., Valuation structure, J. Symbolic. Logic, 67, 1, 1-23 (2002) · Zbl 1002.03020
[21] Zhu, Z.; Xiao, X.; Zhou, Y., Normal conditions for inference relations and injective models, Theoret. Comput. Sci., 309, 287-311 (2003) · Zbl 1049.03024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.