Back to Search Start Over

Generalized Post Embedding Problems

Authors :
Karandikar, Prateek
Schnoebelen, Philippe
Source :
Theory of Computing Systems, 56(4):697-716, 2015
Publication Year :
2011

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.

Subjects

Subjects :
Computer Science - Logic in Computer Science
Computer Science - Formal Languages and Automata Theory

Details

Database :
arXiv
Journal :
Theory of Computing Systems, 56(4):697-716, 2015
Publication Type :
Report
Accession number :
edsarx.1109.1691
Document Type :
Working Paper
Full Text :
https://doi.org/10.1007/s00224-014-9561-9
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details