Critical Pairs in Network Rewriting
2014 (English)In: IWC 2014: 3rd International Workshop on Confluence / [ed] Takahito Aoto & Delia Kesner, 2014, 9-13 p.Conference paper (Refereed)
This extended abstract breifly introduces rewriting of networks (directed acyclic graphs with the extra structure needed to serve as expressions for PROducts and Permutations categories) and describes the critical pairs aspects of this theory. The author's interest in these comes from wanting to do equational reasoning in algebraic theories (such as Hopf algebras) that mix ordinary operations with co-operations; networks then serve as a formalism for expressions.
The main message is to point out two phenomena that arise in network rewriting. The first is that of non-convexity of rules, wherein the left hand side of a rule need not be syntactically similar to a symbol in any extension of the underlying signature. The second is one of critical pairs potentially arising where two redexes wrap around each other even when they do not intersect.
Place, publisher, year, edition, pages
2014. 9-13 p.
network, PROP, critical pair, ambiguity, confluence, wrap ambiguity
Algebra and Logic Discrete Mathematics Mathematics
Research subject Mathematics/Applied Mathematics
IdentifiersURN: urn:nbn:se:mdh:diva-26109OAI: oai:DiVA.org:mdh-26109DiVA: diva2:755875
IWC 2014 (3rd International Workshop on Confluence), part of Vienna Summer of Logic 2014, Vienna, 13 July 2014