Expressive Power of Hypergraph Lambek Grammars

2023/11/04 by Pshenitsyn, Tikhon
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.2311.02416

Abstract

Hypergraph Lambek grammars (HL-grammars) is a novel logical approach to generating graph languages based on the hypergraph Lambek calculus. In this paper, we establish a precise relation between HL-grammars and hypergraph grammars based on the double pushout (DPO) approach: we prove that HL-grammars generate the same class of languages as DPO grammars with the linear restriction on lengths of derivations. This can be viewed as a complete description of the expressive power of HL-grammars and also as an analogue of the Pentus theorem, which states that Lambek grammars generate the same class of languages as context-free grammars. As a corollary, we prove that HL-grammars subsume contextual hyperedge replacement grammars.

Related

• Hypergraph Lambek Calculus
• Introduction to a Hypergraph Logic Unifying Different Variants of the Lambek Calculus
• First-Order Intuitionistic Linear Logic and Hypergraph Languages
• The Logic for a Mildly Context-Sensitive Fragment of the Lambek-Grishin Calculus
• Parallel Hyperedge Replacement Grammars