1
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Expressive Power of Hypergraph Lambek Grammars

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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 collections

          Author and article information

          Journal
          04 November 2023
          Article
          2311.02416
          74ba141b-61c8-4a41-9c11-272e5e42b620

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          cs.FL

          Theoretical computer science
          Theoretical computer science

          Comments

          Comment on this article