Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic under the Event-Based Semantics Article Swipe
Vladislav Ryzhikov
,
Przemysław Andrzej Wałęga
,
Michael Zakharyaschev
·
YOU?
·
· 2019
· Open Access
·
· DOI: https://doi.org/10.24963/ijcai.2019/256
YOU?
·
· 2019
· Open Access
·
· DOI: https://doi.org/10.24963/ijcai.2019/256
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.
Related Topics To Compare & Contrast
Concepts
Datalog
Computer science
Transitive closure
Description logic
Semantics (computer science)
Ontology
Theoretical computer science
Conjunctive query
Recursion (computer science)
Event (particle physics)
Temporal logic
Programming language
Information retrieval
Mathematics
Discrete mathematics
Relational database
Physics
Epistemology
Quantum mechanics
Philosophy
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.24963/ijcai.2019/256
- https://www.ijcai.org/proceedings/2019/0256.pdf
- OA Status
- gold
- Cited By
- 21
- References
- 32
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W2965511917
All OpenAlex metadata
Raw OpenAlex JSON
No additional metadata available.