J.A. Bergstra, University of Amsterdam/A. Ponse, University of Amsterdam
S.A. Smolka, State University of New York at Stony Brook
Handbook of Process Algebra
Description
Process Algebra is a formal description technique for complex computer systems, especially those involving communicating, concurrency executing components. It is a subject that concurrently touches many topic areas of computer science and discrete math, including system design notations, logic, concurrency theory, specification and verification, operational semantics, algorithms, complexity theory, and, of course, algebra.
This Handbook documents the fate of process algebra since its inception in the late 1970's to the present. It is intended to serve as a reference source for researchers, students, and system designers and engineers interested in either the theory of process algebra or in learning what process algebra brings to the table as a formal system description and verification technique. The Handbook is divided into six parts spanning a total of 19 self-contained Chapters. The organization is as follows. Part 1, consisting of four chapters, covers a broad swath of the basic theory of process algebra. Part 2 contains two chapters devoted to the sub-specialization of process algebra known as finite-state processes, while the three chapters of Part 3 look at infinite-state processes, value-passing processes and mobile processes in particular. Part 4, also three chapters in length, explores several extensions to process algebra including real-time, probability and priority. The four chapters of Part 5 examine non-interleaving process algebras, while Part 6's three chapters address process-algebra
tools and applications.
Contents
Preface (J.A. Bergstra, A. Ponse, S.A. Smolka).
Part 1: Basic Theory.
The linear time - brancing time spectrum I (R.J. van Glabbeek).
Trace-oriented models of concurrency (M. Broy, E.-R. Olderog).
Structural operational semantics (L. Aceto, W.J. Fokkink, C. Verhoef).
Modal logics and mu-calculi: an introduction (J.C. Bradfield, C. Stirling).
Part 2: Finite-State Processes.
Process algebra with recursive operations (J.A. Bergstra, W.J. Fokkink, A. Ponse).
Equivalence and preorder checking for finite-state systems (R. Cleaveland, O. Sokolsky).
Part 3: Infinite-State Processes.
A symbolic approach to value-passing processes (A. Ing?lfsd?ttir, H. Lin).
An introduction to the pi-calculus (P. Parrow).
Verification on infinite structures (O. Burkart, D. Caucal, F. Moller, B. Steffen).
Part 4: Extensions.
Process algebra with timing: real time and discrete time (J.C.M. Baeten, C.A. Middelburg).
Probabilistic extensions of process algebras (B. Jonsson, K.G. Larsen, Wang Yi).
Priority in process algebra (R. Cleaveland, G. L?ettgen, V. Natarajan).
Part 5: Non-Interleaving Process Algebra.
Partial-order process algebra (J.C.M. Baeten, T. Basten).
A unified model for nets and process algebras (E. Best, R. Devillers, M. Koutny).
Process algebras with localities (I. Castellani).
Action refinement (R. Gorrieri, A. Rensink).
Part 6: Tools and Applications.
Algebraic process verification (J.F. Groote, M.A. Reniers).
Discrete time process algebra and the semantics of SDL (J.A. Bergstra, C.A. Middelburg, Y.S. Usenko).
A process algebra for Interworkings (S. Mauw, M.A. Reniers).
Hardbound
ISBN: 0-444-82830-3
1356 pages
G. Brady, University of Chicago,
From Peirce to Skolem
A Neglected Chapter in the History of Logic
Included in series
Studies in the History and Philosophy of Mathematics, 4
Description
This book is an account of the important influence on the development of mathematical logic of Charles S. Peirce and his student O.H. Mitchell, through the work of Ernst Schroeder, Leopold L?wenheim, and Thoralf Skolem. As far as we know, this book is the first work delineating this line of influence on modern mathematical
logic.
Contents
Introduction
The Early Work of Charles S. Peirce.
Overview of the Mathematical Systems of Charles S. Peirce.
Peirce's Influence on the Development of Logic.
Peirce's Early Approaches to Logic.
Peirce's Calculus of Relatives: 1870.
Peirce's Algebra of Relations.
Inclusion and Equality.
Addition.
Multiplication.
Peirce's First Quantifiers.
Involution.
Involution and Mixed-quantifier Forms.
Elementary Relatives.
Quantification in the calculus of relatives in 1870. Summary.
Peirce on the Algebra of Logic: 1880.
Overview of Peirce's "On the algebra of logic".
Discussion.
The Origins of Logic.
Syllogism and Illation.
Forms of Propositions.
The Algebra of the Copula.
The Logic of Nonrelative Terms.
Conclusion.
Mitchell on a New Algebra of Logic: 1883.
Mitchell's Rule of Inference.
Single-Variable Monadic Logic.
Single-Variable Monadic Propositions.
Disjunctive Normal Form.
Rules of Inference for Single-Variable Logic.
Two-Variable Monadic Logic.
Mitchell's Dimension Theory.
Contrast to Peirce.
Three-Variable Monadic Logic.
Peirce on Mitchell.
Peirce on the algebra of relatives: 1883.
Background in Linear Associative Algebras.
The Algebra of Relatives.
Types of Relatives.
Operations on Relatives.
Syllogistic in the Relative Calculus.
Prenex Predicate Calculus.
Summary of Peirce's Accomplishments in 1883. Syntax and Semantics.
Quantifiers.
Peirce's Appraisal of His Algebra of Binary Relatives.
Peirce's Logic of Quantifiers: 1885.
On the Derivation of Logic from Algebra.
Nonrelative Logic.
Embedding Boolean algebra in Ordinary Algebra.
Five Peirce Icons.
Truth-functional Interpretations of Propositions.
First-Order Logic.
Infinite Sums and Products.
Mitchell.
Formulas and Rules.
Second-Order Logic.
Schr?der's Calculus of Relatives.
Die algebra der Logik: Volume 1. Die Algebra der Logik: Volume 2. Die Algebra der Logik: Volume 3. Peirce's Attack on the General solutions of Schr?der.
Lectures VI-X and Dedekind Chain Theory.
Lectures XI-XII and Higher Order Logic.
Norbert Wiener's Ph.D. Thesis.
L?wenheim's contribution.
Overview of L?wenheim's 1915 paper.
L?wenheim's Theorem.
Conclusions.
Impact of L?wenheim's Theorem.
Conclusions.
Impact of L?wenheim's Paper.
Skolem's recasting.
Appendices.
Schroeder's Lecture I. Schroeder's Lecture II. Schroeder's Lecture III. Schroeder's Lecture V. Schroeder's Lecture IX. Schroeder's Lecture XI. Schroeder's Lecture XII.
Norbert Wiener's Thesis.
Bibliography.
Index.
Hardbound
ISBN: 0-444-50334-X
625 pages
An Essential Resource for Mathematicians
Numerical Analysis 2000
Order your 7-Volume Set now at special set price
0-444-50686-1
Descriptive text
Topics
Tables of Contents ( Volume I, II, III, IV, V, VI, VII )
Bibliographic Information
The field of numerical analysis has witnessed many significant developments in the 20th century, and will no doubt continue to see major new advances in the years ahead. As the century drew to a close, it seemed only appropriate to mark this special event by celebrating the vast accomplishments made in this field during the last 100 years.
Numerical Analysis 2000 is a unique, seven-volume set chronicling both the historical developments and recent advances in the study of numerical analysis in the 20th century.
A collaborative effort between the editors of the Journal of Computational and Applied Mathematics and of the book series Studies in Computational Mathematics, Numerical Analysis 2000 will be published as a series of seven special Volumes in the Journal of Computational and Applied Mathematics. Each Volume will provide valuable insights into a specific topic, and the historical developments in each of the subject areas will be described in special articles written by renowned mathematicians.
Survey papers and articles on recent advances will also be included, making this unique series an authoritative,
indispensable source of knowledge for the next millennium.
Each issue will also be available separately in paperback, and the historical papers will be published as a separate volume in the Studies in Computational Mathematics Book Series.
Bibliographic Information
Volume I. Approximation theory - Luc Wuytack, Jet Wimp
ISBN 0-444-50596-2
484 pages. Published.
Volume II. Interpolation and extrapolation - Claude Brezinski
ISBN 0-444-50597-0
372 pages. Published.
Volume III. Linear Algebra - Paul van Dooren, Apostolos Hadjidimos, Henk van der Vorst
ISBN 0-444-50598-9
548 pages. Published.
Volume IV. Nonlinear equations and optimisation - Mike Bartholomew-Biggs, John Ford, Layne Watson
ISBN 0-444-50599-9
392 pages. Approximate date of publication: February 2001.
Volume V. Quadrature and orthogonal polynomials - Walter Gautschi, Francisco Marcellan, Lothar Reichel
ISBN 0-444-50615-2
388 pages. Approximate date of publication: March 2001.
Volume VI. Ordinary differential and integral equations - Christopher Baker, John Pryce, Guido Van den Bergh,
Giovanni Monegato
ISBN 0-444-50600-4
588 pages. Approximate date of publication: February 2001.
Volume VII. Partial differential equations - David Sloan, Stefan Van de Walle, Endre Suli
ISBN 0-444-50616-0
482 pages. Approximate date of publication: April 2001
R. Fraesse
Theory of Relations
Included in series
Studies in Logic and the Foundations of Mathematics, 145
Description
Relation theory originates with Hausdorff (Mengenlehre 1914) and Sierpinski (Nombres transfinis, 1928) with the study of order types, specially among chains = total orders = linear orders. One of its first important problems was partially solved by Dushnik, Miller 1940 who, starting from the chain of reals, obtained an infinite strictly decreasing sequence of chains (of continuum power) with respect to embeddability. In 1948 I conjectured that every strictly decreasing sequence of denumerable chains is finite. This was affirmatively
proved by Laver (1968), in the more general case of denumerable unions of scattered chains (ie: which do not embed the chain Q of rationals), by using the barrier and the better orderin gof Nash-Williams (1965 to 68).
Another important problem is the extension to posets of classical properties of chains. For instance one easily sees that a chain A is scattered if the chain of inclusion of its initial intervals is itself scattered (6.1.4). Let us again define a scattered poset A by the non-embedding of Q in A. We say that A is finitely free if every antichain restriction of A is finite (antichain = set of mutually incomparable elements of the base). In 1969 Bonnet and Pouzet proved that a poset A is finitely free and scattered iff the ordering of inclusion of initial intervals of A is scattered. In 1981 Pouzet proved the equivalence with the a priori stronger condition that A is topologically scattered: (see 6.7.4; a more general result is due to Mislove 1984); ie: every non-empty set of initial intervals contains an isolated elements for the simple convergence topology.
In chapter 9 we begin the general theory of relations, with the notions of local isomorphism, free interpretability and free operator (9.1 to 9.3), which is the relationist version of a free logical formula. This is generalized by the back-and-forth notions in 10.10: the (k,p)-operator is the relationist version of the
elementary formula (first order formula with equality). Chapter 12 connects relation theory with permutations: theorem of the increasing number of orbits (Livingstone, Wagner in 12.4). Also in this chapter homogeneity
is introduced, then more deeply studied in the Appendix written by Norbert Saucer.
Chapter 13 connects relation theory with finite permutation groups; the main notions and results are due to Frasnay. Also mention the extension to relations of adjacent elements, by Hodges, Lachlan, Shelah who by this mean give an exact calculus of the reduction threshold. The book covers almost all present knowledge in Relation Theory, from origins (Hausdorff 1914, Sierpinski 1928) to classical results (Frasnay 1965, Laver 1968,
Pouzet 1981) until recent important publications (Abraham, Bonnet 1999). All results are exposed in axiomatic set theory. This allows us, for each statement, to specify if it is proved only from ZF axioms of choice, the continuum hypothesis or only the ultrafilter axiom or the axiom of dependent choice, for instance.
Contents
Introduction.
1. Review of axiomatic set theory, relation.
2. Coherence lemma, cofinality, tree, ideal.
3. Ramsey theorem, partition, incidence matrix.
4. Good, bad sequence, well partial ordering.
5. Embeddability between relations and chains.
6. Scattered chain, scattered poset.
7. Well quasi-ordering of scattered chains.
8. Bivalent tableau, Szpilrajn chain.
9. Free operator, chainability, strong interval.
10. Age, -morphism, back-and-forth.
11. Relative isomorphism, saturated relation.
12. Homogeneous relation, orbit.
13. Compatibility and chainability theorems.
A. On countable homogeneous systems: Sauer
Hardbound
ISBN: 0-444-50542-3
450 pages
A.T. White, Western Michigan University, Kalamazoo, MI 49008, USA
Graphs of Groups on Surfaces
Interactions and Models
Included in series
North-Holland Mathematics Studies, 188
Description
The book, suitable as both an introductory reference and as a text book in the rapidly growing field of topological graph theory, models both maps (as inb map-coloring problems) and groups by means of graph imbeddings on sufaces. Automorphism groups of both graphs and maps are studied. In addition connections
are made to other areas of mathematics, such as hypergraphs, block designs, finite geometries, and finite fields. There are chapters on the emerging subfields of enumerative topological graph theory and random topological graph theory, as well as a chapter on the composition of English church-bell music. The latter is
facilitated by imbedding the right graph of the right group on an appropriate surface, with suitable symmetries. Throughout the emphasis is on Cayley maps: imbeddings of Cayley graphs for finite groups as (possibly branched) covering projections of surface imbeddings of loop graphs with one vertex. This is not as
restrictive as it might sound; many developments in topological graph theory involve such imbeddings.
The approach aims to make all this interconnected material readily accessible to a beginning graduate (or an advanced undergraduate) student, while at the same time providing the research mathematician with a useful reference book in topological graph theory. The focus will be on beautiful connections, both elementary
and deep, within mathematics that can best be described by the intuitively pleasing device of imbedding graphs of groups on surfaces.
Hardbound
ISBN: 0-444-50075-8
364 pages