One Left-linear Semi-unification (1LLSU)
Category: Searching Graphs
Input
A set of pairs of terms $S = \{(M_1, N_1), \ldots, (M_k, N_k)\}$ that is left linear.
Problem
Is $S$ semi-unifiable?
Definitions
See LLSU.
Status
Open (Henglein [1]).
Remarks
2LLSU is $\P$-complete [1]; see LLSU. Henglein conjectures that 1LLSU is $\P$-complete [1].