全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
Mathematics  2015 

!-Graphs with Trivial Overlap are Context-Free

DOI: 10.4204/EPTCS.181.2

Full-Text   Cite this paper   Add to My Lib

Abstract:

String diagrams are a powerful tool for reasoning about composite structures in symmetric monoidal categories. By representing string diagrams as graphs, equational reasoning can be done automatically by double-pushout rewriting. !-graphs give us the means of expressing and proving properties about whole families of these graphs simultaneously. While !-graphs provide elegant proofs of surprisingly powerful theorems, little is known about the formal properties of the graph languages they define. This paper takes the first step in characterising these languages by showing that an important subclass of !-graphs—those whose repeated structures only overlap trivially—can be encoded using a (context-free) vertex replacement grammar.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133