1,205 papers · page 56 of 61
The basic idea of the Schorr-Waite graph-marking algorithm can be precisely formulated, explained, and verified in a completely applicative (functional) programming style.Graphs are specified algebraically as objects of an abstract data type.When formulating recursive programs ov…
article Free Access Share on Efficient Computation of LALR(1) Look-Ahead Sets Authors: Frank DeRemer Computer and Information Sciences, University of California, Santa Cruz, CA Computer and Information Sciences, University of California, Santa Cruz, CAView Profile , Thomas Pennel…
Transformational programming is a relatively new programming technique intended to derive complex algorithms automatically.Initially, a set of transformational rules is described, and an initial specification of the problem to be programmed is given.The specification is written i…
An IEEE Computer Society working group on floating-point arithmetic has recommended a standard for binary floating.pointnumber formats, operations, and semantics.This paper, which has evolved in part during the deliberations of that committee, describes the significance to langua…
article Free Access Share on A System for Assisting Program Transformation Author: Martin S. Feather USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CA USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CAView Profile Authors Info & Cl…
of Expressions in IconExpressions in the Icon programming language may be conditional, possibly producing no result, or they may be generators, possibly producing a sequence of results.Generators, coupled with a goaldirected evaluation mechanism, provide a concise method for expr…
of Optimized
data types have proved to be a useful technique for structuring systems.In large systems it is sometimes useful to have different regions of the system use different representations for the abstract data values.A technique is described for communicating abstract values between su…
Equations provide a convenient notation for defining many computations, for example, for programming language interpreters.This paper illustrates the usefulness of equational programs, describes the problems involved in implementing equational programs, and investigates practical…
S/SL (Syntax/Semantic Language) is a language that was developed for implementing compilers.A subset called SL (Syntax Language) has the same recognition power as do LR(k) parsers.Complete S/SL includes invocation of semantic operations implemented in another language such as PAS…
article Free Access Share on A Model for Implementing EUCLID Modules and Prototypes Authors: Richard C. Holt Computer Systems Research Group, University of Toronto, Toronto, Ontario, Canada M5S 1A1 Computer Systems Research Group, University of Toronto, Toronto, Ontario, Canada M…
Reliable computer systems must handle malfunctioning components that give conflicting information to different parts of the system.This situation can be expressed abstractly in terms of a group of generals of the Byzantine army camped with their troops around an enemy city.Commun…
Formal specification techniques and data abstractions have seen little application to computer graphics.Many of the objects and operations unique to graphics programs can be handled conveniently by def'ming special graphic data types.Not only do graphic data types provide an attr…
The unification problem in f'mst-order predicate calculus is described in general terms as the solution of a system of equations, and a nondeterministic algorithm is given.A new unification algorithm, characterized by having the acyclicity test efficiently embedded into it, is de…
VAL is a high-level, function-based language designed for use on data flow computers.A data flow computer has many small processors organized to cooperate in the execution of a single computation.A computation is represented by its data flow graph; each operator in a graph is sch…
In this paper it is shown how the Dijkstra-Scholten scheme for termination detection in a diffusing computation can be adapted to detect termination or deadlock in a network of communicating sequential processes as defined by Hoare.
A knot in a directed graph is a useful concept in deadlock detection.A distributed algorithm for identifying a knot in a graph by using a network of processes is presented.The algorithm is based on the work of Dijkstra and Scholten.
A liveness property asserts that program execution eventually reaches some desirable state.While termination has been studied extensively, many other liveness properties are important for concurrent programs.A formal proof method, based on temporal logic, for deriving liveness pr…
Finite differencing is a program optimization method that generalizes strength reduction, and provides an efficient implementation for a host of program transformations including "iterator inversion."Finite differencing is formally specified in terms of more basic transformations…