{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T12:26:25Z","timestamp":1747225585398},"reference-count":19,"publisher":"World Scientific Pub Co Pte Ltd","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2009,11]]},"abstract":"<jats:p>The \"if\u2013then\u2013else\" 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\u2013then\u2013else. 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 \u2014 modeling halting programs \u2014 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.<\/jats:p>","DOI":"10.1142\/s0218196709005354","type":"journal-article","created":{"date-parts":[[2009,12,16]],"date-time":"2009-12-16T06:22:12Z","timestamp":1260944532000},"page":"937-961","source":"Crossref","is-referenced-by-count":18,"title":["SEMIGROUPS WITH if\u2013then\u2013else AND HALTING PROGRAMS"],"prefix":"10.1142","volume":"19","author":[{"given":"MARCEL","family":"JACKSON","sequence":"first","affiliation":[{"name":"Department of Mathematics, La Trobe University, Melbourne, Victoria 3086, Australia"}]},{"given":"TIM","family":"STOKES","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Waikato, Hamilton, New Zealand"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01190851"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1137\/0212047"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1017\/S000497270000959X"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1145\/360933.360975"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1137\/0216025"},{"key":"rf6","first-page":"576","volume":"12","author":"Hoare C. A. R.","journal-title":"Comm. Assoc. Comput. Mach."},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-8693(03)00314-4"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196706003426"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1006\/jabr.1999.7939"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1145\/343369.343378"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.069"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01190447"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)72018-4"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1137\/0216033"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1137\/0220049"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573019"},{"key":"rf20","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1090\/trans2\/113\/06","volume":"113","author":"Schein B. M.","journal-title":"Amer. Math. Soc. Translat. Ser. 2"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1007\/s000120050065"},{"key":"rf22","first-page":"481","volume":"72","author":"Stokes T.","journal-title":"Acta Sci. Math. (Szeged)"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196709005354","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,24]],"date-time":"2020-05-24T04:31:06Z","timestamp":1590294666000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196709005354"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,11]]},"references-count":19,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2009,11]]}},"alternative-id":["10.1142\/S0218196709005354"],"URL":"https:\/\/doi.org\/10.1142\/s0218196709005354","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"type":"print","value":"0218-1967"},{"type":"electronic","value":"1793-6500"}],"subject":[],"published":{"date-parts":[[2009,11]]}}}