J.V. Tucker and J.I. Zucker (1991):
Projections of semicomputable relations on abstract data types,
International Journal of Foundations of Computer Science,
2, 267-296.
[text.ps]
Abstract.
We consider projections of semicomputable relations on
abstract structures We show that they arise in several
contexts, including nondeterministic extensions of `while'
programs with arrays by means of arbitrary initializations
and random assignments. They form a basis for an
investigation of the concept of algorithmic specifications
of relations with nondeterministic search.
An important technique in this investigation is the study of computation trees for imperative programs, in order to prove characterization theorems for semicomputable sets, of a form first developed by E. Engeler.