Loading...
Thumbnail Image
Item

Restriction in Program Algebra

Abstract
We provide complete classifications of algebras of partial maps for a significant swathe of combinations of operations not previously classified. Our focus is the many subsidiary operations that arise in recent considerations of the ‘override’ and ‘update’ operations arising in specification languages. These other operations turn out to have an older pedigree: domain restriction, set subtraction and intersection. All signatures considered include domain restriction, at least as a term. Combinations of the operations are classified and given complete axiomatizations with and without the presence of functional composition. Each classification is achieved by way of providing a concrete representation of the corresponding abstract algebras as partial maps acting on special kinds of filters determined with respect to various induced orders. In contrast to many negative results in the broader area, all of the considered combinations lead to finite axiomatizations.
Type
Journal Article
Type of thesis
Series
Citation
Date
2022-07-19
Publisher
OXFORD UNIV PRESS
Degree
Supervisors
Rights
© The Author(s) 2022. This is an Open Access article distributed under the terms of the Creative Commons Attribution License.