Monoids with tests and the algebra of possibly non-halting programs

Simple item page
dc.contributor.authorJackson, Marcel
dc.contributor.authorStokes, Tim E.
dc.date.accessioned2015-04-15T04:29:48Z
dc.date.available2015-03
dc.date.available2015-04-15T04:29:48Z
dc.date.issued2015-03
dc.description.abstractWe study the algebraic theory of computable functions, which can be viewed as arising from possibly non-halting computer programs or algorithms, acting on some state space, equipped with operations of composition, if-then-else and while-do defined in terms of a Boolean algebra of conditions. It has previously been shown that there is no finite axiomatisation of algebras of partial functions under these operations alone, and this holds even if one restricts attention to transformations (representing halting programs) rather than partial functions, and omits while-do from the signature. In the halting case, there is a natural “fix”, which is to allow composition of halting programs with conditions, and then the resulting algebras admit a finite axiomatisation. In the current setting such compositions are not possible, but by extending the notion of if-then-else, we are able to give finite axiomatisations of the resulting algebras of (partial) functions, with while-do in the signature if the state space is assumed finite. The axiomatisations are extended to consider the partial predicate of equality. All algebras considered turn out to be enrichments of the notion of a (one-sided) restriction semigroup
dc.format.mimetypeapplication/pdf
dc.identifier.citationJackson, M., & Stokes, T. E. (2015). Monoids with tests and the algebra of possibly non-halting programs. Journal of Logical and Algebraic Methods in Programming, 84(2), 259–275. http://doi.org/10.1016/j.jlamp.2014.08.007en
dc.identifier.doi10.1016/j.jlamp.2014.08.007
dc.identifier.issn2352-2208
dc.identifier.urihttps://hdl.handle.net/10289/9274
dc.language.isoen
dc.publisherElsevier
dc.relation.isPartOfJournal of Logical and Algebraic Methods in Programming
dc.rightsThis is an author’s accepted version of an article published in the journal: Journal of Logical and Algebraic Methods in Programming. © 2015 Elsevier.
dc.subjectScience & Technology
dc.subjectTechnology
dc.subjectComputer Science, Theory & Methods
dc.subjectLogic
dc.subjectComputer Science
dc.subjectScience & Technology - Other Topics
dc.subjectComputable partial functions
dc.subjectAlgebraic models of computation
dc.subjectDeterministic programs
dc.subjectDomain
dc.subjectRestriction semigroup
dc.subjectIf-then-else
dc.subjectIF-THEN-ELSE
dc.subjectBINARY RELATIONS
dc.subjectSEMIGROUPS
dc.subjectAXIOMATIZABILITY
dc.subjectCORRECTNESS
dc.subjectCATEGORIES
dc.subjectDOMAIN
dc.titleMonoids with tests and the algebra of possibly non-halting programs
dc.typeJournal Article
pubs.begin-page259
pubs.elements-id119492
pubs.end-page275
pubs.issue2
pubs.organisational-group/Waikato
pubs.organisational-group/Waikato/FCMS
pubs.organisational-group/Waikato/FCMS/Mathematics
pubs.publication-statusPublished
pubs.volume84
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Logic-Program-84.pdf
Size:
253.64 KB
Format:
Adobe Portable Document Format
Description:
Accepted version
Thumbnail Image
Name: Logic-Program-84.pdf
Size: 253.64 KB
Kind: Adobe PDF
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
Deposit Agreement.txt
Size:
193 B
Format:
Unknown data format
Description:
Name: Deposit Agreement.txt
Size: 193 B
Kind: Unknown
Collections
Computing and Mathematical Sciences Papers