Polyvariant mixed computation for analyzer programs
type: Item
instance of: scholarly article
title: Polyvariant mixed computation for analyzer programs
zbMATH Open document ID: 0544.68005
DOI: 10.1007/BF00271642
author: Mikhail Bulyonkov
published in: Acta Informatica
publication date: 1984-01-01T00:00:00Z
review text: The two major characteristics of mixed computation - termination and depth - are, in general, conflicting. A class of low-level nonstructured programs with fixed partition of the memory into accessible and suspended parts is considered. The further assumption is that, for any fixed partial input data, all the variety of computation generates a finite set of accessible memory states. Under these assumptions a polyvariant mixed computation algorithm is presented which performs all nonsuspended computation and always terminates. The basic idea is to put into correspondence to every accessible memory state its own copy of the initial program. Then the control flow of this multiple program is rearranged in such a way that if a program instruction which corresponds to an accessible memory state S computes a memory state S' then it appoints its successor in the program copy which corresponds to the state S'. The huge resulting program is called a resultant. The residual program is obtained from the resultant through a sequence of abundant reductions which delete all computation over accessible memory and all unreachable instructions. An iterative version of the mixed computation algorithm is also offered when only reachable instructions over actually computed memory states emerge. The general treatment is supplemented by a series of examples demonstrating useful properties of the mixed computation algorithm. One of those is embedding a control structure into the residual program which is not explicitly presented in the initial program but is encoded in the input data.
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 68N01
zbMATH DE Number: 3866552
zbMATH Keywords: termination
zbMATH Keywords: low-level nonstructured programs
zbMATH Keywords: fixed partition
zbMATH Keywords: polyvariant mixed computation algorithm
zbMATH Keywords: control flow
zbMATH Keywords: multiple program
MaRDI profile type: Publication
cites work: Q3919065
cites work: Mixed computation: potential applications and problems for study
cites work: Q4134896
cites work: On folk theorems
description: scientific article; zbMATH DE number 3866552