Nonterminals, homomorphisms and codings in different variations of OL-systems. I. Deterministic systems

TY - JOUR

T1 - Nonterminals, homomorphisms and codings in different variations of OL-systems. I. Deterministic systems

AU - Nielsen, Mogens

AU - Rozenberg, Grzegorz

AU - Salomaa, Arto

AU - Skyum, Sven

PY - 1974

Y1 - 1974

N2 - The use of nonterminals versus the use of homomorphisms of different kinds in the basic types of deterministic OL-systems is studied. A rather surprising result is that in some cases the use of nonterminals produces a comparatively low generative capacity, whereas in some other cases the use of nonterminals gives a very high generative capacity. General results are obtained concerning the use of erasing productions versus the use of erasing homomorphisms. The paper contains a systematic classification of the effect of nonterminals, codings, weak codings, nonerasing homomorphisms and homomorphisms for all basic types of deterministic OL-languages, including table languages.

AB - The use of nonterminals versus the use of homomorphisms of different kinds in the basic types of deterministic OL-systems is studied. A rather surprising result is that in some cases the use of nonterminals produces a comparatively low generative capacity, whereas in some other cases the use of nonterminals gives a very high generative capacity. General results are obtained concerning the use of erasing productions versus the use of erasing homomorphisms. The paper contains a systematic classification of the effect of nonterminals, codings, weak codings, nonerasing homomorphisms and homomorphisms for all basic types of deterministic OL-languages, including table languages.

U2 - 10.1007/BF00288938

DO - 10.1007/BF00288938

M3 - Journal article

SN - 0001-5903

VL - 4

SP - 87

EP - 106

JO - Acta Informatica

JF - Acta Informatica

IS - 1

ER -