Mathematics of Program Construction: Third International Conference, MPC '95, Kloster Irsee, Germany, July 17 - 21, 1995. Proceedings (Lecture Notes in Computer Science, 947)

This volume constitutes the proceedings of the Third International Conference on the Mathematics of Program Construction, held at Kloster Irsee, Germany in July 1995. Besides five invited lectures by distinguished researchers there are presented 19 full revised papers selected from a total of 58 submissions. The general theme is the use of crisp, clear mathematics in the discovery and design of algorithms and in the development of corresponding software and hardware; among the topics addressed are program transformation, program analysis, program verification, as well as convincing case studies. Towards Automatic Parallelization Of Logic Programs / K.r. Apt -- Functional Algorithm Design / R.s. Bird -- Mathematics Of Software Engineering / M. Broy -- Program Construction In Intuitionistic Type Theory / T. Coquand -- Computer-aided Computing / N. Shankar -- Derivation Of Parallel Algorithms From Functional Specifications To Csp Processes / A.e. Abdallah -- Architecture Independent Massive Parallelization Of Divide-and-conquer Algorithms / K. Achatz, W. Schulte -- Exploring Summation And Product Operators In The Refinement Calculus / R.-j.r. Back, M. Butler -- An Action System Specification Of The Caltech Asynchronous Microprocessor / R.-j.r. Back, A.j. Martin, K. Sere -- Formal Derivation Of Csp Programs From Temporal Specifications / R. Berghammer, B. Von Karger -- A Compositional Proof System For Asynchronously Communicating Processes / F.s. De Boer, M. Van Hulst -- A Graphical Calculus / S. Curtis, G. Lowe -- A Simple, Efficient, And Flexible Implementation Of Flexible Arrays / V.j. Dielissen, A. Kaldewaij -- Induction And Recursion On Datatypes / H. Doornbos, R. Backhouse -- Program Construction By Parts / M. Frappier, A. Mili, J. Desharnais -- An Initial-algebra Approach To Directed Acrylic Graphs / J. Gibbons -- Algebraic Proof Assistants In Hol / R. Groenboom [and Others] -- Angelic Termination In Dijkstra's Calculus / W.h. Hesselink -- Extracting Programs With Exceptions In An Impredicative Type System / J.-f. Monin -- Synthesising Proofs From Programs In The Calculus Of Inductive Constructions / C. Parent -- A General Scheme For Breadth-first Graph Traversal / M. Russling -- Specware : Formal Support For Composing Software / Y.v. Srinivas, R. Jüllig -- A Refinement Relation Supporting The Transition From Unbounded To Bounded Communication Buffers / K. Stølen -- Impunity : Unity With Procedures And Local Variables / R.t. Udink, J.n. Kok. Bernhard Möller, Ed. Includes Bibliographical References. Towards automatic parallelization of logic programs....Pages 1-1 Functional Algorithm Design....Pages 2-17 Mathematics of software engineering....Pages 18-48 Program construction in intuitionistic Type Theory....Pages 49-49 Computer-aided computing....Pages 50-66 Derivation of parallel algorithms from functional specifications to CSP processes....Pages 67-96 Architecture independent massive parallelization of divide-and-conquer algorithms....Pages 97-127 Exploring summation and product operators in the refinement calculus....Pages 128-158 An action system specification of the caltech asynchronous microprocessor....Pages 159-179 Formal derivation of CSP programs from temporal specifications....Pages 180-196 A compositional proof system for asynchronously communicating processes....Pages 197-213 A graphical calculus....Pages 214-231 A simple, efficient, and flexible implementation of flexible arrays....Pages 232-241 Induction and recursion on datatypes....Pages 242-256 Program construction by parts....Pages 257-281 An initial-algebra approach to directed acyclic graphs....Pages 282-303 Algebraic proof assistants in HOL....Pages 304-321 Angelic termination in Dijkstra's calculus....Pages 322-334 Extracting programs with exceptions in an impredicative type system....Pages 335-350 Synthesizing proofs from programs in the Calculus of Inductive Constructions....Pages 351-379 A general scheme for breadth-first graph traversal....Pages 380-398 Specware: Formal support for composing software....Pages 399-422 A refinement relation supporting the transition from unbounded to bounded communication buffers....Pages 423-451 ImpUNITY: UNITY with procedures and local variables....Pages 452-472 A common approach in software engineering is to apply during the design phase a variety of structured techniques like top-down design, decomposition and abstraction, while only subsequently, in the implementation phase, is the design tested to ensure reliability. But this approach neglects that central aspects of software design and program development have a strong formal character which admits tool support for the construction of reliable and correct computer systems based on formal reasoning. This monograph provides much information both for theoreticians interested in algebraic theories, and for software engineers building practically relevant tools. The author presents the theoretical foundations needed for the verification of reactive, sequential infinite-state systems. Two new algorithms are introduced allowing for automatic verification of important aspects such as safety or liveness properites of a given infinite-state system. The formal framework developed involves recent results from various theoretical areas like process algebras, fixpoint theory, modal logics and model checking