A faithful embedding of parallel computations in star-finite models

The purpose of this paper is to show that there exist star-finite tree-structured sets in which the computations of parallel programs can be faithfully embedded, and that the theory of star-finite sets and relations therefore provides a new tool for the analysis of non-deterministic computations.This research was carried out while the author held a Postdoctoral Fellowship from the Natural Sciences and Engineering Research Council of Canada. The author also gratefully acknowledges the support of the Centre inter-universitaire en études catégoriques de Montréal.