The Regular Post Embedding Problem
Philippe Schnoebelen
Info
|
Date |
9th May 2012 (week 3, Trinity Term 2012) |
|
Time |
11:30 |
|
Place |
147 |
Abstract
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
Further info
|
Related series |
|
