Generalized Post Embedding Problems
  The Regular Post Embedding Problem extended with partial (co)directness is shown decidable. This extends to universal and/or counting versions. It is also shown that combining directness and codirectness in Post Embedding problems leads to undecidability. 
Prateek Karandikar and Philippe Schnoebelen
cs.LO cs.FL