Logic Programming Representation of the Compound Term Composition Algebra

• Autorzy: Analyti A. , Pachoulakis I.
• Języki publikacji: EN

Abstrakty

EN

The Compound Term Composition Algebra (CTCA) is an algebra with four algebraic operators, which can be used to generate the valid (meaningful) compound terms of a given faceted taxonomy, in an efficient and flexible manner. The positive operations allow the derivation of valid compound terms through the declaration of a small set of valid compound terms. The negative operations allow the derivation of valid compound terms through the declaration of a small set of invalid compound terms. In this paper, we show how CTCA can be represented in logic programming with negation-as-failure, according to both Clark's and well-founded semantics. Indeed, the SLDNF-resolution can be used for checking compound term validity and well-formedness of an algebraic expression in polynomial time w.r.t. the size of the expression and the number of terms in the taxonomy. This result makes our logic programming representation a competitive alternative to imperative algorithms. Embedding of our logic programming representation to the programming environment of a web portal for a computer sales company is demonstrated.

Słowa kluczowe

EN

faceted taxonomies; Logic Programming (LP); computational complexity; application

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 3
• Strony: 321--360
• Opis fizyczny: bibliogr. 36 poz., wykr.

Twórcy

autor

Analyti A.

autor

Pachoulakis I.

• Institute of Computer Science, FORTH-ICS, Crete, Greece,

Bibliografia

