Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems

摘要

We introduce PEP, the Post Embedding Problem, a variant of PCP where one compares strings with the subword relation, and PEP~(reg), a further variant where solutions are constrained and must belong to a given regular language. PEP~(reg) is decidable but not primitive recursive. This entails the decidability of reachability for unidirectional systems with one reliable and one lossy channel.