Displaying similar documents to “Hotz-isomorphism theorems in formal language theory”

Indexed counter languages

J. Duske, M. Middendorf, R. Parchmann (1992)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Weightreducing grammars and ultralinear languages

Ulrike Brandt, Ghislain Delepine, Hermann K.-G. Walter (2004)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We exhibit a new class of grammars with the help of weightfunctions. They are characterized by decreasing the weight during the derivation process. A decision algorithm for the emptiness problem is developed. This class contains non-contextfree grammars. The corresponding language class is identical to the class of ultralinear languages.