Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup (Q1921846)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup |
scientific article |
Statements
Undecidability of the positive \(\forall\exists^ 3\)-theory of a free semigroup (English)
0 references
8 January 1997
0 references
Let \(\Pi_n\) denote a free semigroup of rank \(n\) with free generators \(a_1,\dots,a_n\). The main result is Theorem 1. For \(n\geq 2\) the positive \(\forall\exists^3\)-theory of \(\Pi_n\) is algorithmically undecidable.
0 references
free semigroups
0 references
free generators
0 references
positive \(\forall\exists^ 3\)-theory
0 references
algorithmically undecidable theories
0 references
