On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators (Extended Version)
Alessandro Artale, Anton Gnatenko, Vladislav Ryzhikov, Michael Zakharyaschev · 2025
Read On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators (Extended Version) by Alessandro Artale, Anton Gnatenko, Vladislav Ryzhikov, Michael Zakharyaschev (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-13762.txt.
Description
Alessandro Artale, Anton Gnatenko, Vladislav Ryzhikov, and Michael Zakharyaschev study how hard it is to answer certain database queries, in a paper from twenty twenty-five. The queries use simple rules extended with time operators, such as next moment or sometime in the future. Cost is measured against the size of the data alone.
For queries using only next and previous steps, the authors sort all cases into a few cost classes. They then ask how hard it is to tell which class a query falls in, and give matching upper and lower bounds. For queries with sometime operators, the picture darkens: most of these sorting questions cannot be decided at all, under standard assumptions.
Catalog record
| CREATOR | Alessandro Artale, Anton Gnatenko, Vladislav Ryzhikov, Michael Zakharyaschev |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 137 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-13762