Advertisement
Published in:
2006 | OriginalPaper | Chapter
The Data Complexity of MDatalog in Basic Modal Logics
Author : Linh Anh Nguyen
Published in: Mathematical Foundations of Computer Science 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study the data complexity of the modal query language MDatalog and its extension eMDatalog in basic modal logics. MDatalog is a modal extension of Datalog, while eMDatalog is the general modal Horn fragment with the allowedness condition. As the main results, we prove that the data complexity of MDatalog and eMDatalog in
K
4,
KD
4, and
S
4 is PSPACE-complete, in
K
is coNP-complete, and in
KD
,
T
,
KB
,
KDB
, and
B
is PTIME-complete.