Uniform Word Problem for Finitely Presented Algebras (UWPFPA)
Input
A finitely presented algebra $A = (M, \mathcal{A}, \Gamma)$ and a pair of terms $x$ and $y$.
Problem
Is $x \equiv y$?
Definitions
Set $M$ is finite and consists of symbols and $\mathcal{A} : M \to \N$ defines the arity of each symbol. $M$ is partitioned into two sets: $G = \{a \in M \mid \mathcal{A}(a) = 0\}$ consists of generator symbols and $O = \{a \in M \mid \mathcal{A}(a) > 0\}$ consists of operator symbols. The set of terms over $M$ is the smallest subset of $M^\ast$ such that
- all elements of $G$ are terms, and
- if $\theta$ is $m$-ary and $x_1, \ldots, x_m$ are terms, then $\theta(x_1, \ldots, x_m)$ is a term.
Let $\tau$ denote the set of terms. Set $\Gamma$ consists of unordered pairs of terms called axioms. The congruence relation $\equiv$ is the smallest on $\tau$ satisfying the axioms of $\Gamma$.
Status
$\P$-complete (Kozen [1]).
Remarks
A polynomial time algorithm for the problem is given in [1]. The reduction to show hardness is from MCVP.