Home
Scholarly Works
PROJECTIONS OF SEMICOMPUTABLE RELATIONS ON...
Journal article

PROJECTIONS OF SEMICOMPUTABLE RELATIONS ON ABSTRACT DATA TYPES

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.

Authors

TUCKER JV; ZUCKER JI

Journal

International Journal of Foundations of Computer Science, Vol. 2, No. 03, pp. 267–296

Publisher

World Scientific Publishing

Publication Date

September 1, 1991

DOI

10.1142/s0129054191000170

ISSN

0129-0541

Labels

View published work (Non-McMaster Users)

Contact the Experts team