2,199 papers · page 106 of 110
Most abstract models of a set of parallel processes define a computation of the model to be a sequence. It is either a sequence of actions taken by the system [Lip] or a sequence of states of the system existing between actions [Kel, Lau, Ash]. Parallelsim is represented only by …
We describe a simplifier for use in program manipulation and verification. The simplifier finds a normal form for any expression over the language consisting of individual variables, the usual boolean connectives, the conditional function cond (denoting if-then-else), the integer…
We study some consequences of the formal language approach to modelling software system behavior for the case of asynchronous, concurrent subsystems. We use the formal language shuffle operation to give an "algebraic" definition of semantics for a simple (structured) concurrent p…
A decision algorithm is given for the quantifier-free theory of recursively defined data structures which, for a conjunction of length n, decides its satisfiability in time linear in n. The first-order theory of recursively defined data structures, in particular the first-order t…
A move algorithm, and some of its formal properties, is presented for use in a practical syntactic error scheme for LR parsers. The algorithm finds fragment (comparable to a valid prefix) just to the right of a point of error detection. For expositional purposes the algorithm is …
A global flow model is assumed; as usual, the flow of control is represented by a digraph called the control flow graph. The objective of our program analysis is the construction of a mapping (a cover) from program text expressions to symbolic expressions for their value holding …
In programming languages which permit both assignment and procedures, distinct identifiers can represent data structures which share storage or procedures with interfering side effects. In addition to being a direct source of programming errors, this phenomenon, which we call int…
The earliest data flow analysis research dealt with concrete problems (such as detection of available expressions) and with low level representations of control flow (with one large graph, each of whose nodes represents a basic block). Several recent papers have introduced an abs…
It has long been known that recursively defined types in a highly typed language such as Algol 68 or Pascal may be tested for structural equivalence by the same algorithm that compares finite automata [5,11]. Several authors (for example, [3,8,9,16]) have proposed that classes of…
Previous work on optimal code generation has usually assumed that the underlying machine has identical registers and that all operands fit in a single register or memory location. This paper considers the more realistic problem of generating optimal code for expressions involving…
A new interprocedural data flow analysis algorithm is presented and analyzed. The algorithm associates with each procedure in a program information about which variables may be modified, which may be used, and which are possibly preserved by a call on the procedure, and all of it…
Procedure call mechanisms have mainly been studied in the framework of recursive programs without assignments, for the simplicity of their operational and denotational semantics (See Scott [16], Nivat [14], Vuillemin [17]).
Article A complete and consistent hoare axiomatics for a simple programming language Share on Authors: J. Cherniavsky SUNY at Stony Brook, N.Y. SUNY at Stony Brook, N.Y.View Profile , S. Kamin SUNY at Stony Brook, N.Y. SUNY at Stony Brook, N.Y.View Profile Authors Info & Claims P…
Hoare-like deduction systems for establishing partial correctness of programs may fail to be complete because of (a) incompleteness of the assertion language relative to the underlying interpretation or (b) inability of the assertion language to express the invariants of loops. S…
A program denotes computations in some universe of objects. Abstract interpretation of programs consists in using that denotation to describe computations in another universe of abstract objects, so that the results of abstract execution give some information on the actual comput…
Article Free Access Share on Social processes and proofs of theorems and programs Authors: Richard A. DeMillo Georgia Institute of Technology Georgia Institute of TechnologyView Profile , Richard J. Lipton Yale University Yale UniversityView Profile , Alan J. Perlis Yale Universi…
Brosgol [Br] formalizes the notion that parsing methods can be classified by the positions at which production rules are recognized. In an LL parser, each rule is recognized at the left end, before the rule's yield has been read; in an LR parser, a rule is recognized at its right…
We develop a theory for the correctness of asynchronous parallel programs. A program is considered correct if its behavior is in some sense similar to that of an abstract version of the program. We discuss various criteria for this similarity. We then concentrate on one of them a…