13 citations · 17 across the 16 of their papers we have counts for
22 papers
Two Variables and Two-Dimensional Structures
Bartosz Jan Bednarczyk, Daumantas Kojelis, Krzysztof Szymański
We study the two-variable fragment FO^2 of first-order logic over two-dimensional structures. Formulae may employ two linear orders <=_1, <=_2, their successor relations S_1, S_2,…
Binary Codes Correcting Multiple Edits via Polynomial Hashing and Entropy Recycling
Quan D. Bui, Shuche Wang, Van Khu Vu
Codes in the Levenshtein metric that can correct multiple edits (including deletions, insertions, and substitutions) have attracted a lot of attention recently owing to their appli…
A Horn extension of DL-Lite with NL data complexity
Janos Arpasi, Bartosz Jan Bednarczyk, Magdalena Ortiz
The literature on ontology-mediated query answering (OMQA) has been shaped by two key results: first-order rewritability for DL-Lite, and PTime-hardness of data complexity for esse…
Guarded Fragments Meet Dynamic Logic: The Story of Regular Guards (Extended Version)
Bartosz Bednarczyk, Emanuel Kieroński
We study the Guarded Fragment with Regular Guards (RGF), which combines the expressive power of the Guarded Fragment (GF) with Propositional Dynamic Logic with Intersection and Con…
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…
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-…