(0,1)-TOTALITY IS UNDECIDABLE FOR ARBITRARY CONTEXT-FREE GRAMMARS

Article type: Research Article

Authors: Mäkinen, Erkki

Affiliations: University of Tampere, Department of Computer Science, P.O. Box 607, FIN-33101 Tampere, Finland E-mail: [email protected]

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.

Keywords: cryptosystems, Szilard languages, (0,l)-totality

DOI: 10.3233/FI-1996-27404

Journal: Fundamenta Informaticae, vol. 27, no. 4, pp. 413-415, 1996