Free semiring-representations and nondeterminism
type: Item
instance of: scholarly article
title: Free semiring-representations and nondeterminism
zbMATH Open document ID: 0608.68012
DOI: 10.1016/0022-0000(85)90049-2
author: David B. Benson
author: Michael Main
published in: Journal of Computer and System Sciences
publication date: 1985-01-01T00:00:00Z
review text: 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 \(\bullet)\) correspond to nondeterministic \textbf{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.
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 68N01
Mathematics Subject Classification ID: 68Q55
zbMATH DE Number: 3984550
zbMATH Keywords: syntax for a nondeterministic programming language
zbMATH Keywords: nondeterministic program segment
zbMATH Keywords: nondeterministic \textbf{or}
zbMATH Keywords: program composition
zbMATH Keywords: free representations
MaRDI profile type: Publication
full work available at URL: 0022-0000(85)90049-2
OpenAlex ID: W2060315471
cites work: Q3667921
cites work: Q3907039
cites work: Deterministic and nondeterministic flowchart interpretations
cites work: Q3925881
cites work: Q3959403
description: scientific article; zbMATH DE number 3984550