Automated Generation of Logical Constraints on Approximation Spaces Using Quantifier Elimination

• Autorzy: Doherty P. , Szałas A.
• Języki publikacji: EN

Abstrakty

EN

This paper focuses on approximate reasoning based on the use of approximation spaces. Approximation spaces and the approximated relations induced by them are a generalization of the rough set-based approximations of Pawlak. Approximation spaces are used to define neighborhoods around individuals and rough inclusion functions. These in turn are used to define approximate sets and relations. In any of the approaches, one would like to embed such relations in an appropriate logical theory which can be used as a reasoning engine for specific applications with specific constraints. We propose a framework which permits a formal study of the relationship between properties of approximations and properties of approximation spaces. Using ideas from correspondence theory, we develop an analogous framework for approximation spaces. We also show that this framework can be strongly supported by automated techniques for quantifier elimination.

Słowa kluczowe

EN

approximate reasoning; approximation spaces; knowledge representation; quantifier elimination; rough sets

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 127, nr 1-4
• Strony: 135--149
• Opis fizyczny: Bibliogr. 20 poz.

Twórcy

autor

Doherty P.

• Department of Computer and Information Science, Linköping University, Linköping, Sweden

autor

Szałas A.

• Institute of Informatics, University of Warsaw, Poland
• Department of Computer and Information Science, Linköping University, Linköping, Sweden

Bibliografia

• [1] Ackermann, W.: Untersuchungenüber das Eliminationsproblemder mathematischen Logik, Mathematische Annalen, 110, 1935, 390-413.
• [2] Doherty, P., Łukaszewicz, W., Skowron, A., Szałas, A. : Knowledge Engineering. A Rough Set Approach, vol. 202 of Studies in Fuzziness and Soft Computing, Springer-Verlag, 2006.
• [3] Doherty, P., Łukaszewicz, W., Szałas, A.: A Reduction Result for Circumscribed Semi-Horn Formulas, Fundamenta Informaticae, 28(3-4), 1996, 261-271.
• [4] Doherty, P., Łukaszewicz, W., Szałas, A.: Computing Circumscription Revisited, Journal of Automated Reasoning, 18(3), 1997, 297-336.
• [5] Doherty, P., Szałas, A.: On the Correspondence between Approximations and Similarity, Proc. Rough Sets and Current Trends in Computing, 4th International Conference, RSCTC 2004 (S. Tsumoto, R. Slowiński, H. Komorowski, J. Grzymala-Busse, Eds.), LNCS, vol. 3066 of LNCS, 2004, 143-152.
• [6] Doherty, P., Szałas, A.: A Correspondence Framework between Three-Valued Logics and Similarity-Based Approximate Reasoning, Fundam. Inform., 75(1-4), 2007, 179-193.
• [7] Doherty, P., Szalas, A.: Reasoning with Qualitative Preferences and Cardinalities using Generalized Circumscription, Proc. Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference, KR ’08 (G. Brewka, J. Lang, Eds.), AAAI Press, 2008, 560-570.
• [8] Gabbay, D., Schmidt, R., Szałas, A.: Second-Order Quantifier Elimination. Foundations, Computational Aspects and Applications, vol. 12 of Studies in Logic, College Publications, 2008.
• [9] Gomolinska, A.: Satisfiability and Meaning of Formulas and Sets of Formulas in Approximation Spaces, Fundam. Inform., 67(1-3), 2005, 77-92.
• [10] Gustafsson, J.: An Implementation and Optimization of an Algorithm for Reducing Formulas in Second- Order Logic, 1996, Technical Report LiTH-MAT-R-96-04, http://www.ida.liu.se/labs/kplab/projects/dls/.
• [11] Lifschitz, V.: Circumscription, Handbook of Artificial Intelligence and Logic Programming (D. M. Gabbay, C. J. Hogger, J. A. Robinson, Eds.), vol. 3, Oxford University Press, 1991, 297-352.
• [12] Magnusson, M.: Implementation of DLS*, 2005, Http://www.ida.liu.se/labs/kplab/projects/dlsstar/.
• [13] Nonnengart, A., Szałas, A.: A Fixpoint Approach to Second-Order Quantifier Elimination with Applications to Correspondence Theory, Logic at Work: Essays Dedicated to the Memory of Helena Rasiowa (E. Orłowska, Ed.), Studies in Fuzziness and Soft Computing, vol. 24 of Studies in Fuzziness and Soft Computing, Springer Physica-Verlag, 1998, 307-328.
• [14] Pawlak, Z.: Rough sets, International Journal of Computer and Information Sciences, 11, 1982, 341-356.
• [15] Pawlak, Z.: Rough Sets. Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Dordrecht, 1991.
• [16] Peters, J., Skowron, A., Stepaniuk, J.: Nearness of Objects: Extension of Approximation Space Model, Fundam. Inform., 79(3-4), 2007, 497-512.
• [17] Skowron, A., Stepaniuk, J.: Tolerance Approximation Spaces, Fundamenta Informaticae, 27, 1996, 245253.
• [18] Skowron, A., Stepaniuk, J., Swiniarski, R.: Approximation Spaces in Rough-Granular Computing, Fundam. Inform., 100(1-4), 2010, 141-157.
• [19] Stepaniuk, J.: Approximation Spaces Reducts and Representatives, Rough Sets in Knowledge Discovery, vol. 2, Physica Verlag, 1998, 109-126.
• [20] Van Benthem, J.: Correspondence Theory, Handbook of Philosophical Logic (D. Gabbay, F. Guenthner, Eds.), vol. 2, D. Reidel Pub. Co., 1984, 167-247.