Cover Image

Spectra of Cardinality Queries over Description Logic Knowledge Bases

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Manière, Quentin, Przybyłko, Marcin
Format:	Preprint
Published:	2024
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

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

Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster
by: Lutz, Carsten, et al.
Published: (2024)

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

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

On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)
by: Artale, Alessandro, et al.
Published: (2025)

Exploiting Uncertainty for Querying Inconsistent Description Logics Knowledge Bases
by: Zese, Riccardo, et al.
Published: (2023)

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

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

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

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

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

Near-Optimal Encodings of Cardinality Constraints
by: Krapivin, Andrew, et al.
Published: (2026)

Queries With Exact Truth Values in Paraconsistent Description Logics
by: Bienvenu, Meghyn, et al.
Published: (2024)

Partially Finite Model Reasoning in Description Logics Extended Version
by: Gogacz, Tomasz, et al.
Published: (2026)

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

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

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

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

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

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

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

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

Aspects of Coherence in Dependence Logic
by: Barlag, Timon, et al.
Published: (2026)

Logic and Computation through the Lens of Semirings
by: Barlag, Timon, et al.
Published: (2025)

Incremental, inconsistency-resilient reasoning over Description Logic Abox streams
by: Proost, Cas, et al.
Published: (2026)

On the Descriptive Complexity of Vertex Deletion Problems
by: Bannach, Max, et al.
Published: (2024)

The Descriptive Complexity of Relation Modification Problems
by: Chudigiewitsch, Florian, et al.
Published: (2026)

Finite Variable Counting Logics with Restricted Requantification
by: Raßmann, Simon, et al.
Published: (2024)

Epistemic Skills: Logical Dynamics of Knowing and Forgetting
by: Liang, Xiaolong, et al.
Published: (2024)

Logics with probabilistic team semantics and the Boolean negation
by: Hannula, Miika, et al.
Published: (2023)

Query maintenance under batch changes with small-depth circuits
by: Datta, Samir, et al.
Published: (2024)

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

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

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

On the Logical Content of Knowledge Bases
by: Gheorghiu, Alexader V., et al.
Published: (2025)

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

Constructive Interpolation and Concept-Based Beth Definability for Description Logics via Sequents
by: Lyon, Tim S., et al.
Published: (2024)

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

Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
by: Barto, Libor, et al.
Published: (2021)

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
by: Kazakov, Yevgeny, et al.
Published: (2009)