Abstract
This note shows that it is undecidable whether or not an arbitrary context-free grammar is (0,l)-total, i.e., whether or not {0, 1}+ ⊆ g(Szl(G)) holds for an arbitrary context-free grammar G, the left Szilard language Szl(G) of G, and a homomorphism g mapping the labels of G's productions into {0, 1} ∪ {λ}. These considerations are motivated by cryptosystems recently proposed by Andrasiu et al.
Get full access to this article
View all access options for this article.