Johannes Hostert: Bachelor's Thesis

Saarland University Computer Science

The Undecidability of First-order Logic over Small Signatures

Advisors: Andrej Dudenhefner and Dominik Kirst


The project mainly consists of showing that problems first-order logic is already undecidable when the logic has just one binary relation.
For this, we provide an explicit reduction from a variant of H10, hoping to avoid signature compression steps.

Legal notice, Privacy policy