Nonterminals and codings in defining variations of OL-systems

Research output: Contribution to book/anthology/report/proceedingBook chapterResearchpeer-review

  • Department of Computer Science
The use of nonterminals versus the use of codings in variations of OL-systems is studied. It is shown that the use of nonterminals produces a comparatively low generative capacity in deterministic systems while it produces a comparatively high generative capacity in nondeterministic systems.
Finally it is proved that the family of context-free languages is contained in the family generated by codings on propagating OL-systems with a finite set of axioms, which was one of the open problems in [10]. All the results in this paper can be found in [71] and [72].
Original languageEnglish
Title of host publicationL Systems
EditorsGrzegorz Rozenberg, Arto Salomaa
Number of pages6
PublisherSpringer
Publication year1974
Pages244-249
DOIs
Publication statusPublished - 1974
SeriesLecture Notes in Computer Science
Volume15

See relations at Aarhus University Citationformats

ID: 37175613