Imaginary groups: lazy monoids and reversible computation

Murdoch J Gabbay, Peter H Kropholler

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

We use constructions in monoid and group theory to exhibit an adjunction between the category of partially ordered monoids and lazy 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. We introduce the new notion of a lazy homomorphism for a function f between partially ordered monoids such that f(m circle m')

Every monoid can be endowed with the discrete partial ordering (m

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').

Original languageEnglish
Pages (from-to)1002-1031
Number of pages30
JournalMathematical Structures in Computer Science
Volume23
Issue number5
DOIs
Publication statusPublished - Oct 2013

Cite this