• [1] "XFML: eXchangeable Faceted Metadata Language". http://www.xfml.org.
• [2] "XFML+CAMEL:Compound term composition Algebraically-Motivated Expression Language". http://www.csi.forth.gr/markup/xfml+camel.
• [3] J. J. Alferes, C. V. Damásio, and L. M. Pereira. "SemanticWeb Logic Programming Tools". In International Workshop on Principles and Practice of Semantic Web Reasoning (PPSWR'03), pages 16-32, 2003.
• [4] Krzysztof R. Apt and Roland N. Bol. "Logic Programming and Negation: A Survey". Journal of Logic Programming, 19/20:9-71, 1994.
• [5] S. Battle, A. Bernstein, H. Boley, B. Grosof, M. Gruninger, R. Hull, M. Kifer, D. Martin, S. McIlraith, D. McGuinness, J. Su, and S. Tabet. "Semantic Web Services Language (SWSL)". W3C Member Submission, 9 September 2005. Available at http://www.w3.org/Submission/2005/SUBM/SWSF-SWSL-20050909/.
• [6] W. Chen, T. Swift, and D. S. Warren. "Efficient Top-Down Computation of Queries under theWell-Founded Semantics". Journal of Logic Programming, 24(3):161-199, 1995.
• [7] W. Chen and D. S. Warren. "Query Evaluation under the Well Founded Semantics". In 12th ACM SIGACTSIGMOD-SIGART Symposium on Principles of Database Systems (PODS-1993), pages 168-179. ACM Press, May 1993.
• [8] K. L. Clark. " Negation as Failure". In Logic and Data Bases, pages 293-322. Plenum Press, 1978.
• [9] F.M. Donini,M. Lenzerini, D. Nardi, and A. Schaerf. "Reasoning in Description Logics". In Gerhard Brewka, editor, Principles of Knowledge Representation, chapter 1, pages 191-236. CSLI Publications, 1996.
• [10] Elizabeth B. Duncan. "A Faceted Approach to Hypertext". In Ray McAleese, editor, HYPERTEXT: theory into practice, BSP, pages 157-163, 1989.
• [11] P. A. Fejer and D. A. Simovici. "Mathematical Foundations of Computer Science. Volume 1: Sets, Relations, and Induction". Springer-Verlag, 1991.
• [12] A. Van Gelder, K. A. Ross, and J. S. Schlipf. "The Well-Founded Semantics for General Logic Programs". Journal of the ACM, 38(3):620-650, 1991.
• [13] B. N. Grosof. "Representing e-commerce rules via situated courteous logic programs in RuleML". Electronic Commerce Research and Applications, 3(1):2-20, 2004.
• [14] B. N. Grosof, Y. Labrou, and H. Y. Chan. "A declarative approach to business rules in contracts: courteous logic programs in XML". In 1st ACM Conference on Electronic Commerce (EC-1999), pages 68-77, 1999.
• [15] Patrick Hayes. "RDF Semantics". W3C Recommendation, 10 February 2004. Available at http://www.w3.org/TR/2004/REC-rdf-mt-20040210
• [16] I. Horrocks and P. F. Patel-Schneider. "Reducing OWL Entailment to Description Logic Satisfiability". In 2nd International Semantic Web Conference (ISWC-2003), pages 17-29, October 2003.
• [17] International Organization For Standardization. "Documentation - Guidelines for the establishment and development of monolingual thesauri", 1986. Ref. No ISO 2788-1986.
• [18] G. Klyne and J. J. Carroll. "Resource Description Framework (RDF): Concepts and Abstract Syntax". W3C Recommendation, 10 February 2004. Available at http://www.w3.org/TR/2004/REC-rdf-concepta-20040210
• [19] P. H. Lindsay and D. A. Norman. Human Information Processing. Academic press, New York, 1977.
• [20] J.W. Lloyd. Foundations of Logic Programming. Springer-Verlag, second edition, 1987.
• [21] Amanda Maple. "Faceted Access: A Review of the Literature", 1995. http://theme.music.indiana.edu/tech s/mla/facacc.rev.
• [22] D. L. McGuinness and F. van Harmelen. "OWL Web Ontology Language Overview". W3C Recommendation, 10 February 2004. Available at http://www.w3.org/TR/2004/REC-owl-features-20040210
• [23] Ruben Prieto-Diaz. "Classification of Reusable Modules". In Software Reusability. Volume I, chapter 4, pages 99-123. ACM Press, 1989.
• [24] Ruben Prieto-Diaz. "Implementing Faceted Classification for Software Reuse". Communications of the ACM, 34(5):88-97, 1991.
• [25] U. Priss and E. Jacob. "Utilizing Faceted Structures for Information Systems Design". In Proceedings of the ASIS Annual Conf. on Knowledge: Creation, Organization, and Use (ASIS'99), October 1999.
• [26] T. C. Przymusinski. "Well-founded and Stationary Models of Logic Programs". Annals of Mathematics and Artificial Intelligence, 12(3-4):141-187, 1994.
• [27] S. R. Ranganathan. "The Colon Classification". In Susan Artandi, editor, Vol IV of the Rutgers Series on Systems for the Intellectual Organization of Information. New Brunswick, NJ: Graduate School of Library Science, Rutgers University, 1965.
• [28] P. Rao, K. F. Sagonas, T. Swift, D. S. Warren, and J. Freire. "XSB: A System for Efficiently Computing WFS". In Proceedings of 4th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'97), pages 1070-1080, July 1997.
• [29] "The Rule Markup Initiative (RuleML)". Available at http://www.rulemel.org
• [30] K. Sagonas, T. Swift, and D. S. Warren. "XSB as an efficient deductive database engine". In Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data (SIGMOD'94), pages 442-453, 1994.
• [31] Y. Tzitzikas, A. Analyti, N. Spyratos, and P. Constantopoulos. "An Algebraic Approach for Specifying Compound Terms in Faceted Taxonomies". In Information Modelling and Knowledge Bases XV, 13th European-Japanese Conference on Information Modelling and Knowledge Bases, EJC'03, pages 67-87. IOS Press, 2004.
• [32] Y. Tzitzikas, R. Launonen,M. Hakkarainen, P. Kohonen, T. Leppanen, E. Simpanen, H. Tornroos, P. Uusitalo, and P. Vanska. "FASTAXON: A system for FAST (and Faceted) TAXONomy design". In Procs. of 23th Int. Conf. on Conceptual Modeling, ER'2004, Shanghai, China, November 2004. (an on-line demo is available at http://fastaxon.erve.vtt.fi/).
• [33] Yannis Tzitzikas, Anastasia Analyti, and Nicolas Spyratos. "Compound Term Composition Algebra: The Semantics". LNCS Journal on Data Semantics, 2:58-84, 2005.
• [34] B. C. Vickery. "Knowledge Representation: A Brief Review". Journal of Documentation, 42(3):145-159, 1986.
• [35] Jan Wielemaker. "An overview of the SWI-Prolog Programming Environment". In 13th International Workshop on Logic Programming Environments, pages 1-16, December 2003.
• [36] K. Yee, K. Swearingen, K. Li, and M. Hearst. "Faceted Metadata for Image Search and Browsing". In Proceedings of the Conf. on Human Factors in Computing Systems (CHI'03), pages 401-408, April 2003.