13 citations · 15 across the 4 of their papers we have counts for
9 papers · 1 filter
The Adjacent Fragment and Quine's Limits of Decision
Bartosz Bednarczyk, Daumantas Kojelis, Ian Pratt-Hartmann
We introduce the adjacent fragment AF of first-order logic, obtained by restricting the sequences of variables occurring as arguments in atomic formulas. The adjacent fragment gene…
Lutz's Spoiler Technique Revisited: A Unified Approach to Worst-Case Optimal Entailment of Unions of Conjunctive Queries in Locally-Forward Description Logics
Bartosz Bednarczyk
We present a unified approach to (both finite and unrestricted) worst-case optimal entailment of (unions of) conjunctive queries (U)CQs in the wide class of "locally-forward" descr…
On Classical Decidable Logics extended with Percentage Quantifiers and Arithmetics
Bartosz Bednarczyk, Maja Orłowska, Anna Pacanowska +1
During the last decades, a lot of effort was put into identifying decidable fragments of first-order logic. Such efforts gave birth, among the others, to the two-variable fragment…
The Price of Selfishness: Conjunctive Query Entailment for ALCSelf is 2ExpTime-hard
Bartosz Bednarczyk, Sebastian Rudolph
In logic-based knowledge representation, query answering has essentially replaced mere satisfiability checking as the inferencing problem of primary interest. For knowledge bases i…
Modal Logics with Composition on Finite Forests: Expressivity and Complexity (Extra Material)
Bartosz Bednarczyk, Stéphane Demri, Raul Fervari +1
We investigate the expressivity and computational complexity of two modal logics on finite forests equipped with operators to reason on submodels. The logic ML(|) extends the basic…
"Most of" leads to undecidability: Failure of adding frequencies to LTL
Bartosz Bednarczyk, Jakub Michaliszyn
Linear Temporal Logic (LTL) interpreted on finite traces is a robust specification framework popular in formal verification. However, despite the high interest in the logic in rece…