4 citations · 4 across the 2 of their papers we have counts for
3 papers
cs.DB2026
A Fine-Grained Dichotomy for Bounded-Variable Query Evaluation: The Calculus of Relations, a Boolean Modal Logic, and One-Variable Counting Logic
Yoshiki Nakamura, Yuya Uezato
We study the fine-grained complexity of evaluating Boolean bounded-variable first-order queries over sparse relational structures. For every fixed , every relational signa…
cs.LO2023
On the Finite Variable-Occurrence Fragment of the Calculus of Relations with Bounded Dot-Dagger Alternation
Yoshiki Nakamura
We introduce the -variable-occurrence fragment, which is the set of terms having at most occurrences of variables. We give a sufficient condition for the decidability of the…
cs.LO2023★ 4 cited
Existential Calculi of Relations with Transitive Closure: Complexity and Edge Saturations
Yoshiki Nakamura
We study the decidability and complexity of equational theories of the existential calculus of relations with transitive closure (ECoR*) and its fragments, where ECoR* is the posit…