Lattice Generators (LG)

Input

A lattice $L$, a set of equations $E$ and $e, g_1, \ldots, g_n$ terms over $\mathcal{U}$.

Problem

Does $E \models \text{gen}(e, g_1, \ldots, g_n)$?

Definitions

See UWPL for base definitions of lattices. Let $\mu : \mathcal{U} \to L$ be a valuation, and $X \subseteq L$. The sublattice generated by $X$ is the smallest subset of $L$ that contains $X$ and is closed under the operations of $L$. $e$ is generated by $g_1, \ldots, g_n$ in $L$ under $\mu$, denoted $L \models_\mu \text{gen}(e, g_1, \ldots, g_n)$, if and only if $\mu(e)$ is in the sublattice of $L$ generated by the set $\{\mu(g_i) \mid i = 1, \ldots, n\}$. $E$ implies that $e$ is generated by $g_1, \ldots, g_n$, denoted $E \models \text{gen}(e, g_1, \ldots, g_n)$, if and only if for every lattice $L$ and valuation $\mu$ such that $L \models_\mu E$, it follows that $L \models_\mu \text{gen}(e, g_1, \ldots, g_n)$.

Status

$\P$-complete (Cosmadakis [1]).

Remarks

A polynomial time algorithm for the problem is given in [1]. The reduction is a continuation of the reduction used in UWPL.

The problem remains $\P$-complete when $E = \varnothing$ and the terms are represented by directed acyclic graphs instead of trees. However, if $E = \varnothing$ and the terms are represented as trees the problem is in $\mathsf{DLOG}$ [1]. This problem is called the Generator Problem for Free Lattices.