Notes on Fragments of First-Order Concatenation Theory

Abstract

We identify a number of decidable and undecidable fragments of first-order concatenation theory. We also give a purely universal axiomatization which is complete for the fragments we identify. Furthermore, we prove some normal-form results.

References in corpus (1)

• The Satisfiability of Extended Word Equations: The Boundary Between Decidability and Undecidability