Abstract
A new variation of 0L systems, called quasi-deterministic 0L systems, is defined. A quasi-deterministic 0L system is a 0L system which generates a bounded set of words at every step, where “bounded” means that the cardinality of the set is always less than a given constant. The family of languages generated by quasi-deterministic 0L systems is properly included by the family of 0L languages and properly includes that of D0L languages. A 0L system is effectively determined whether it is quasi-deterministic or not.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Jürgen Dassow: Eine neue Funktion für Lindenmayer-Systeme, Elektronische Informationsverarbeitung und Kybernetik 12, 515–521 (1976)
A. Ehrenfeucht and G. Rozenberg: Simplifications of Homornorphisms, Information and Control 38, 298–309 (1978)
G. T. Herman and G. Rozenberg: Developmental systems and languages, North Holland (1975)
Aristid Lindenmayer: Developmental systems without cellular interactions, their languages and grammars, Journal of Theoretical Biology 30, 455–484 (1971)
A. Lindenmayer and G. Rozenberg (eds): Automata, Languages, Development, North Holland (1976)
T. Nishida: Quasi-deterministic 0L systems, SCCS Technical Report 92-1-01, Chukyo University (1992)
T. Nishida and Y. Kobuchi: Repeatable words for substitution, Theoretical Computer Science 53, 319–333 (1987)
G. Rozenberg and A. Salomaa (eds): L systems, Lecture Notes in Computer Science 15, Springer Verlag (1974)
G. Rozenberg and A. Salomaa: The mathematical theory of L systems, Academic Press (1980)
G. Rozenberg and A. Salomaa (eds): The book of L, Springer Verlag (1986)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Nishida, T.Y. (1992). Quasi-deterministic 0L systems. In: Kuich, W. (eds) Automata, Languages and Programming. ICALP 1992. Lecture Notes in Computer Science, vol 623. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55719-9_64
Download citation
DOI: https://doi.org/10.1007/3-540-55719-9_64
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55719-7
Online ISBN: 978-3-540-47278-0
eBook Packages: Springer Book Archive