Imaginary groups

lazy monoids and reversible computation

Murdoch J Gabbay, Peter H Kropholler

Research output: Contribution to journalArticle

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

@article{f6880e106fb5498fbabb29dd9f711664,
title = "Imaginary groups: lazy monoids and reversible computation",
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 (mInformally, 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').",
author = "Gabbay, {Murdoch J} and Kropholler, {Peter H}",
year = "2013",
month = "10",
doi = "10.1017/S0960129512000849",
language = "English",
volume = "23",
pages = "1002--1031",
journal = "Mathematical Structures in Computer Science",
issn = "0960-1295",
publisher = "Cambridge University Press",
number = "5",

}

Imaginary groups : lazy monoids and reversible computation. / Gabbay, Murdoch J; Kropholler, Peter H.

In: Mathematical Structures in Computer Science, Vol. 23, No. 5, 10.2013, p. 1002-1031.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Imaginary groups

T2 - lazy monoids and reversible computation

AU - Gabbay, Murdoch J

AU - Kropholler, Peter H

PY - 2013/10

Y1 - 2013/10

N2 - 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 (mInformally, 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').

AB - 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 (mInformally, 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').

U2 - 10.1017/S0960129512000849

DO - 10.1017/S0960129512000849

M3 - Article

VL - 23

SP - 1002

EP - 1031

JO - Mathematical Structures in Computer Science

JF - Mathematical Structures in Computer Science

SN - 0960-1295

IS - 5

ER -