Abstract
A DTOL system is unambiguous if no two different sequences of morphisms yield the same word from an axiom. A subfamily of DTOL systems with decidable ambiguity problem is exhibited. Four different sufficient conditions for a DTOL system to be unambiguous are formulated. These DTOL systems are very much suitable for the construction of public key cryptosystems based on L systems. We also prove that for DOL systems over a binary alphabet, the ambiguity problem is effectively decidable. This result has useful applications in the construction of public key cryptosystems which encrypt plain-texts over a binary alphabet using a TOL system obtained from an underlying unambiguous DOL system.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Berstel and D. Perrin (1985), ‘Theory of Codes', Academic Press, New York.
J. Dassow (1984), A note on DTOL systems, Bull. EATCS, 22, 11–14.
Do Long Van (1982), Codes avec des mots infinis, RAIRO informatique Theorique 16, 371–386.
Do Long Van (1985), Ensembles code-compatibles et une generalisation du theoreme de Sardinas-Patterson, Theo. Comp. Sci. 38,123–132.
S. Ginsburg (1986), ‘The Mathematical Theory of Context-free languages', McGraw Hill, New York.
A.Reedy and W.J.Savitch (1974), Ambiguity in developmental systems, Proc. of the 1974 Conf. on Biologically Motivated Automata Theory, 97–105.
G. Rozenberg and A. Salomaa (1980), ‘The Mathematical Theory of L systems', Academic Press, New York.
A. Salomaa (1973), ‘Formal Languages', Academic Press, New York.
A. Salomaa (1985), ‘Computation and Automata', Encyclopaedia of Mathematics and its Applications, 25, Cambridge University Press, New York.
K.G.Subramanian, R.Siromoney and Abisha Jeyanthi (1987), A DOL-TOL public-key cryptosystem, To appear in Inform. Proc. Lett.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Subramanian, K.G., Van Long, D., Siromoney, R. (1987). On ambiguity of DTOL systems. In: Nori, K.V. (eds) Foundations of Software Technology and Theoretical Computer Science. FSTTCS 1987. Lecture Notes in Computer Science, vol 287. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-18625-5_38
Download citation
DOI: https://doi.org/10.1007/3-540-18625-5_38
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-18625-0
Online ISBN: 978-3-540-48033-4
eBook Packages: Springer Book Archive