Weightreducing grammars and ultralinear languages
University of Technology, Darmstadt Department of Computer Science, Germany; firstname.lastname@example.org.,
Accepted: 7 November 2003
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.
Mathematics Subject Classification: 68Q45
Key words: Chomsky-grammars / weightfunctions / weightreducing grammars / emptiness problem / ultralinear languages.
© EDP Sciences, 2004