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.
@article{ITA_2004__38_1_19_0, author = {Brandt, Ulrike and Delepine, Ghislain and Walter, Hermann K.-G.}, title = {Weightreducing grammars and ultralinear languages}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, volume = {38}, year = {2004}, pages = {19-25}, doi = {10.1051/ita:2004001}, mrnumber = {2059026}, zbl = {1084.68058}, language = {en}, url = {http://dml.mathdoc.fr/item/ITA_2004__38_1_19_0} }
Brandt, Ulrike; Delepine, Ghislain; Walter, Hermann K.-G. Weightreducing grammars and ultralinear languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 38 (2004) pp. 19-25. doi : 10.1051/ita:2004001. http://gdmltest.u-ga.fr/item/ITA_2004__38_1_19_0/
[1] An Analoge of a Theorem about Contextfree Languages. Inform. Control 11 (1968). | Zbl 0184.02601
,[2] Finite-Turn Pushdown Automata. J. SIAM Control 4 (1966). | MR 204294 | Zbl 0147.25302
and ,[3] Derivation - bounded languages. J. Comput. Syst. Sci. 2 (1968). | Zbl 0176.16703
and ,[4] A Few Remarks on the Index of Contextfree Grammars and Languages. Inform. Control 19 (1971) | MR 311153 | Zbl 0241.68036
,[5] Introduction to Formal Language Theory. Addison-Wesley Pub. Co. (1978). | MR 526397 | Zbl 0411.68058
,[6] Formal Languages. Academic Press, New York (1973). | MR 438755 | Zbl 0262.68025
,