Parallel Functions In Recursive Program Schemes

Abstract:- We consider models of sequential programs (recursive program schemes) and analyze their extension with parallel functions. For this purpose, we introduce a special class of parallel functions (called invariant functions) that don’t depend on interpretation of domain on which they are defined. Expressive power of extended classes of recursive schemes is analyzed in terms of sequential reducibility between the used parallel functions. It is shown that the obtained hierarchy of schemes is infinite but not dense. Key-Words:- Program models, semantics, parallel functions, expressive power