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.
Mots-clés : Chomsky-grammars, weightfunctions, weightreducing grammars, emptiness problem, 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}, pages = {19--25}, publisher = {EDP-Sciences}, volume = {38}, number = {1}, year = {2004}, doi = {10.1051/ita:2004001}, mrnumber = {2059026}, zbl = {1084.68058}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita:2004001/} }
TY - JOUR AU - Brandt, Ulrike AU - Delepine, Ghislain AU - Walter, Hermann K.-G. TI - Weightreducing grammars and ultralinear languages JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2004 SP - 19 EP - 25 VL - 38 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita:2004001/ DO - 10.1051/ita:2004001 LA - en ID - ITA_2004__38_1_19_0 ER -
%0 Journal Article %A Brandt, Ulrike %A Delepine, Ghislain %A Walter, Hermann K.-G. %T Weightreducing grammars and ultralinear languages %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2004 %P 19-25 %V 38 %N 1 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita:2004001/ %R 10.1051/ita:2004001 %G en %F 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) no. 1, pp. 19-25. doi : 10.1051/ita:2004001. http://archive.numdam.org/articles/10.1051/ita:2004001/
[1] An Analoge of a Theorem about Contextfree Languages. Inform. Control 11 (1968). | Zbl
,[2] Finite-Turn Pushdown Automata. J. SIAM Control 4 (1966). | MR | Zbl
and ,[3] Derivation - bounded languages. J. Comput. Syst. Sci. 2 (1968). | Zbl
and ,[4] A Few Remarks on the Index of Contextfree Grammars and Languages. Inform. Control 19 (1971) | MR | Zbl
,[5] Introduction to Formal Language Theory. Addison-Wesley Pub. Co. (1978). | MR | Zbl
,[6] Formal Languages. Academic Press, New York (1973). | MR | Zbl
,Cité par Sources :