Experimental analysis of some computation rules in a simple parallel reasoning system for the ALC description logic

Adam Meissner

International Journal of Applied Mathematics and Computer Science, Tome 21 (2011), p. 83-95 / Harvested from The Polish Digital Mathematics Library

Résumé

A computation rule determines the order of selecting premises during an inference process. In this paper we empirically analyse three particular computation rules in a tableau-based, parallel reasoning system for the ALC description logic, which is built in the relational programming model in the Oz language. The system is constructed in the lean deduction style, namely, it has the form of a small program containing only basic mechanisms, which assure soundness and completeness of reasoning. In consequence, the system can act as a convenient test-bed for comparing various inference algorithms and their elements. We take advantage of this property and evaluate the studied methods of selecting premises with regard to their efficiency and speedup, which can be obtained by parallel processing.

Détail

Publié le : 2011-01-01

Zbl 1221.68239

EUDML-ID : urn:eudml:doc:208039

Bibliographie

[000] Amir, E. and Maynard-Zhang, P. (2004). Logic-based subsumption architecture, Artificial Intelligence 153(1-2): 167-237. | Zbl 1085.68680

[001] Aslani, M.and Haarslev, V. (2008). Towards parallel classifcation of TBoxes, in F. Baader, C. Lutz, and B. Motik (Eds.), Proceedings of the 21st International Workshop on Description Logics (DL2008), CEUR Workshop Proceedings, Vol. 353.

[002] Baader, F., McGuinness, D., Nardi, D. and Patel-Schneider, P. (Eds.) (2003). The Description Logic Handbook: Theory, Implementation, and Applications, Cambridge University Press, Cambridge. | Zbl 1058.68107

[003] Baader, F. and Sattler, U. (2001). An overview of tableau algorithms for description logics, Studia Logica 69(1): 5-40. | Zbl 0991.03012

[004] Beckert, B. and Possega, J. (1995). lean$T^{A}P$ : Lean, tableau-based deduction, Journal of Automated Reasoning 15(3): 339-358. | Zbl 0838.68097

[005] Calvanese, D., Lenzerini, M. and Nardi, D. (1999). Unifying class-based representation formalisms, Journal of Artificial Intelligence Research 11: 199-240. | Zbl 0924.68184

[006] De Giacomo, G., Iocchi, L., Nardi, D. and Rosati R. (1996). Moving a robot: The KR&R approach at work, Proceedings of the 5th International Conference on Principles of Knowledge Representation and Reasoning, Cambridge, MA, USA, pp. 198-209.

[007] Devanbu, P. and Jones, M. (1997). The use of description logics in KBSE systems, ACM Transactions on Software Engineering and Methodology 6(2): 141-172.

[008] Herchenröder, T. (2006). Lightweight Semantic Web Oriented Reasoning in Prolog: Tableaux Inference for Description Logics, M.Sc. thesis, University of Edinburgh, Edinburgh.

[009] Horrocks, I. and Patel-Schneider, P.F. (1998). DL systems comparison (summary relation), Proceedings of the 1998 International Workshop on Description Logics (DL'98), CEUR Workshop Proceedings, Vol. 11, pp. 55-57.

[010] Hustadt, U., Motik, B. and Sattler, U. (2004). Reducing SHIQdescription logic to disjunctive datalog programs, in D. Dubois, C.A. Welty and M.-A. Williams (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Ninth International Conference (KR2004), AAAI Press, Menlo Park, CA, pp. 152-162.

[011] Liebig, T. and Müller, F. (2007). Parallelizing tableaux-based description logic reasoning, in R. Meersman, Z. Tari, and P. Herrero (Eds.), On the Move to Meaningful Internet Systems 2007: OTM 2007 Workshops, Lecture Notes in Computer Science, Vol. 4806, Springer-Verlag, Berlin/Heidelberg, pp. 1135-1144.

[012] Meissner, A. (2009a). Introducing parsimonious rules to a parallel reasoning system for the ALC description logic, Proceedings of the 7th Conference on Computer Methods and Systems, CMS'09, Cracow, Poland, pp. 75-80.

[013] Meissner, A. (2009b). A simple parallel reasoning system for the ALC description logic, in N.T. Nguyen, R. Kowalczyk, and S.-M. Chen (Eds.), Computational Collective Intelligence. Semantic Web, Social Networks and Multiagent Systems: Proceedings of the First International Conference, ICCCI 2009, Lecture Notes in Artificial Intelligence, Vol. 5796, Springer-Verlag, Berlin/Heidelberg, pp. 413-424.

[014] OWL Web Ontology Language Overview (2004), http://www.w3.org/TR/owl-features/.

[015] Rector A.L., Zanstra, P., Solomon, W., Rogers, J., Baud, R., Ceusters, W., Claassen, A., Kirby, J., Rodrigues, J., Mori, A., van der Haring, E. and Wagner, J. (1998). Reconciling users' needs and formal requirements: Issues in developing a reusable ontology for medicine, IEEE Transactions on Information Technology in Biomedicine 2(4): 229-242.

[016] Rychtyckyj, N. (1996). DLMS: An evaluation of KL-ONE in the automobile industry, in L.C. Aiello, J. Doyle, and S.C. Shapiro (Eds.), Proceedings of the 5th International Conference on Principles of Knowledge Representation and Reasoning (KR'96), Morgan Kaufmann, San Francisco, CA, pp. 588-596.

[017] Schmidt-Schauß, M. and Smolka, G. (1991). Attributive concept descriptions with complements, Artificial Intelligence 48(1): 1-26. | Zbl 0712.68095

[018] Schulte, C. (2000). Programming Constraint Services, Ph.D. thesis, Saarland University, Saarbrücken. | Zbl 0994.68038

[019] Semantic Web (2001). http://www.w3.org/2001/sw/.

[020] The Mozart Programming System (2008). http://www.mozart-oz.org.

[021] Tsarkov, D. and Horrocks, I. (2006). FaCT++ description logic reasoner: System description, in U. Furbach and N. Shankar (Eds.), Automated Reasoning: Third International Joint Conference, IJCAR 2006, Lecture Notes in Computer Science, Vol. 4130, Springer-Verlag, Berlin/Heidelberg, pp. 292-297.

[022] Van Roy, P. and Haridi, S. (2004). Concepts, Techniques, and Models of Computer Programming, MIT Press, Cambridge, MA.

[023] Wessel, M. and Möller, R. (2005). A high performance Semantic Web query answering engine, in I. Horrocks, U. Sattler and F. Wolter (Eds.), Proceedings of the 2005 International Workshop on Description Logics (DL2005), CEUR Workshop Proceedings, Vol. 147.