Conference item icon

Conference item

Data complexity and rewritability of ontology-mediated queries in metric temporal logic under the event-based semantics

Abstract:
We investigate the data complexity of answering queries mediated by metric temporal logic ontologies under the event-based semantics assuming that data instances are finite timed words timestamped with binary fractions. We identify classes of ontology-mediated queries answering which can be done in AC0, NC1, L, NL, P, and coNP for data complexity, provide their rewritings to first-order logic and its extensions with primitive recursion, transitive closure or datalog, and establish lower complexity bounds.
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
  • (Version of record, pdf, 195.3KB)
Publisher copy:
10.24963/ijcai.2019/256

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More from this funder
Name:
Engineering and Physical Sciences Research Council
Grant:
EP/K00607X/1
Publisher:
International Joint Conferences on Artificial Intelligence Organization
Host title:
Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, (IJCAI-19)
Journal:
28th International Joint Conference on Artificial Intelligence More from this journal
Pages:
1851-1857
Publication date:
2019-07-28
Acceptance date:
2019-05-10
DOI:
ISBN:
9780999241141
Pubs id:
pubs:1014908
UUID:
uuid:ab11db37-fdad-492d-a7b4-8249063041f5
Local pid:
pubs:1014908
Source identifiers:
1014908
Deposit date:
2019-06-17

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP