Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 2083

Preprint Number 2083

Previous Next Preprint server

2083. Juvenal Murwanashyaka
Undecidability in First-Order Theories of Term Algebras Extended with a Substitution Operator

Submission date: 31 October 2021


We introduce a first-order theory of finite full binary trees and then identify decidable and undecidable fragments of this theory. We show that the analogue of Hilbert`s 10th Problem is undecidable by constructing a many-to-one reduction of Post`s Correspondence Problem. By a different method, we show that deciding truth of sentences with one existential quantifier and one bounded universal quantifier is undecidable.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 2111.00573: pdf, ps.

Last updated: November 3 2021 20:52 Please send your corrections to: