Showing cs.LOShow all
3 papers · 1 filter
cs.LO2024
Data Complexity in Expressive Description Logics With Path Expressions
Bartosz Bednarczyk
We investigate the data complexity of the satisfiability problem for the very expressive description logic ZOIQ (a.k.a. ALCHb Self reg OIQ) over quasi-forests and establish its NP-…
cs.LO2022
Order-Invariance of Two-Variable Logic is coNExpTime-complete
Bartosz Bednarczyk
We establish coNExpTime-completeness of the problem of deciding order-invariance of a given two variable first-order formula, improving and significantly simplifying coTwoNExpTime…
cs.LO2016
Extending Two-Variable Logic on Trees
Bartosz Bednarczyk, Witold Charatonik, Emanuel Kieroński
The finite satisfiability problem for the two-variable fragment of first-order logic interpreted over trees was recently shown to be ExpSpace-complete. We consider two extensions o…