Imaginary groups: lazy monoids and reversible computation. (October 2013)

• Record Type: Journal Article
• Authors: GABBAY, MURDOCH J.; KROPHOLLER, PETER H.
• Is Part Of: Mathematical structures in computer science. Volume 23:Number 5(2013)
• Page Start: 1002
• Page End: 1031
• Publication Date: 2013-10
• Subjects: Computer science -- Mathematics -- Periodicals; 004.015105
• DOI: 10.1017/S0960129512000849
• Languages: English
• ISSNs: 0960-1295

Abstract

<abstract abstract-type="normal"> <title> <x content-type="archive" xml:space="preserve">Abstract</x> </title> <p>We use constructions in monoid and group theory to exhibit an adjunction between the category of partially ordered monoids and <italic>lazy</italic> monoid homomorphisms and the category of partially ordered groups and group homomorphisms such that the unit of the adjunction is injective. We also prove a similar result for sets acted on by monoids and groups.</p> <p>We introduce the new notion of a <italic>lazy homomorphism</italic> for a function <italic>f</italic> between partially ordered monoids such that <italic>f(m ○ m′)</italic> ≤ <italic>f(m) ○ f(m′)</italic>.</p> <p>Every monoid can be endowed with the discrete partial ordering (<italic>m ≤ m′</italic> if and only if <italic>m=m′)</italic>, so our constructions provide a way of embedding monoids into groups. A simple counterexample (the two-element monoid with a non-trivial idempotent) and some calculations show that one can never hope for such an embedding to be a monoid homomorphism, so the price paid for injecting a monoid into a group is that we must weaken the notion of a homomorphism to this new notion of a lazy homomorphism.</p> <p>The computational significance of this is that a monoid is an abstract model of computation – or at least of 'operations' – and, similarly, a group models <italic>reversible</italic> computations/operations. With this reading, the adjunction with its injective unit gives a systematic high-level way of faithfully translating an irreversible system into a 'lazy' reversible one.</p> <p>Informally, but perhaps informatively, we can describe this work as follows: we give an abstract analysis of how we can sensibly add 'undo' (in the sense of 'control-Z').</p> </abstract>