مقاله PSPACE Tableau Algorithms for Acyclic Modalized TeX : تی پی بین

خلاصه مقاله

We study ALCKm and ALCS4m, which extend the description logic ALC by adding modal operators of the basic multi-modal logics K m and S4 m . We develop a sound and complete tableau algorithm ΛK for answering ALCKm queries w.r.t. an ALCKm knowledge base with an acyclic TBox. Defining tableau expansion rules in the presence of acyclic definitions by considering only the concept names on the left-hand side of TBox definitions or their negations, allows us to give a PSPACE implementation for ΛK. We then consider answering ALCS4m queries w.r.t. an ALCS4m knowledge base (with an acyclic TBox) in which the epistemic operators correspond to those of classical multi-modal logic S4 m . The expansion rules in the tableau algorithm Λ S4 are designed to syntactically incorporate the epistemic properties. Blocking is corporated into the tableau expansion rules to ensure termination. We also provide a PSPACE implementation for Λ S4. In light of the fact that the satisfiability problem for ALCKm with general TBox and no epistemic properties (i.e., KALC) is NEXPTIME-complete, we conclude that both ALCKm and ALCS4m offer computationally manageable and practically useful fragments of KALC

نویسندگان

Jia Tao [ Department of Computer Science, Iowa State University, Ames, IA, USA ]

Giora Slutzki [ Department of Computer Science, Iowa State University, Ames, IA, USA ]

Vasant Honavar [ Department of Computer Science, Iowa State University, Ames, IA, USA ]

کلمات کلیدی

Description logic $\ mathcal{ALC}$ Modal logic Tableau algorithm PSPACE

آدرس این مقاله

آدرس مستقیم دسترسی به این مقاله

مشخصات کنفرانس

مشاهده مقالات

Journal of Automated Reasoning 2013

The interdisciplinary Journal of Automated Reasoning balances theory, implementation and application. The spectrum of coverage ranges from the presentation of a new inference rule with proof of its logical properties to a detailed account of a computer program designed to solve various problems in industry. Topics include automated theorem proving, logic programming, expert systems, program synthesis and validation, artificial intelligence, computational logic, robotics, and various industrial applications. The contents focus on several aspects of automated reasoning, a field whose objective is the design and implementation of a computer program that serves as an assistant in solving problems and in answering questions that require reasoning. The Journal of Automated Reasoning provides a forum and a means for exchanging information for those interested purely in theory, those interested primarily in implementation, and those interested in specific research and industrial applications.

حوزه های تحت پوشش : automated theorem proving, logic programming, expert systems, program synthesis and validation, artificial intelligence, computational logic, robotics, and various industrial applications