Download PDFOpen PDF in browserTransformation of DPO Grammars into Hypergraph Lambek Grammars with the Conjunctive Kleene StarEasyChair Preprint 861410 pages•Date: August 7, 2022AbstractWe study how to embed well-known hypergraph grammars based on the double pushout (DPO) approach in the hypergraph Lambek calculus HL. It turns out that DPO rules can be naturally encoded by types of HL. However, this encoding is not enough to convert a DPO grammar into an equivalent grammar based on HL: we additionally need a logical operation that would allow making arbitrarily many copies of types. We develop such an operation called the conjunctive Kleene star and show that any DPO grammar can be converted into an equivalent HL-grammar enriched with this operation. Keyphrases: Double Pushout Approach, Kleene star, Lambek calculus, generative power, graph grammar
|