Research Commons
      • Browse 
        • Communities & Collections
        • Titles
        • Authors
        • By Issue Date
        • Subjects
        • Types
        • Series
      • Help 
        • About
        • Collection Policy
        • OA Mandate Guidelines
        • Guidelines FAQ
        • Contact Us
      • My Account 
        • Sign In
        • Register
      View Item 
      •   Research Commons
      • University of Waikato Research
      • Computing and Mathematical Sciences
      • Computing and Mathematical Sciences Papers
      • View Item
      •   Research Commons
      • University of Waikato Research
      • Computing and Mathematical Sciences
      • Computing and Mathematical Sciences Papers
      • View Item
      JavaScript is disabled for your browser. Some features of this site may not work without it.

      How to generalise demonic composition

      Stokes, Tim E.
      Thumbnail
      Files
      SFDemonGeneric.pdf
      Accepted version, 286.8Kb
      DOI
       10.1007/s00233-020-10117-2.
      Link
       links.springernature.com
      Find in your library  
      Citation
      Export citation
      Stokes, T. E. (2020). How to generalise demonic composition. Semigroup Forum. https://doi.org/10.1007/s00233-020-10117-2.
      Permanent Research Commons link: https://hdl.handle.net/10289/13679
      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).
      Date
      2020
      Type
      Journal Article
      Publisher
      Springer Verlag
      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
      Collections
      • Computing and Mathematical Sciences Papers [1454]
      Show full item record  

      Usage

      Downloads, last 12 months
      77
       
       
       

      Usage Statistics

      For this itemFor all of Research Commons

      The University of Waikato - Te Whare Wānanga o WaikatoFeedback and RequestsCopyright and Legal Statement