Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCoherent confluence modulo relations and double groupoids
129
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A coherent presentation of an n-category is a presentation by generators, relations and relations among relations. Completions of presentations by rewriting systems give coherent presentations, whose relations among relations are generated by confluence diagrams induced by critical branchings. This article extends this construction to presentations by polygraphs defined modulo a set of relations. Our coherence results are formulated using the structure of n-category enriched in double groupoids, whose horizontal cells represent rewriting sequences, vertical cells represent the congruence generated by relations modulo and square cells represent coherence cells induced by confluence modulo. We illustrate these constructions for rewriting modulo commutation relations in monoids and isotopy relations in pivotal monoidal categories.
rate research
Read More
Convergent rewriting systems on algebraic structures give methods to solve decision problems, to prove coherence results, and to compute homological invariants. These methods are based on higher-dimensional extensions of the critical branching lemma that characterizes local confluence from confluence of the critical branchings. The analysis of local confluence of rewriting systems on algebraic structures, such as groups or linear algebras, is complicated because of the underlying algebraic axioms, and in some situations, local confluence properties require additional termination conditions. This article introduces the structure of algebraic polygraph modulo that formalizes the interaction between the rules of an algebraic rewriting system and the inherent algebraic axioms, and we show a critical branching lemma for algebraic polygraphs. We deduce from this result a critical branching lemma for rewriting systems on algebraic objects whose axioms are specified by convergent modulo rewriting systems. We illustrate our constructions for string, linear, and group rewriting systems.
We study internal structures in regular categories using monoidal methods. Groupoids in a regular Goursat category can equivalently be described as special dagger Frobenius monoids in its monoidal category of relations. Similarly, connectors can equivalently be described as Frobenius structures with a ternary multiplication. We study such ternary Frobenius structures and the relationship to binary ones, generalising that between connectors and groupoids.
Confluence denotes the property of a state transition system that states can be rewritten in more than one way yielding the same result. Although it is a desirable property, confluence is often too strict in practical applications because it also considers states that can never be reached in practice. Additionally, sometimes states that have the same semantics in the practical context are considered as different states due to different syntactic representations. By introducing suitable invariants and equivalence relations on the states, programs may have the property to be confluent modulo the equivalence relation w.r.t. the invariant which often is desirable in practice. In this paper, a sufficient and necessary criterion for confluence modulo equivalence w.r.t. an invariant for Constraint Handling Rules (CHR) is presented. It is the first approach that covers invariant-based confluence modulo equivalence for the de facto standard semantics of CHR. There is a trade-off between practical applicability and the simplicity of proving a confluence property. Therefore, a better manageable subset of equivalence relations has been identified that allows for the proposed confluence criterion and and simplifies the confluence proofs by using well established CHR analysis methods.
Bergman has given the following abstract characterisation of the inner automorphisms of a group $G$: they are exactly those automorphisms of $G$ which can be extended functorially along any homomorphism $G rightarrow H$ to an automorphism of $H$. This leads naturally to a definition of inner automorphism applicable to the objects of any category. Bergman and Hofstra--Parker--Scott have computed these inner automorphisms for various structures including $k$-algebras, monoids, lattices, unital rings, and quandles---showing that, in each case, they are given by an obvious notion of conjugation. In this note, we compute the inner automorphisms of groupoids, showing that they are exactly the automorphisms induced by conjugation by a bisection. The twist is that this result is false in the category of groupoids and homomorphisms; to make it true, we must instead work with the less familiar category of groupoids and comorphisms in the sense of Higgins and Mackenzie. Besides our main result, we also discuss generalisations to topological and Lie groupoids, to categories and to partial automorphisms, and examine the link with the theory of inverse semigroups.
In this paper, we introduce the notion of a topological groupoid extension and relate it to the already existing notion of a gerbe over a topological stack. We further study the properties of a gerbe over a Serre, Hurewicz stack.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
