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