Semigroups with if-then-else and halting programs. (English) Zbl 1203.08005

Jackson, Marcel; Stokes, Tim

Int. J. Algebra Comput. 19, No. 7, 937-961 (2009).

Authors’ 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.”

Reviewer: Valentin F. Goranko (Johannesburg)

MSC:

08A70	Applications of universal algebra in computer science
20M20	Semigroups of transformations, relations, partitions, etc.
68N30	Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)

Keywords:

transformation; semigroup; if-then-else; equality test; fixed-point test; composition of programs

References:

[1]	DOI: 10.1007/BF01190851 · Zbl 0692.18003
[2]	DOI: 10.1137/0212047 · Zbl 0518.68010
[3]	DOI: 10.1017/S000497270000959X · Zbl 0811.08006
[4]	DOI: 10.1145/360933.360975 · Zbl 0308.68017
[5]	DOI: 10.1137/0216025 · Zbl 0628.68032
[6]	Hoare C. A. R., Comm. Assoc. Comput. Mach. 12 pp 576–
[7]	DOI: 10.1016/S0021-8693(03)00314-4 · Zbl 1041.20043
[8]	DOI: 10.1142/S0218196706003426 · Zbl 1117.08003
[9]	DOI: 10.1006/jabr.1999.7939 · Zbl 0939.16013
[10]	DOI: 10.1145/343369.343378 · Zbl 1365.68326
[11]	DOI: 10.1016/j.tcs.2005.09.069 · Zbl 1086.68082
[12]	DOI: 10.1007/BF01190447 · Zbl 0795.08006
[13]	DOI: 10.1016/S0049-237X(08)72018-4
[14]	DOI: 10.1137/0216033 · Zbl 0654.68029
[15]	DOI: 10.1137/0220049 · Zbl 0736.68061
[16]	DOI: 10.1007/BF02573019 · Zbl 0197.29404
[17]	Schein B. M., Amer. Math. Soc. Translat. Ser. 2 113 pp 123– · Zbl 0404.20057
[18]	DOI: 10.1007/s000120050065 · Zbl 0935.06013
[19]	Stokes T., Acta Sci. Math. (Szeged) 72 pp 481–