Browse Prior Art Database

Lucid-Boxes Vs. Black-Boxes

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

Publishing Venue

Software Patent Institute

Related People

Uzi Vishkin: AUTHOR [+3]

Abstract

An explicit understanding of the opportunity for constructing new algorithms out of existing (or supposedly existing) algorithms is presented. Say that [Equation ommitted] are problems. We present an abstract setting that provides for the effective use of algorithms for problems [Equation ommitted] for the design of efficient algorithms for problem B. A notion of "lucid boxes" which is an extention of "black boxes" is introduced for this purpose. t -2-

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

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Lucid-Boxes Vs. Black-Boxes

by Uzi Vishkin Technical Report No. 81 July Lucid-Boxes Vs. Black-Boxes

(June 83)

Uzi Vishkin Courant Institute, New York University

ABSTRACT.

An explicit understanding of the opportunity for constructing new algorithms out of existing (or supposedly existing) algorithms is presented. Say that

(Equation Omitted)

are problems. We present an abstract setting that provides for the effective use of algorithms for problems

(Equation Omitted)

for the design of efficient algorithms for problem B. A notion of "lucid boxes" which is an extention of "black boxes" is introduced for this purpose. t -2-

2. Lucid-box Compositions of Procedures.

We try to give a self-contained presentation. However, in a few cases the reader will be referred to [AHU]. (It is referenced as 'the book' in some places.) As a mean of presentation we specify places in the book where 'patches' are proposed. The reader is assumed to be familiar with the contents of sections 1.2, 1.3, 1.4 and 1.8 where the random access machine (RAM), the random-access-stored-program-machine (RASP) and Pidgin ALGOL are introduced. Unlike conventional programming languages Pidgin ALGOL programs should be read by a human reader rather than a machine. Pidgin ALGOL permits a succinct presentation of algorithms in the book. A Pidgin ALGOL program can be translated into a RAM or RASP program in a straightforward manner. It _7_

is necessary to consider time and space required to execute the code corresponding to a Pidgin ALGOL statement or a RAM or RASP. Later we say how, to extend Pidgin ALGOL in order to include lucid-box composition of procedures, tae start by presenting a machine which is slightly different from both the RAM and RASP. The changes relative to the RAM in the definition of this machine reflect proposed changes in Y the definition of the extended Pidgin ALGOL with respect to Pidgin . ALGOL; thereby, implying how to translate statements of the extended Pidgin ALGOL into this machine. We call this new machine random-access-memory-and-program machine (RAMP). The only difference between the RAMP and the known RAM is that the program is located in a read-only memory. Recall that the indirect read instruction 'READ *i' means: "copy the register whose number is the content of register i into the accumulator". The `READ *i' instruction of our machine may refer also to locations (registers) in the program part of

New York University Page 1 Dec 31, 1983

Page 2 of 13

Lucid-Boxes Vs. Black-Boxes

the machine. (The instructions are encoded by integers. For an example of a similar encoding see the presentation of the RASP in the book.) The book shows that the order of time (and space) complexities of the RAM and RASP are the same for the same algorithm if the cost of instructions is either uniform or logarithmic. No new ideas are required in order to establish similar relationships between the RAM (or...