Download PDFOpen PDF in browser

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

EasyChair Preprint 8614

10 pagesDate: August 7, 2022

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

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@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}}
Download PDFOpen PDF in browser