The Regular Post Embedding Problem
Post's "Embedding??" Problem
Let u,v:Σ^{*}→Γ^{*} be two morphisms. With
Post's Correspondence Problem, one asks whether u(x)=v(x)
for some nontrivial x, i.e., for x∈Σ^{+}.
Post's Embedding Problem is a variant where one asks whether u(x)≤v(x) for some x∈Σ^{+}. Here "≤"
denotes the (scattered) subword relation, aka "embedding". For
example, abba ≤ abracadabra.

The Regular Post Embedding Problem
The Regular Post Embedding Problem asks whether
u(x)≤v(x) for some x∈R, where R⊆Σ^{+} is a given
regular language.
Without the regular constraint, Post's Embedding Problem
is trivial (if there is a solution x∈Σ^{+} then, in
particular, there is a lengthone solution).
The addition of regular constraints makes the problem highly nontrivial.

References (in chronological order)

[1]
P. Chambart and Ph. Schnoebelen.
Post Embedding Problem is not Primitive Recursive, with Applications to Channel Systems.
In
Proc. FSTTCS 2007, LNCS 4855, pages 265–276. Springer, 2007.
[2]
P. Chambart and Ph. Schnoebelen.
The ωRegular Post Embedding Problem.
In
Proc. FoSSaCS 2008, LNCS 4962, pages 97–111. Springer, 2008.
[3]
P. Chambart and Ph. Schnoebelen.
Pumping and Counting on the Regular Post Embedding Problem.
In
Proc. ICALP 2010, LNCS 6199, pages 64–75. Springer, 2010.
[4]
P. Chambart and Ph. Schnoebelen.
Computing Blocker Sets for the Regular Post Embedding Problem.
In
Proc. DLT 2010, LNCS 6224, pages 136–147. Springer, 2010.
[5]
P. Karandikar and Ph. Schnoebelen.
Cutting Through Regular Post Embedding Problems.
In
Proc. CSR 2012, LNCS 7353, pages 229–240. Springer,
2012.
[6]
P. Barceló, D. Figueira, and L. Libkin.
Graph logics with rational relations and the generalized intersection
problem.
In
Proc. LICS 2012, pages 115–124. IEEE Comp. Soc. Press,
2012.
[7]
P. Karandikar and Ph. Schnoebelen.
Generalized Post Embedding Problems.
In
Theory of Computing Systems. Springer,
2015.