×

Rough set reasoning using answer set programs. (English) Zbl 1487.68228

Summary: Reasoning about uncertainty is one of the main cornerstones of Knowledge Representation. Formal representations of uncertainty are numerous and highly varied due to different types of uncertainty intended to be modeled such as vagueness, imprecision and incompleteness. There is a rich body of theoretical results that has been generated for many of these approaches. It is often the case though, that pragmatic tools for reasoning with uncertainty lag behind this rich body of theoretical results. Rough set theory is one such approach for modeling incompleteness and imprecision based on indiscernibility and its generalizations. In this paper, we provide a pragmatic tool for constructively reasoning with generalized rough set approximations that is based on the use of Answer Set Programming (Asp). We provide an interpretation of answer sets as (generalized) approximations of crisp sets (when possible) and show how to use Asp solvers as a tool for reasoning about (generalized) rough set approximations situated in realistic knowledge bases. The paper includes generic Asp templates for doing this and also provides a case study showing how these techniques can be used to generate reducts for incomplete information systems. Complete, ready to run clingo Asp code is provided in the Appendix, for all programs considered. These can be executed for validation purposes in the clingo Asp solver.

MSC:

68T37 Reasoning under uncertainty in the context of artificial intelligence
68N17 Logic programming
68T30 Knowledge representation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abiteboul, S.; Hull, R.; Vianu, V., Foundations of Databases (1996), Addison-Wesley Pub. Co.: Addison-Wesley Pub. Co. Boston, MA, USA
[2] Alviano, M.; Faber, W.; Leone, N.; Perri, S.; Pfeifer, G.; Terracina, G., The disjunctive datalog system DLV, (de Moor, O.; Gottlob, G.; Furche, T.; Sellers, A., Datalog Reloaded (2011), Springer), 282-301
[3] Antoniou, G., A tutorial on default logics, ACM Comput. Surv., 31, 337-359 (1999)
[4] Baral, C., Knowledge Representation, Reasoning, and Declarative Problem Solving (2003), Cambridge University Press · Zbl 1056.68139
[5] Brewka, G.; Eiter, T.; Truszczyński, M., Answer set programming at a glance, Commun. ACM, 54, 92-103 (2011)
[6] Chellas, B. F., Modal Logic - an Introduction (1980), Cambridge University Press · Zbl 0431.03009
[7] Ciucci, D., Orthopairs: a simple and widely used way to model uncertainty, Fundam. Inform., 108, 287-304 (2011) · Zbl 1242.68309
[8] Ciucci, D.; Dubois, D., Three-valued logics, uncertainty management and rough sets, (Peters, J.; Skowron, A., Transactions on Rough Sets XVII (2014), Springer: Springer Berlin Heidelberg), 1-32 · Zbl 1404.68159
[9] Demri, S.; Orłowska, E., Incomplete Information: Structure, Inference, Complexity, EATCS Monographs (2002), Springer · Zbl 1016.68163
[10] Doherty, P.; Łukaszewicz, W.; Skowron, A.; Szałas, A., Knowledge Representation Techniques. A Rough Set Approach, Studies in Fuziness and Soft Computing, vol. 202 (2006), Springer Verlag · Zbl 1131.68107
[11] Doherty, P.; Łukaszewicz, W.; Szałas, A., Efficient reasoning using the local closed-world assumption, (Cerri, A.; Dochev, D., Proc. 9th Int. Conference AIMSA 2000 (2000), Springer-Verlag), 49-58 · Zbl 0973.68217
[12] Doherty, P.; Szałas, A., Stability, supportedness, minimality and Kleene Answer Set Programs, (Eiter, T.; Strass, H.; Truszczyński, M.; Woltran, S., Advances in Knowledge Representation, Logic Programming, and Abstract Argumentation - Essays Dedicated to G. Brewka on the Occasion of His 60th Birthday (2015), Springer), 125-140 · Zbl 1432.68457
[13] Doherty, P.; Szałas, A., On the correspondence between approximations and similarity, (Tsumoto, S.; Słowiński, R.; Komorowski, H.; Grzymala-Busse, J., Proc. 4th Conf. RSCTC Rough Sets and Current Trends in Computing (2004), Springer), 143-152 · Zbl 1103.68841
[14] Doherty, P.; Szałas, A., A correspondence framework between three-valued logics and similarity-based approximate reasoning, Fundam. Inform., 75, 179-193 (2007) · Zbl 1108.68113
[15] Etzioni, O.; Golden, K.; Weld, D., Sound and efficient closed-world reasoning for planning, Artif. Intell., 89, 113-148 (1997) · Zbl 1018.03513
[16] Gebser, M.; Kaminski, R.; Kaufmann, B.; Schaub, T., Answer Set Solving in Practice. Synthesis Lectures on Artificial Intelligence and Machine Learning (2012), Morgan and Claypool Pub.
[17] Gebser, M.; Kaufmann, B.; Neumann, A.; Schaub, T., clasp: A conflict-driven answer set solver, (9th Int. Conf. LPNMR.07 (2007)), 260-265
[18] Gelfond, M.; Kahl, Y., Knowledge Representation, Reasoning, and the Design of Intelligent Agents - The Answer-Set Programming Approach (2014), Cambridge University Press
[19] Gelfond, M.; Lifschitz, V., The stable model semantics for logic programming, (Kowalski, R.; Bowen, K., Proc. of Int’l Logic Programming (1988), MIT Press), 1070-1080
[20] Hughes, G. E.; Cresswell, M. J., An Introduction to Modal Logic (1968), Methuen and Co. Ltd.: Methuen and Co. Ltd. London, New York · Zbl 0205.00503
[21] Janhunen, T., Cross-translating answer set programs using the ASPTOOLS collection, KI: Künstl. Intell., 32, 183-184 (2018)
[22] Kleene, S., On notation for ordinal numbers, J. Symb. Log., 3, 150-155 (1938) · JFM 64.0932.03
[23] Kryszkiewicz, M., Rough set approach to incomplete information systems, Inf. Sci., 112, 39-49 (1998) · Zbl 0951.68548
[24] Kumar, A.; Banerjee, M., Kleene algebras and logic: Boolean and rough set representations, 3-valued, rough set and Perp semantics, Stud. Log., 105, 439-469 (2017) · Zbl 1417.03301
[25] Leone, N.; Pfeifer, G.; Faber, W.; Eiter, T.; Gottlob, G.; Perri, S.; Scarcello, F., The DLV system for knowledge representation and reasoning, ACM Trans. Comput. Log., 7, 499-562 (2006) · Zbl 1367.68308
[26] Lierler, Y., cmodels - SAT-based disjunctive answer set solver, (Logic Programming and Nonmonotonic Reasoning, 8th International Conference. Logic Programming and Nonmonotonic Reasoning, 8th International Conference, LPNMR 2005 (2005)), 447-451
[27] Lin, F.; Zhao, Y., ASSAT: computing answer sets of a logic program by SAT solvers, Artif. Intell., 157, 115-137 (2004) · Zbl 1085.68544
[28] Łukasiewicz, J., O logice trójwartościowej, Ruch Filoz., 5, 170-171 (1920), (in Polish); On three-valued logic, (Borkowski, L., Selected works by Jan Łukasiewicz (1970), North-Holland: North-Holland Amsterdam), 87-88, English translation:
[29] Niemelä, I.; Simons, P.; Soininen, T., Stable model semantics of weight constraint rules, (Gelfond, M.; Leone, N.; Pfeifer, G., Proc. LPNMR: 5th Conf. Logic Programming and Nonmonotonic Reasoning (1999), Springer), 317-331 · Zbl 0952.68029
[30] Pawlak, Z., Rough sets, Int. J. Comput. Inf. Sci., 11, 341-356 (1982) · Zbl 0501.68053
[31] Pawlak, Z., Rough Sets. Theoretical Aspects of Reasoning about Data (1991), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0758.68054
[32] Pawlak, Z.; Skowron, A., Rudiments of rough sets, Inf. Sci., 117, 3-27 (2007) · Zbl 1142.68549
[33] Polkowski, L.; Sets, Rough, Mathematical Foundations. Advances in Intelligent and Soft Computing, vol. 15 (2002), Physica-Verlag · Zbl 1040.68114
[34] Reiter, R., On closed world data bases, (Gallaire, H.; Minker, J., Logic and Data Bases (1978), Plenum Press), 55-76
[35] Reiter, R., A logic for default reasoning, Artificial Intelligence, 13, 81-132 (1980) · Zbl 0435.68069
[36] Simons, P.; Niemelä, I.; Soininen, T., Extending and implementing the stable model semantics, Artificial Intelligence, 138, 181-234 (2002) · Zbl 0995.68021
[37] Skowron, A.; Rauszer, C., The discernibility matrices and functions in information systems, (Slowiński, R., Intelligent Decision Support - Handbook of Applications and Advances of the Rough Sets Theory. Intelligent Decision Support - Handbook of Applications and Advances of the Rough Sets Theory, Theory and Decision Library, vol. 11 (1992), Springer), 331-362 · Zbl 0820.68001
[38] Słowiński, R.; Vanderpooten, D., Similarity relation as a basis for rough approximations, (Wang, P., Advances in Machine Intelligence & Soft Computing. Advances in Machine Intelligence & Soft Computing, Bookwrights, Raleigh NC (1997)), 17-33
[39] Słowiński, R.; Vanderpooten, D., A generalized definition of rough approximations based on similarity, IEEE Trans. Knowl. Data Eng., 12, 331-336 (2000)
[40] Van Benthem, J., Correspondence theory, (Gabbay, D.; Guenthner, F., Handbook of Philosophical Logic (1984), D. Reidel Pub. Co.), 167-247 · Zbl 0875.03048
[41] Yao, Y.; Wong, S.; Lin, T., A review of rough set models, (Lin, T.; Cercone, N., Rough Sets and Data Mining (1997), Springer), 47-75 · Zbl 0861.68101
[42] Zhang, Q.; Xie, Q.; Wang, G., A survey on rough set theory and its applications, CAAI Trans. Intell. Technol., 1, 323-333 (2016)
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.