This monograph studies the logical aspects of domains as used in de notational semantics of programming languages. Frameworks of domain logics are introduced; these serve as foundations for systematic derivations of proof systems from denotational semantics of programming languages. Any proof system so derived is guaranteed to agree with denotational se mantics in the sense that the denotation of any program coincides with the set of assertions true of it. The study focuses on two categories for dena tational semantics: SFP domains, and the less standard, but important, category of stable...

Recently, a variety ofresults on the complexitystatusofthegraph isomorphism problem has been obtained. These results belong to the so-called structural part of Complexity Theory. Our idea behind this book is to summarize such results which might otherwise not be easily accessible in the literature, and also, to give the reader an understanding of the aims and topics in Structural Complexity Theory, in general. The text is basically self contained; the only prerequisite for reading it is some elementary knowledge from Complexity Theory and Probability Theory. It can be used to teach a seminar...

The original motivation of this study comes from the following questions that were mentioned to one ofus by H. Matano. Let 2 2 G= B = {x=(X1lX2) E 2; x + x = Ixl

Our Subjects and Objectives. This book is about algebraic and symbolic computation and numerical computing (with matrices and polynomials). It greatly extends the study of these topics presented in the celebrated books of the seventies, AHU] and BM] (these topics have been under-represented in CLR], which is a highly successful extension and updating of AHU] otherwise). Compared to AHU] and BM] our volume adds extensive material on parallel com- putations with general matrices and polynomials, on the bit-complexity of arithmetic computations (including some recent techniques of data...

Combinatory logic started as a programme in the foundation of mathematics and in an historical context at a time when such endeavours attracted the most gifted among the mathematicians. This small volume arose under quite differ ent circumstances, namely within the context of reworking the mathematical foundations of computer science. I have been very lucky in finding gifted students who agreed to work with me and chose, for their Ph. D. theses, subjects that arose from my own attempts 1 to create a coherent mathematical view of these foundations. The result of this collaborative work is...

Harmonic maps are solutions to a natural geometrical variational prob lem. This notion grew out of essential notions in differential geometry, such as geodesics, minimal surfaces and harmonic functions. Harmonic maps are also closely related to holomorphic maps in several complex variables, to the theory of stochastic processes, to nonlinear field theory in theoretical physics, and to the theory of liquid crystals in materials science. During the past thirty years this subject has been developed extensively. The monograph is by no means intended to give a complete description of the theory of...

by Luea Cardelli Ever since Strachey's work in the 1960's, polymorphism has been classified into the parametric and overloading varieties. Parametric polymorphism has been the subject of extensive study for over two decades. Overloading, on the other hand, has often been considered too ad hoc to deserve much attention even though it has been, in some form, an ingredient of virtually every programming lan- guage (much more so than parametric polymorphism). With the introduction of object-oriented languages, and in particular with multiple-dispatch object-oriented languages, overloading has...

During the last three decades several different styles of semantics for program ming languages have been developed. This book compares two of them: the operational and the denotational approach. On the basis of several exam ples we show how to define operational and denotational semantic models for programming languages. Furthermore, we introduce a general technique for comparing various semantic models for a given language. We focus on different degrees of nondeterminism in programming lan guages. Nondeterminism arises naturally in concurrent languages. It is also an important concept in...

To construct a compiler for a modern higher-level programming languagel one needs to structure the translation to a machine-like intermediate language in a way that reflects the semantics of the language. little is said about such struc turing in compiler texts that are intended to cover a wide variety of program ming languages. More is said in the Iiterature on semantics-directed compiler construction 1] but here too the viewpoint is very general (though limited to 1 languages with a finite number of syntactic types). On the other handl there is a considerable body of work using the...