Hirsch, R;
Jackson, M;
Mikulas, S;
(2016)
The algebra of functions with antidomain and range.
Journal of Pure and Applied Algebra
, 220
(6)
pp. 2214-2239.
10.1016/j.jpaa.2015.11.003.
Preview |
Text
Hirsch_FunctionAlgebra_revisedJPAArevised.pdf Download (399kB) | Preview |
Abstract
We give complete, finite quasiequational axiomatisations for algebras of unary partial functions under the operations of composition, domain, antidomain, range and intersection. This completes the extensive programme of classifying algebras of unary partial functions under combinations of these operations. We also look at the complexity of the equational theories and provide a nondeterministic polynomial upper bound. Finally we look at the problem of finite representability and show that finite algebras can be represented as a collection of functions over a finite base set provided that intersection is not in the signature.
| Type: | Article |
|---|---|
| Title: | The algebra of functions with antidomain and range |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.jpaa.2015.11.003 |
| Publisher version: | http://dx.doi.org/10.1016/j.jpaa.2015.11.003 |
| Language: | English |
| Additional information: | Copyright © 2016. This manuscript version is published under a Creative Commons Attribution Non-commercial Non-derivative 4.0 International licence (CC BY-NC-ND 4.0). This licence allows you to share, copy, distribute and transmit the work for personal and non-commercial use providing author and publisher attribution is clearly stated. Further details about CC BY licences are available at http://creativecommons.org/licenses/by/4.0. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/1498508 |
Archive Staff Only
 |
View Item |
