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 non-trivial 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 length-one solution). The addition of regular constraints makes the problem highly non-trivial.

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, 2014.

About LSV