Semigroups with if-then-else and halting programs

Simple item page
dc.contributor.authorJackson, Marcel
dc.contributor.authorStokes, Tim E.
dc.date.accessioned2010-03-17T22:52:27Z
dc.date.available2010-03-17T22:52:27Z
dc.date.issued2009
dc.description.abstractThe "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.en
dc.format.mimetypeapplication/pdf
dc.identifier.citationJackson, M. & Stokes, T. (2009). Semigroups with if-then-else and halting programs. International Journal of Algebra and Computation (IJAC), 19(7), 937-961.en
dc.identifier.doi10.1142/S0218196709005354en
dc.identifier.urihttps://hdl.handle.net/10289/3728
dc.language.isoen
dc.publisherWorld Scientific Publishing Companyen_NZ
dc.relation.isPartOfInternational Journal of Algebra and Computationen_NZ
dc.relation.urihttp://www.worldscinet.com/ijac/19/1907/S0218196709005354.htmlen
dc.rightsElectronic 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.htmlen
dc.subjecttransformationen
dc.subjectsemigroupen
dc.subjectif-then-elseen
dc.subjectequality testen
dc.titleSemigroups with if-then-else and halting programsen
dc.typeJournal Articleen
pubs.begin-page937en_NZ
pubs.elements-id34636
pubs.end-page961en_NZ
pubs.issue7en_NZ
pubs.volume19en_NZ
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ITEplain.pdf
Size:
264.05 KB
Format:
Adobe Portable Document Format
Thumbnail Image
Name: ITEplain.pdf
Size: 264.05 KB
Kind: Adobe PDF
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.79 KB
Format:
Item-specific license agreed upon to submission
Description:
Name: license.txt
Size: 1.79 KB
Kind: License
Collections
Computing and Mathematical Sciences Papers