Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Artale, Alessandro, Gnatenko, Anton, Ryzhikov, Vladislav, Zakharyaschev, Michael
Format:	Preprint
Published:	2025
Subjects:	Artificial Intelligence Computational Complexity Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Symmetric Linear Arc Monadic Datalog and Gadget Reductions
by: Bodirsky, Manuel, et al.
Published: (2024)

Datalog-Expressibility for Monadic and Guarded Second-Order Logic
by: Bodirsky, Manuel, et al.
Published: (2020)

Unique Characterisability and Learnability of Temporal Queries Mediated by an Ontology
by: Jung, Jean Christoph, et al.
Published: (2023)

On Probabilistic and Causal Reasoning with Summation Operators
by: Ibeling, Duligur, et al.
Published: (2024)

Data Complexity in Expressive Description Logics With Path Expressions
by: Bednarczyk, Bartosz
Published: (2024)

Verifying Quantized GNNs With Readout Is Decidable But Highly Intractable
by: Chernobrovkin, Artem, et al.
Published: (2025)

Spectra of Cardinality Queries over Description Logic Knowledge Bases
by: Manière, Quentin, et al.
Published: (2024)

Analysing Temporal Reasoning in Description Logics Using Formal Grammars
by: Bourgaux, Camille, et al.
Published: (2025)

Complexity of Faceted Explanations in Propositional Abduction
by: Schmidt, Johannes, et al.
Published: (2025)

Epistemic Logic Programs: Non-Ground and Counting Complexity
by: Eiter, Thomas, et al.
Published: (2025)

From Time to Space: The Impact of Linearity in Higher-Order Datalog
by: Charalambidis, Angelos, et al.
Published: (2026)

Proof Complexity of Linear Logics
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2026)

FormulaOne: Measuring the Depth of Algorithmic Reasoning Beyond Competitive Programming
by: Beniamini, Gal, et al.
Published: (2025)

Data-Complexity of the Two-Variable Fragment with Counting Quantifiers
by: Pratt-Hartmann, Ian
Published: (2008)

2-ASP(Q) programs with weak constraints: Complexity and efficient implementation
by: Cuteri, Andrea, et al.
Published: (2026)

The Power of Negation in Higher-Order Datalog
by: Charalambidis, Angelos, et al.
Published: (2025)

The Computational Complexity of Satisfiability in State Space Models
by: Alsmann, Eric, et al.
Published: (2025)

Measuring Decidability as Related to Busy Beaver Numbers
by: Tandi, Gurpreet, et al.
Published: (2026)

Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning
by: Sälzer, Marco, et al.
Published: (2024)

Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Integer Linear Arithmetic
by: Gokaj, Geri, et al.
Published: (2025)

Epistemic Skills: Reasoning about Knowledge and Oblivion
by: Liang, Xiaolong, et al.
Published: (2025)

Solving Satisfiability Modulo Counting for Symbolic and Statistical AI Integration With Provable Guarantees
by: Li, Jinzhao, et al.
Published: (2023)

A Theory of Formalisms for Representing Knowledge
by: Zhang, Heng, et al.
Published: (2024)

Rejection in Abstract Argumentation: Harder Than Acceptance?
by: Fichte, Johannes K., et al.
Published: (2024)

Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete
by: Ghosh, Avijeet, et al.
Published: (2025)

Probabilistic and Causal Satisfiability: Constraining the Model
by: Bläser, Markus, et al.
Published: (2025)

Minimal Model Reasoning in Description Logics: Don't Try This at Home!
by: Di Stefano, Federica, et al.
Published: (2025)

Efficient Inference and Computation of Optimal Alternatives for Preference Languages Based On Lexicographic Models
by: Wilson, Nic, et al.
Published: (2024)

Compilation and Fast Model Counting beyond CNF
by: de Colnet, Alexis, et al.
Published: (2025)

Meta Operator for Complex Query Answering on Knowledge Graphs
by: Yin, Hang, et al.
Published: (2024)

Effective Versions of Strong Measure Zero
by: Rayman, Matthew
Published: (2025)

The Complexity and Expressive Power of Second-Order Extended Logic
by: Feng, Shiguang, et al.
Published: (2022)

Extremal Separation Problems for Temporal Instance Queries
by: Jung, Jean Christoph, et al.
Published: (2024)

On the Complexity of the Numerically Definite Syllogistic and Related Fragments
by: Pratt-Hartmann, Ian
Published: (2007)

The Scaling Properties of Implicit Deductive Reasoning in Transformers
by: Vompa, Enrico, et al.
Published: (2026)

Object-Centric Conformance Alignments with Synchronization (Extended Version)
by: Gianola, Alessandro, et al.
Published: (2023)

On the Boolean Network Theory of Datalog$^\neg$
by: Trinh, Van-Giang, et al.
Published: (2025)

Meta-Mathematics of Computational Complexity Theory
by: Oliveira, Igor C.
Published: (2025)

Deciding the Existence of Interpolants and Definitions in First-Order Modal Logic
by: Kurucz, Agi, et al.
Published: (2023)

The Sticky Path to Expressive Querying: Decidability of Navigational Queries under Existential Rules
by: Ostropolski-Nalewaja, Piotr, et al.
Published: (2024)