Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

TRANSLATABILITY AND DECIDABILITY QUESTIONS FOR RESTRICTED CLASSES OF PROGRAM SCHEMAS

IP.com Disclosure Number: IPCOM000128227D
Original Publication Date: 1978-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 13 page(s) / 39K

Publishing Venue

Software Patent Institute

Related People

ELAINE J. WEYUKER: AUTHOR [+3]

Abstract

Two hew classes of schemas are introduced: the reachable s,.,hemas and the 3emifree schemas. A schema is reachable if every statement in the schema is executed under some.-interpretation. A schema is semifree if every test in the schema is necessary in the sewe that each exit of the test is taken under some interpretation. It is shown that most of the standard decision problems are unsolvable for schemas in these two classes, and that there can be no algorithm which effectively translates an arbitrary schema into an equivalent reachable or semifree schema, even though such equivalent schemas always exist. These classes are also compared to the free and liberal schemas, and interclass translatability questions are investigated. It is demonstrated that every reachable schema can be effectiveiy translated into a semifree schema, even though it is not decidable whether a reachable schema is semifree. I Key words: program schema, flowchart schema,.abstract program, translatability, decision problems

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 11% of the total text.

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

TRANSLATABILITY AND DECIDABILITY QUESTIONS FOR RESTRICTED CLASSES OF PROGRAM SCHEMAS

BY ELAINE J. WEYUKER OCTOBER 1978 REPORT NO. 006

ABSTRACT

Two hew classes of schemas are introduced: the reachable s,.,hemas and the 3emifree schemas. A schema is reachable if every statement in the schema is executed under some.- interpretation. A schema is semifree if every test in the schema is necessary in the sewe that each exit of the test is taken under some interpretation.

It is shown that most of the standard decision problems are unsolvable for schemas in these two classes, and that there can be no algorithm which effectively translates an arbitrary schema into an equivalent reachable or semifree schema, even though such equivalent schemas always exist. These classes are also compared to the free and liberal schemas, and interclass translatability questions are investigated. It is demonstrated that every reachable schema can be effectiveiy translated into a semifree schema, even though it is not decidable whether a reachable schema is semifree. I

Key words: program schema, flowchart schema,.abstract program,

translatability, decision problems

I.INTRODUQTIQN and DEFINITIONS

For several years, people have studied abstractions of computer programs known as program schemas. A great deal of work has been done comparJ.ng the relative computational power of classes of schemas with additional features [11, (21, (8]. We are interested in considering classes of schemas whose -embers fulfill certain semantic requirements. We introduce two such classes of schemas, the semifree schemas and the reachable schemas, and consider various decision problems for these classes. We also consider the relative power of these classes. We compare them to the class of all schemas as well as to other well-known semantically restricted classes. We use a program schema model based largely on the one formulated by Luckham, Park, and Paterson [6].

We have a formal language whose alphabet consists of the following disjoint sets of symbols: (i) Vari&bIg = Locatign Symbols, denoted by the letters u,v,w,x,y,z. The set of variables is divided into three disjoint subsets X,Y, and Z. The set X contains the input yariables, Y is the set of 2rogram ygriables, and Z is the set of output variables. The value of a variable in X may be retrieved but never changed, whereas an element of Z may be assigned a value, but may never be retrieved from. An element of Y may either be retrieved from or assigned to provided it has been assigned a value before it is retrieved from or tested. (ii) Function Symbols, denoted by the letters f,g,h. (11i) Predicate Symbolg, denoted by the letters p,q,r,s,t. (iv) Disting-uished Symbols: START, HALT, numerals, comma. Each of the symbols in i, ii, and iii may appear with

New York University Page 1 Dec 31, 1978

Page 2 of 13

TRANSLATABILITY AND DECIDABILITY QUESTIONS FOR RESTRICTED CLASSES OF...