We gratefully acknowledge support from
the Simons Foundation and member institutions.
Full-text links:

Download:

Current browse context:

cs.FL

Change to browse by:

References & Citations

DBLP - CS Bibliography

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo

Computer Science > Formal Languages and Automata Theory

Title: Context-Free Languages of String Diagrams

Abstract: We introduce context-free languages of morphisms in monoidal categories, extending recent work on the categorification of context-free languages, and regular languages of string diagrams. Context-free languages of string diagrams include classical context-free languages of words, trees, and hypergraphs, when instantiated over appropriate monoidal categories. Using a contour-splicing adjunction, we prove a representation theorem for context-free languages of string diagrams: every such language arises as the image under a monoidal functor of a regular language of string diagrams.
Subjects: Formal Languages and Automata Theory (cs.FL); Category Theory (math.CT)
Cite as: arXiv:2404.10653 [cs.FL]
  (or arXiv:2404.10653v1 [cs.FL] for this version)

Submission history

From: Matthew Earnshaw [view email]
[v1] Tue, 16 Apr 2024 15:30:20 GMT (305kb,D)

Link back to: arXiv, form interface, contact.