Generalized Post Embedding Problems
classification
💻 cs.LO
cs.FL
keywords
embeddingpostdirectnessproblemscodirectnesscombiningcountingdecidable
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.