PROJECTIONS OF SEMICOMPUTABLE RELATIONS ON ABSTRACT DATA TYPES Journal Articles

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, Jeffery

status

• published 

publication date

• September 1991

has subject area

• 08 Information and Computing Sciences (FoR)
• Computation Theory & Mathematics (Science Metrix)

published in

• International Journal of Foundations of Computer Science  Journal

keywords

• 46 Information and Computing Sciences

Digital Object Identifier (DOI)

• 10.1142/s0129054191000170

start page

• 267

end page

• 296

volume

• 02

issue

• 03