Free semiring-representations and nondeterminism

摘要

Semirings provide a simple abstract model of the syntax for a nondeterministic programming language. Each element of a semiring is a nondeterministic program segment, and the semiring operations (+ and ⊎) correspond to nondeterministic or and program composition. This is analogous to using an algebraic theory for the abstract syntax of a deterministic language. In the case of algebraic theories, an algebra provides the semantics, and free algebras (which always exist) are particularly important. For a semiring, semantics is provided by a representation as a system of relations. This paper examines the question of when free representations exist. Unlike free algebras, free representations do not always exist. It is shown that a semiring has free representations generated by arbitrary sets of variables iff it has a free representation generated by a single variable. Examples of semirings are given that do not have free representations. However, for an important class of semirings, free representations are always available. This class consists of semirings which arise when nondeterminism is freely added to a deterministic programming language.