The Regular Post Embedding Problem

The Regular Post Embedding Problem (PEP) is a variant of Post's Correspondence Problem where instead of asking for equality between two concatenations of corresponding word sequences, one asks for embedding of one in the other, using the notion of subword, i.e., scattered subsequence. PEP is decidable but with surprisingly high complexity.

PEP was introduced in connection with verification problems on unreliable machine models like lossy channel systems and has since found new applications. It is still a very new problem: easy to learn, with many fascinating questions still open, many avenues and variants still totally unexplored.

The talk will survey the main known results on PEP and its variants and will illustrate a few proof techniques. A PEP bibliography is available at http://www.lsv.ens-cachan.fr/~phs/PEP.php