Computing Critical Pairs in 2-Dimensional Rewriting Systems

Details Computing Critical Pairs in 2-Dimensional Rewriting Systems Computing Critical Pairs in 2-Dimensional Rewriting Systems

2010-04-19

arxiv.org/abs/1004.3135v1

Computer Science

Formal Languages and Automata Theory

Scientific paper

Rewriting systems on words are very useful in the study of monoids. In good cases, they give finite presentations of the monoids, allowing their manipulation by a computer. Even better, when the presentation is confluent and terminating, they provide one with a notion of canonical representative for the elements of the presented monoid. Polygraphs are a higher-dimensional generalization of this notion of presentation, from the setting of monoids to the much more general setting of n-categories. Here, we are interested in proving confluence for polygraphs presenting 2-categories, which can be seen as a generalization of term rewriting systems. For this purpose, we propose an adaptation of the usual algorithm for computing critical pairs. Interestingly, this framework is much richer than term rewriting systems and requires the elaboration of a new theoretical framework for representing critical pairs, based on contexts in compact 2-categories.

Affiliated with

Also associated with

No associations

Rating

Computing Critical Pairs in 2-Dimensional Rewriting Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing Critical Pairs in 2-Dimensional Rewriting Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing Critical Pairs in 2-Dimensional Rewriting Systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-59473