4 papers
A Decidable Bundled Fragment of First-Order Modal Logic Without Finite Model Property
Varad Joshi, Anantha Padmanabha
The satisfiability problem for First-order Modal Logic (\FOML) is undecidable even for simple fragments like having only unary predicates, two variables etc. Recently a new way to…
A Simple Algorithm for Consistent Query Answering under Primary Keys
Diego Figueira, Anantha Padmanabha, Luc Segoufin +1
We consider the dichotomy conjecture for consistent query answering under primary key constraints. It states that, for every fixed Boolean conjunctive query q, testing whether q is…
Boundedness for Unions of Conjunctive Regular Path Queries over Simple Regular Expressions
Diego Figueira, S. Krishna, Om Swostik Mishra +1
The problem of checking whether a recursive query can be rewritten as query without recursion is a fundamental reasoning task, known as the boundedness problem. Here we study the b…
A Dichotomy in the Complexity of Consistent Query Answering for Two Atom Queries With Self-Join
Anantha Padmanabha, Luc Segoufin, Cristina Sirangelo
We consider the dichotomy conjecture for consistent query answering under primary key constraints. It states that, for every fixed Boolean conjunctive query q, testing whether q is…