# On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)

arXiv: https://arxiv.org/abs/2501.13762 · HTML: https://mlsanity.com/paper/2501.13762/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 51 references that are in the map.
- First posted on arXiv 23 Jan 2025.

## Builds on (most cited first, 9 of 9)

- [The DL-Lite Family and Relations](https://mlsanity.com/paper/1401.3487/) (2014)
- [Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP](https://mlsanity.com/paper/1301.6479/) (2013)
- [Querying Log Data with Metric Temporal Logic (Technical Report)](https://mlsanity.com/paper/1703.08982/) (2017)
- [MeTeoR: Practical Reasoning in Datalog with Metric Temporal Operators](https://mlsanity.com/paper/2201.04596/) (2022)
- [Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic under the Event-Based Semantics (Full Version)](https://mlsanity.com/paper/1905.12990/) (2019)
- [Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics](https://mlsanity.com/paper/1701.02231/) (2017)
- [First-Order Rewritability of Ontology-Mediated Queries in Linear Temporal Logic](https://mlsanity.com/paper/2004.07221/) (2020)
- [The Complexity of Clausal Fragments of LTL](https://mlsanity.com/paper/1306.5088/) (2013)
- [Deciding FO-rewritability of regular languages and ontology-mediated queries in Linear Temporal Logic](https://mlsanity.com/paper/2207.06210/) (2022)

## Built on by (most cited first, 1 of 1)

- [Analysing Temporal Reasoning in Description Logics Using Formal Grammars](https://mlsanity.com/paper/2508.00575/) (2025)

## Abstract (arXiv)

Our concern is the data complexity of answering linear monadic datalog queries whose atoms in the rule bodies can be prefixed by operators of linear temporal logic LTL. We first observe that, for data complexity, answering any connected query with operators bigcirc/bigcirc^- (at the next/previous moment) is either in AC0, or in ACC0!setminus!AC0, or NC1-complete, or LogSpace-hard and in NLogSpace. Then we show that the problem of deciding LogSpace-hardness of answering such queries is PSpace-complete, while checking membership in the classes AC0 and ACC0 as well as NC1-completeness can be done in ExpSpace. Finally, we prove that membership in AC0 or in ACC0, NC1-completeness, and LogSpace-hardness are undecidable for queries with operators Diamondf/Diamondp (sometime in the future/past) provided that NC1 ne NLogSpace, and LogSpace ne NLogSpace.