The Regular Post Embedding Problem, with applications to lossy channel systems

1^st May 2012, 16:00 G12
Dr. Philippe Schnoebelen
LSV, CNRS & ENS
CACHAN Cedex
France
This year: visiting Oxford Univ. Comp. Sci. Dept.

Abstract

The Regular Post Embedding Problem, aka PEP, is the question, given two word morphisms u and v and a regular language R, whether there is some x in R such that u(x) embeds into (i.e., is a scattered subword of) v(x).

PEP was introduced in connection with verification problem on unreliable machine models like lossy channel systems. PEP is decidable but with surprisingly high complexity. It is a good master problem for complexity at level omega^omega in the Fast-Growing Hierarchy.

The talk will survey the still relatively few known results on PEP and its variants.
Related papers are available at /tinyurl.com/7r8sd6d.