Theories of HNN-Extensions and Amalgamated Products.

It is shown that the existential theory of ${\mathbb G}$ with rational constraints, over an HNN-extension ${\mathbb G}=\langle {\mathbb H},t; t^{-1}at=\varphi(a) (a \in A) \rangle$ is decidable, provided that the same problem is decidable in the base group ${\mathbb H}$ and that A is a finite group. The positive theory of ${\mathbb G}$ is decidable, provided that the existential positive theory of ${\mathbb G}$ is decidable and that A and ϕ(A) are proper subgroups of the base group ${\mathbb H}$ with A ∩ϕ(A) finite. Analogous results are also shown for amalgamated products. As a corollary, the positive theory and the existential theory with rational constraints of any finitely generated virtually-free group is decidable. [ABSTRACT FROM AUTHOR]