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.
Let I be a finite set of words and be the derivation relation generated by the set of productions {ε → u | u ∈ I}. Let be the set of words u such that . We prove that the set I is unavoidable if and only if the relation is a well quasi-order on the set . This result generalizes a theorem of [Ehrenfeucht et al.,Theor. Comput. Sci.27 (1983) 311–332]. Further generalizations are investigated.
In this note we prove that the language of a numeration system is the language of a -shift under some assumptions on the basis. We deduce from this result a partial answer to the question when the language of a numeration system is regular. Moreover, we give a characterization of the arithmetico-geometric sequences and the mixed radix sequences that are basis of a numeration system for which the language is regular. Finally, we study the Ostrowski systems of numeration and give another proof of...