research
∙
07/19/2023
Exploring Non-Regular Extensions of Propositional Dynamic Logic with Description-Logics Features
We investigate the impact of non-regular path expressions on the decidab...
share
research
∙
05/04/2023
On the Limits of Decision: the Adjacent Fragment of First-Order Logic
We define the adjacent fragment AF of first-order logic, obtained by res...
research
∙
04/17/2023
About the Expressive Power and Complexity of Order-Invariance with Two Variables
Order-invariant first-order logic is an extension of first-order logic (...
research
∙
08/16/2022
Order-Invariance of Two-Variable Logic is coNExpTime-complete
We establish coNExpTime-completeness of the problem of deciding order-in...
research
∙
06/23/2022
Towards a Model Theory of Ordered Logics: Expressivity and Interpolation (Extended version)
We consider the family of guarded and unguarded ordered logics, that con...
research
∙
08/12/2021
Lutz's Spoiler Technique Revisited: A Unified Approach to Worst-Case Optimal Entailment of Unions of Conjunctive Queries in Locally-Forward Description Logics
We present a unified approach to (both finite and unrestricted) worst-ca...
research
∙
06/29/2021
On Classical Decidable Logics extended with Percentage Quantifiers and Arithmetics
During the last decades, a lot of effort was put into identifying decida...
research
∙
06/29/2021
The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2ExpTime-hard
In logic-based knowledge representation, query answering has essentially...
research
∙
04/27/2021
Why Propositional Quantification Makes Modal and Temporal Logics on Trees Robustly Hard?
Adding propositional quantification to the modal logics K, T or S4 is kn...
research
∙
07/16/2020
Modal Logics with Composition on Finite Forests: Expressivity and Complexity (Extra Material)
We investigate the expressivity and computational complexity of two moda...
research
∙
07/02/2020
"Most of" leads to undecidability: Failure of adding frequencies to LTL
Linear Temporal Logic (LTL) interpreted on finite traces is a robust spe...
research
∙
02/14/2020
Satisfiability and Query Answering in Description Logics with Global and Local Cardinality Constraints
We introduce and investigate the expressive description logic (DL) ALCSC...
research
∙
11/02/2019
Statistical EL is ExpTime-complete
We show that consistency of Statistical EL knowledge bases, as defined b...
research
∙
12/11/2018
On the Complexity of Graded Modal Logics with Converse
A complete classification of the complexity of the local and global sati...
research
∙
10/25/2018
The One-Variable Logic Meets Presburger Arithmetic
We consider the one-variable fragment of first-order logic extended with...
research
∙
10/16/2017