Grammars over the Lambek Calculus with Permutation: Recognizing Power and Connection to Branching Vector Addition Systems with States

DOI10.1007/S10849-023-09407-ZarXiv2209.08415MaRDI QIDQ6411091FDOQ6411091

Publication date: 17 September 2022

Abstract: In (Van Benthem, 1991) it is proved that all permutation closures of context-free languages can be generated by grammars over the Lambek calculus with the permutation rule (LP-grammars); however, to our best knowledge, it is not established whether the converse holds or not. In this paper, we show that LP-grammars are equivalent to linearly-restricted branching vector addition systems with states and with additional memory (shortly, lBVASSAM), which are modified branching vector addition systems with states. Then an example of such an lBVASSAM is presented, which generates a non-semilinear set of vectors; this yields that LP-grammars generate more than permutation closures of context-free languages. Moreover, equivalence of LP-grammars and lBVASSAM allows us to present a normal form for LP-grammars and, as a consequence, prove that LP-grammars are equivalent to LP-grammars without product. Finally, we prove that the class of languages generated by LP-grammars is closed under intersection.

This page was built for publication: Grammars over the Lambek Calculus with Permutation: Recognizing Power and Connection to Branching Vector Addition Systems with States

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6411091)