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 (2011)

  • Volume: 21, Issue: 1, page 83-95
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Adam Meissner. "Experimental analysis of some computation rules in a simple parallel reasoning system for the ALC description logic." International Journal of Applied Mathematics and Computer Science 21.1 (2011): 83-95. <http://eudml.org/doc/208039>.

@article{AdamMeissner2011,
abstract = {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.},
author = {Adam Meissner},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {parallel reasoning; lean deduction; ALC description logic; Oz language; description logic},
language = {eng},
number = {1},
pages = {83-95},
title = {Experimental analysis of some computation rules in a simple parallel reasoning system for the ALC description logic},
url = {http://eudml.org/doc/208039},
volume = {21},
year = {2011},
}

TY - JOUR
AU - Adam Meissner
TI - Experimental analysis of some computation rules in a simple parallel reasoning system for the ALC description logic
JO - International Journal of Applied Mathematics and Computer Science
PY - 2011
VL - 21
IS - 1
SP - 83
EP - 95
AB - 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.
LA - eng
KW - parallel reasoning; lean deduction; ALC description logic; Oz language; description logic
UR - http://eudml.org/doc/208039
ER -

References

top
  1. Amir, E. and Maynard-Zhang, P. (2004). Logic-based subsumption architecture, Artificial Intelligence 153(1-2): 167-237. Zbl1085.68680
  2. 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. 
  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. Zbl1058.68107
  4. Baader, F. and Sattler, U. (2001). An overview of tableau algorithms for description logics, Studia Logica 69(1): 5-40. Zbl0991.03012
  5. Beckert, B. and Possega, J. (1995). lean T A P : Lean, tableau-based deduction, Journal of Automated Reasoning 15(3): 339-358. Zbl0838.68097
  6. Calvanese, D., Lenzerini, M. and Nardi, D. (1999). Unifying class-based representation formalisms, Journal of Artificial Intelligence Research 11: 199-240. Zbl0924.68184
  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 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. 
  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. Zbl0712.68095
  19. Schulte, C. (2000). Programming Constraint Services, Ph.D. thesis, Saarland University, Saarbrücken. Zbl0994.68038
  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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.