Reproduce “Answering Conjunctive Queries over Linear Existential Rules with Transitivity” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Cristina Feier, Tomasz Gogacz, Filip Murlak
The paper sketches a reduction from lossy counter-machine reachability to conjunctive-query entailment under linear existential rules with transitivity. Its encoding represents configurations with paths and uses parity labels to track values during backward query rewriting. The draft claims Ackermann-hardness, but leaves proof issues unresolved; its binary-signature claim appears to conflict with decidability results for linear rules with conjunctive heads.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.