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
|
| [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.
|