Characterizing the Expressive Power for Concept Descriptions and Terminological Axioms Boxes in the Description Logic εLU
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    The two most important properties of a logic are its expressive power and the complexity of reasoning, which are also an opposing relation in the logic. Bisimulations between interpretations are effective way to characterize the expressive power, and the van Benthem characterization theorem is a classical result which gives an exact condition for when a first-order formula with one free variable is equivalent to a modal logic formula. This paper provides a simulation for εLU (including atomic concept, top concept, conjunction concept, disjunction concept, and existential quantification). Based on the simulation, the characterization theorems of expressive power for concept descriptions and TBoxes are established to give the sufficient and necessary conditions for when a first-order formula is equivalent to a concept description or a TBox are set up. The above results provide effective supports for the tradeoff between the expressive power and the complexity of reasoning problems.

    Reference
    Related
    Cited by
Get Citation

申宇铭,王驹,唐素勤.描述逻辑εLU概念及术语公理集的表达能力刻画.软件学报,2014,25(8):1794-1805

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:December 13,2012
  • Revised:June 21,2013
  • Adopted:
  • Online: August 01,2014
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063