References

BB

Christoph Beierle and Egon Börger, ``Correctness proof for the WAM with types'', Springer LNCS 626 (1992), 15-34.

The Börger-Rosenzweig's correctness proof for compiling Prolog to WAM [BRo1] is extended to the Protos-L language which extends Prolog with polymorphic (dynamic) types.

Bl

Bob Blakley, ``A Smalltalk Evolving Algebra And Its Uses'', Ph. D. Thesis, University of Michigan, 1992.

An early student work on evolving algebras (the late date of 1992 is accidental). A reduced version of Smalltalk (called Mumble) is formalized and studied.

Bo1

Egon Börger, ``A Logical Operational Semantics for Full Prolog. Part I: Selection Core and Control'', CSL'89, 3rd Workshop on Computer Science Logic (eds. E. Börger et al. ), Springer LNCS 440 (1990), 36-64.

Bo2

Egon Börger, ``A Logical Operational Semantics for Full Prolog. Part II: Built-in Predicates for Database Manipulations'', in Proc. of Mathematical Foundations of Computer Science 1990 (ed. B. Rovan), Springer LNCS 452, 1-14.

Bo3

Egon Börger, ``A Logical Operational Semantics of Full Prolog. Part III: Built-in Predicates for Files, Terms, Arithmetic and Input-Output'', in: Y. Moschovakis (ed. ), ``Logic from Computer Science'', Mathematical Sciences Research Institute Publications, vol. 21, Springer Verlag, 1992, 17-50.

These are the original 3 papers of Börger where he gives a complete evolving-algebra formalization of Prolog with all features discussed in the WG17 of ISO. An improved (tree based) version is found in [BRo2].

BD

Egon Börger and K. Daessler, ``PROLOG: DIN Papers for Discussion'', in ISO/IEC JTCI SC22 WG17 No. 58, National Physical Laboratory, Middlesex, 1990, 114 pages.

A version of [Bo1-3] proposed to WG17 as a complete formal semantics of Prolog.

BRi1

Elvinia Riccobene and Egon Börger, ``A Formal Specification of Parlog'', in ``Semantics of Programming Languages and Model Theory'' (eds. M. Droste and Y. Gurevich), Gordon and Breach, 1993, to appear. [Preliminary version in Springer LNCS 567 (1992) and 592 (1992).]

An evolving algebra formalization of Parlog, a well known parallel version of Prolog.

BRi2

Elvinia Riccobene and Egon Börger, ``A Mathematical Model of Concurrent Prolog'', CSTR-92-15, Dept. of Computer Science, University of Bristol, 1992.

An evolving algebra formalization of Ehud Shapiro's Concurrent Prolog.

BRo1

Egon Börger and Dean Rosenzweig, ``The WAM - Definition and Compiler Correctness'', TR-14/92, Dipartimento di Informatica, Universita di Pisa, June 1992, 57 pages. [Previous version in Springer LNCS 533 and 592.]

