Аннотация:
In 1993, Mati Pentus proved that Lambek grammars are equivalent to context-free grammars in the sense that they generate the same set of languages (disregarding the empty word). We prove that a similar result does not hold for grammars over the Lambek calculus with permutation (LP), which can also be called commutative Lambek grammars. More precisely, we show that there is a language that can be generated by a commutative Lambek grammar such that it is not a permutation closure of a context-free language. To prove this, we present a formalism equivalent to commutative Lambek grammars, which we call linearly-restricted branching vector addition systems with states; it is simpler to establish the desired result for them.
