Loading...
Abstract
Demonic composition is defined on the set of binary relations over the non-empty set X, π
πππ, and is a variant of standard or βangelicβ composition. It arises naturally in the setting of the theory of non-deterministic computer programs, and shares many of the nice features of ordinary composition (it is associative, and generalises composition of functions). When equipped with the operations of demonic composition and domain, π
πππ is a left restriction semigroup (like πππ, the semigroup of partial functions on X), whereas usual composition and domain give a unary semigroup satisfying weaker laws. By viewing π
πππ under a restricted version of its usual composition and domain as a constellation (a kind of βone-sidedβ category), we show how this demonic left restriction semigroup structure arises on π
πππ, placing it in a more general context. The construction applies to any unary semigroup with a βdomain-likeβ operation satisfying certain minimal conditions which we identify. In particular it is shown that using the construction, any Baer β-semigroup S can be given a left restriction semigroup structure which is even an inverse semigroup if S is β-regular. It follows that the semigroup of πΓπ matrices over the real or complex numbers is an inverse semigroup with respect to a modified notion of product that almost always agrees with the usual matrix product, and in which inverse is pseudoinverse (MooreβPenrose inverse).
Type
Journal Article
Type of thesis
Series
Citation
Stokes, T. E. (2020). How to generalise demonic composition. Semigroup Forum. https://doi.org/10.1007/s00233-020-10117-2.
Date
2020
Publisher
Springer Verlag
Degree
Supervisors
Rights
This is a post-peer-review, pre-copyedited version of an article published in Semigroup Forum. The final authenticated version is available online at https://doi.org/10.1007/s00233-020-10117-2