The first substantial example of the successive refinement method in the area. A hierarchy of evolving algebras provides a solid foundation for constructing provably correct compilers from Prolog to WAM. Various refinement steps take care of different distinctive features (``orthogonal components'' in the authors' metaphor) of WAM making the specification as well as the correctness proof modular and extendible; an example of such an extension is found in [BB].

BRo2

Egon Börger and Dean Rosenzweig, ``A Simple Mathematical Model for Full Prolog'', TR-33/92, Dipartimento di Informatica, Universita di Pisa, October 1992, 23 pages.

An improved version of [Bo1-3].

BS

Egon Börger and Peter Schmitt, ``A formal operational semantics for languages of type Prolog III'', CSL'90, 4th Workshop on Computer Science Logic (eds. E. Börger et al. ), Springer LNCS 533, 1991, 67-79.

An evolving algebra formalization of Alain Colmerauer's constraint logic programming language Prolog III.

GR

Paola Glavan and Dean Rosenzweig, ``Communicating Evolving Algebras - Part 1'', Manuscript, University of Zagreb, Croatia, October 1992.

The first part of a two-part paper, presented at CSL'92, aimed to ``demonstrate the power of the framework by providing simple and transparent models of the (polyadic) -calculus of Milner, the Chemical Abstract Machine of Berry and Boudol, and TCCS of de Niccola and Henessy''.

GKS

Georg Gottlob, Gerti Kappel and Michael Schrefl, ``Semantics of Object-Oriented Data Models - The Evolving Algebra Approach'', in ``Next Generation Information Technology'' (eds. J. W. Schimdt and A. A. Stogny), Springer LNCS 504, 144-160.

``In this paper we show how evolving algebras can be used in particular to define the operational semantics of object creation, of overriding and dynamic binding, and of inheritance at the type level (type specialization) and at the instance level (object specialization).''

Gr

George Gratzer, ``Universal Algebra'', Van Nostrand, 1968.

Gu1

Yuri Gurevich, ``Logic and the challenge of computer science", In ``Current Trends in Theoretical Computer Science" (ed. E. Börger), Computer Science Press, 1988, 1-57.

The introduction and the first use of evolving algebras (at the end of the paper).

Gu2

Yuri Gurevich, ``Algorithms in the world of bounded resources", in ``The universal Turing machine - a half-century story", (ed. R. Herken), Oxford University Press, 1988, 407-416.

Gu3

Yuri Gurevich, ``Kolmogorov machines and related issues: The column on logic in computer science", Bulletin of EATCS, No. 35, June 1988, 71-82.

Gu4

Yuri Gurevich, ``Evolving Algebra 1993: Lipari Guide", in ``Specification and Validation Methods", Ed. E. Börger, Oxford University Press, 1995, 9-36.

GMr

Yuri Gurevich and James Morris, ``Algebraic operational semantics and Modula-2", CSL'87, 1st Workshop on Computer Science Logic, Springer LNCS 329 (1988), 81-101.

An abstract of [Mo].

GMs

Yuri Gurevich and Larry Moss ``Algebraic Operational Semantics and Occam'', Springer LNCS 440, 176-192.

The first application of evolving algebras to distributed parallel computing with the challenge of true concurrency.

GH

Yuri Gurevich and James Huggins, ``The Evolving Algebra Semantics of C'', CSE-TR-141-92, EECS Department, University of Michigan, 1992.

The method of successive refinements is used to give a more succinct semantics of the C programming language.

JM

David E. Johnson and Lawrence S. Moss, ``Dynamic Syntax'', 1993 (to appear).

Distributed Evolving Algebras are used to model formalisms for natural language syntax.

KS

Gerti Kappel and Michael Schrefl, ``Cooperation Contracts'', Proc. 10th International Conference on the Entity Relationship Approach (ed. T. J. Teorey), San Mateo, California, 1991, ER Institute, 285-307.

The authors introduce the concept of cooperative message handling and use evolving algebras to give formal semantics.

KR

Brian W. Kernighan and Dennis M. Ritchie, ``The C Programming Language'', Prentice-Hall, 1988, Englewood Cliffs, NJ.

KU

A. N. Kolmogorov and V. A. Uspensky, ``To the Definition of an Algorithm'', Uspekhi Mat. Nauk 13:4 (1958), 3-28 (Russian); English translation in AMS Translations, ser. 2, vol. 21 (1963), 217-245

Mo

James Morris, ``Algebraic operational semantics for Modula 2'', Ph.D. thesis, University of Michigan, 1988.

The earliest formalization of a real-life language. In the meantime, the methodology has developed enabling more elegant descriptions, but one has to start somewhere.

Pr

Vaughan R. Pratt, ``Dynamic algebras and the nature of induction'', 12th ACM Symposium on Theory of Computation, 1980.

Sch

Arnold Schönhage A, ``Storage Modification Machines'', SIAM J. on Computing 9:3 (1980), 490-508.

Tu

Alan M. Turing, ``On computable numbers with an application to the Entscheidungsproblem," Proc. London Math. Soc. 42 (1937) 230-265; correction, ibid, No. 43 (1937), 544-546.

WG17

``PROLOG. Part 1, General Core, Committee Draft 1.0'', ISO/IEC JTCI SC22 WG17 No. 92, 1992.