La Trobe

Restriction in Program Algebra

Download (598.5 kB)
journal contribution
posted on 2023-10-11, 00:53 authored by Marcel JacksonMarcel Jackson, Tim Stokes

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.

History

Publication Date

2023-10-01

Journal

Logic Journal of the IGPL

Volume

31

Issue

5

Pagination

35p. (p. 926-960)

Publisher

Oxford University Press

ISSN

1367-0751

Rights Statement

This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted reuse, distribution, and reproduction in any medium, provided the original work is properly cited.

Usage metrics

    Journal Articles

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC