Quasi-deterministic 0L systems | SpringerLink
Skip to main content

Quasi-deterministic 0L systems

  • Conference paper
  • First Online:
Automata, Languages and Programming (ICALP 1992)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 623))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Jürgen Dassow: Eine neue Funktion für Lindenmayer-Systeme, Elektronische Informationsverarbeitung und Kybernetik 12, 515–521 (1976)

    Google Scholar 

  2. A. Ehrenfeucht and G. Rozenberg: Simplifications of Homornorphisms, Information and Control 38, 298–309 (1978)

    Google Scholar 

  3. G. T. Herman and G. Rozenberg: Developmental systems and languages, North Holland (1975)

    Google Scholar 

  4. Aristid Lindenmayer: Developmental systems without cellular interactions, their languages and grammars, Journal of Theoretical Biology 30, 455–484 (1971)

    PubMed  Google Scholar 

  5. A. Lindenmayer and G. Rozenberg (eds): Automata, Languages, Development, North Holland (1976)

    Google Scholar 

  6. T. Nishida: Quasi-deterministic 0L systems, SCCS Technical Report 92-1-01, Chukyo University (1992)

    Google Scholar 

  7. T. Nishida and Y. Kobuchi: Repeatable words for substitution, Theoretical Computer Science 53, 319–333 (1987)

    Article  Google Scholar 

  8. G. Rozenberg and A. Salomaa (eds): L systems, Lecture Notes in Computer Science 15, Springer Verlag (1974)

    Google Scholar 

  9. G. Rozenberg and A. Salomaa: The mathematical theory of L systems, Academic Press (1980)

    Google Scholar 

  10. G. Rozenberg and A. Salomaa (eds): The book of L, Springer Verlag (1986)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

W. Kuich

Rights and permissions

Reprints 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

Publish with us

Policies and ethics