Representation of polynomials by multimodal categorial dependency grammars

Abstract

Categorial dependency grammars are generalization of classical categorical grammars. Unlike context-free grammars, they describe the sentence structure not by using constituents, but by using syntactic dependencies between words. These grammars are very expressive, they allow to generate many non-context-free languages. The expressive power of one of the variants of these grammars is studied in this paper – multimodal categorical dependency grammars. It was established earlier that they can generate non-semilinear languages. The possibility of representation of polynomials by such grammars is studied in this paper. It is proved that for every polynomial there exists a grammar generating the set of all positive values of this polynomial encoded in unary system. The set of absolute values of all non-zero values of an arbitrary polynomial can be represented in an analogous way. It is established that it is possible to construct grammars performing calculation of the value of a polynomial by a given argument, and calculation of the argument by a given value of a polynomial.