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.

      Semigroups with if-then-else and halting programs

      Jackson, Marcel; Stokes, Tim E.
      Thumbnail
      Files
      ITEplain.pdf
      264.0Kb
      DOI
       10.1142/S0218196709005354
      Link
       www.worldscinet.com
      Find in your library  
      Citation
      Export citation
      Jackson, M. & Stokes, T. (2009). Semigroups with if-then-else and halting programs. International Journal of Algebra and Computation (IJAC), 19(7), 937-961.
      Permanent Research Commons link: https://hdl.handle.net/10289/3728
      Abstract
      The "if–then–else" construction is one of the most elementary programming commands, and its abstract laws have been widely studied, starting with McCarthy. Possibly, the most obvious extension of this is to include the operation of composition of programs, which gives a semigroup of functions (total, partial, or possibly general binary relations) that can be recombined using if–then–else. We show that this particular extension admits no finite complete axiomatization and instead focus on the case where composition of functions with predicates is also allowed (and we argue there is good reason to take this approach). In the case of total functions — modeling halting programs — we give a complete axiomatization for the theory in terms of a finite system of equations. We obtain a similar result when an operation of equality test and/or fixed point test is included.
      Date
      2009
      Type
      Journal Article
      Publisher
      World Scientific Publishing Company
      Rights
      Electronic version of an article published as International Journal of Algebra and Computation (IJAC), 19(7), 937-961, DOI:10.1142/S0218196709005354. © 2009 World Scientific Publishing Company.

      http://www.worldscinet.com/ijac/19/1907/S0218196709005354.html
      Collections
      • Computing and Mathematical Sciences Papers [1454]
      Show full item record  

      Usage

      Downloads, last 12 months
      72
       
       
       

      Usage Statistics

      For this itemFor all of Research Commons

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