Transformation of DPO Grammars into Hypergraph Lambek Grammars with the Conjunctive Kleene Star

EasyChair Preprint 8614

Abstract

We 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

@booklet{EasyChair:8614,
  author    = {Tikhon Pshenitsyn},
  title     = {Transformation of DPO Grammars into Hypergraph Lambek Grammars with the Conjunctive Kleene Star},
  howpublished = {EasyChair Preprint 8614},
  year      = {EasyChair, 2022}}