Johannes Hostert: Bachelor's Thesis

Saarland University Computer Science

The Undecidability of First-order Logic over Small Signatures

Advisors: Andrej Dudenhefner and Dominik Kirst

Downloads

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