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

• Autorzy: Meissner A.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

parallel reasoning; lean deduction; ALC description logic; Oz language

PL

wnioskowanie równoległe; logika opisowa

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2011
• Tom: Vol. 21, no 1
• Strony: 83--95
• Opis fizyczny: Bibliogr. 24 poz., rys., tab.

Twórcy

autor

Meissner A.

• Institute of Control and Information Engineering, Poznań University of Technology, pl. M. Skłodowskiej-Curie 5, 60-965 Poznań, Poland,

Bibliografia

• [1] Amir, E. and Maynard-Zhang, P. (2004). Logic-based subsumption architecture, Artificial Intelligence 153(1-2): 167-237.
• [2] Aslani, M.and Haarslev, V. (2008). Towards parallel classification 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.
• [3] Baader, F., McGuinness, D., Nardi, D. and Patel-Schneider, P. (Eds.) (2003). The Description Logic Handbook: Theory, Implementation, and Applications, Cambridge University Press, Cambridge.
• [4] Baader, F. and Sattler, U. (2001). An overview of tableau algorithms for description logics, Studia Logica 69(1): 5-40.
• [5] Beckert, B. and Possega, J. (1995). leanTAP: Lean, tableau-based deduction, Journal of Automated Reasoning 15(3): 339-358.
• [6] Calvanese, D., Lenzerini, M. and Nardi, D. (1999). Unifying class-based representation formalisms, Journal of Artificial Intelligence Research 11: 199-240.
• [7] 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.
• [8] 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.
• [9] Herchenröder, T. (2006). Lightweight Semantic Web Oriented Reasoning in Prolog: Tableaux Inference for Description Logics, M.Sc. thesis, University of Edinburgh, Edinburgh.
• [10] 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.
• [11] Hustadt, U., Motik, B. and Sattler, U. (2004). Reducing SHIQ-description 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.
• [12] 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.
• [13] 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.
• [14] 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.
• [15] OWL Web Ontology Language Overview (2004), http://www.w3.org/TR/owl-features/.
• [16] 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.
• [17] 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.
• [18] Schmidt-Schauß, M. and Smolka, G. (1991). Attributive concept descriptions with complements, Artificial Intelligence 48(1): 1-26.
• [19] Schulte, C. (2000). Programming Constraint Services, Ph.D. thesis, Saarland University, Saarbrücken.
• [20] Semantic Web (2001). http://www.w3.org/2001/sw/.
• [21] The Mozart Programming System (2008). http://www.mozart-oz.org.
• [22] 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.
• [23] Van Roy, P. and Haridi, S. (2004). Concepts, Techniques, and Models of Computer Programming, MIT Press, Cambridge, MA.
• [24] 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.