Programs as term transformers

Article type: Research Article

Authors: Sokołowski, Stefan

Affiliations: University of Gdańsk

Abstract: Predicates describing the states of computation may be regarded as functions into the Boolean algebra {false, true} and programs as transformers of those functions. If we do not restrict ourselves to this algebra, we get instead terms describing the states of computation and programs transforming the terms. In many cases this approach turns out to be more natural. This paper is a mathematical study of partial correctness and termination of programs in the language of term transformations.

Keywords: semantics of programs, partial correctness, termination, calculus of relations, test relations, term transformers

DOI: 10.3233/FI-1980-3403

Journal: Fundamenta Informaticae, vol. 3, no. 4, pp. 419-431, 1980