BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260920T141623Z
UID:Seminar-dept-284@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20120501T160000
DTEND:20120501T170000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Philippe Schnoebelen: The Regular Post Embedding Problem, with applications to lossy channel systems\n\nThe 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).\n\n\n\nPEP 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.\n\n\n\nThe talk will survey the still relatively few known results on PEP and its variants. \n\nRelated papers are available at /tinyurl.com/7r8sd6d.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=284
LOCATION:G12
END:VEVENT
END:VCALENDAR