Disjunctive-binding first-order logic decidability conjecture

Let dbdb denote the disjunctive-binding fragment of first-order logic, whose binding-form grammar permits disjunctions but not conjunctions. Its satisfiability problem asks whether a sentence has a model.

Disjunctive-binding decidability conjecture. The fragment dbdb enjoys a decidable satisfiability problem.

The source proves that this fragment does not have the finite-model property, but conjectures that satisfiability is nevertheless decidable. The motivation given is that standard undecidability proofs appear to require both conjunctions and disjunctions of binding forms; no resolution is supplied.

Sources & referencesView supporting material

Primary source

Fabio Mogavero and Giuseppe Perelli, “On the Remarkable Features of Binding Forms”, arXiv:1404.1531 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.