Logic plays a central conceptual role in modern mathematics. However, mathematical logic has grown into one of the most recondite areas of mathematics. As a result, most of modern logic is inaccessible to all but the specialist. This new book is a resource that provides a quick introduction and review of the key topics in logic for the computer scientist, engineer, or mathematician. Handbook of Logic and Proof Techniques for Computer Science presents the elements of modern logic, including many current topics, to the reader having only basic mathematical literacy. Computer scientists will find specific examples and important ideas such as axiomatics, recursion theory, decidability, independence, completeness, consistency, model theory, and P/NP completeness. The book contains definitions, examples and discussion of all of the key ideas in basic logic, but also makes a special effort to cut through the mathematical formalism, difficult notation, and esoteric terminology that is typical of modern mathematical logic.T This handbook delivers cogent and self-contained introductions to critical advanced topics, including: * Godel's completeness and incompleteness theorems * Methods of proof, cardinal and ordinal numbers, the continuum hypothesis, the axiom of choice, model theory, and number systems and their construction * Extensive treatment of complexity theory and programming applications * Applications to algorithms in Boolean algebra * Discussion of set theory and applications of logic The book is an excellent resource for the working mathematical scientist. The graduate student or professional in computer science and engineering or the systems scientist who needs to have a quick sketch of a key idea from logic will find it here in this self-contained, accessible, and easy-to-use reference.

On the 26th of November 1992 the organizing committee gathered together, at Luigi Salce's invitation, for the first time. The tradition of abelian groups and modules Italian conferences (Rome 77, Udine 85, Bressanone 90) needed to be kept up by one more meeting. Since that first time it was clear to us that our goal was not so easy. In fact the main intended topics of abelian groups, modules over commutative rings and non commutative rings have become so specialized in the last years that it looked really ambitious to fit them into only one meeting. Anyway, since everyone of us shared the same mathematical roots, we did want to emphasize a common link. So we elaborated the long symposium schedule: three days of abelian groups and three days of modules over non commutative rings with a two days' bridge of commutative algebra in between. Many of the most famous names in these fields took part to the meeting. Over 140 participants, both attending and contributing the 18 Main Lectures and 64 Communications (see list on page xv) provided a really wide audience for an Algebra meeting. Now that the meeting is over, we can say that our initial feeling was right.

"Categorical Perspectives" consists of introductory surveys as well as articles containing original research and complete proofs devoted mainly to the theoretical and foundational developments of category theory and its applications to other fields. A number of articles in the areas of topology, algebra and computer science reflect the varied interests of George Strecker to whom this work is dedicated. Notable also are an exposition of the contributions and importance of George Strecker's research and a survey chapter on general category theory. This work is an excellent reference text for researchers and graduate students in category theory and related areas. Contributors: H.L. Bentley * G. Castellini * R. El Bashir * H. Herrlich * M. Husek * L. Janos * J. Koslowski * V.A. Lemin * A. Melton * G. Preua * Y.T. Rhineghost * B.S.W. Schroeder * L. Schr"der * G.E. Strecker * A. Zmrzlina

As of today, Evolutionary Computing and Fuzzy Set Computing are two mature, wen -developed, and higbly advanced technologies of information processing. Bach of them has its own clearly defined research agenda, specific goals to be achieved, and a wen setUed algorithmic environment. Concisely speaking, Evolutionary Computing (EC) is aimed at a coherent population -oriented methodology of structural and parametric optimization of a diversity of systems. In addition to this broad spectrum of such optimization applications, this paradigm otTers an important ability to cope with realistic goals and design objectives reflected in the form of relevant fitness functions. The GA search (which is often regarded as a dominant domain among other techniques of EC such as evolutionary strategies, genetic programming or evolutionary programming) delivers a great deal of efficiency helping navigate through large search spaces. The main thrust of fuzzy sets is in representing and managing nonnumeric (linguistic) information. The key notion (whose conceptual as weH as algorithmic importance has started to increase in the recent years) is that of information granularity. It somewhat concurs with the principle of incompatibility coined by L. A. Zadeh. Fuzzy sets form a vehic1e helpful in expressing a granular character of information to be captured. Once quantified via fuzzy sets or fuzzy relations, the domain knowledge could be used efficiently very often reducing a heavy computation burden when analyzing and optimizing complex systems.

This volume contains papers which are based primarily on talks given at an inter national conference on Algorithmic Problems in Groups and Semigroups held at the University of Nebraska-Lincoln from May ll-May 16, 1998. The conference coincided with the Centennial Celebration of the Department of Mathematics and Statistics at the University of Nebraska-Lincoln on the occasion of the one hun dredth anniversary of the granting of the first Ph.D. by the department. Funding was provided by the US National Science Foundation, the Department of Math ematics and Statistics, and the College of Arts and Sciences at the University of Nebraska-Lincoln, through the College's focus program in Discrete, Experimental and Applied Mathematics. The purpose of the conference was to bring together researchers with interests in algorithmic problems in group theory, semigroup theory and computer science. A particularly useful feature of this conference was that it provided a framework for exchange of ideas between the research communities in semigroup theory and group theory, and several of the papers collected here reflect this interac tion of ideas. The papers collected in this volume represent a cross section of some of the results and ideas that were discussed in the conference. They reflect a synthesis of overlapping ideas and techniques stimulated by problems concerning finite monoids, finitely presented mono ids, finitely presented groups and free groups.

This monograph treats the theory of Dirichlet forms from a comprehensive point of view, using "nonstandard analysis." Thus, it is close in spirit to the discrete classical formulation of Dirichlet space theory by Beurling and Deny (1958). The discrete infinitesimal setup makes it possible to study the diffusion and the jump part using essentially the same methods. This setting has the advantage of being independent of special topological properties of the state space and in this sense is a natural one, valid for both finite- and infinite-dimensional spaces.
The present monograph provides a thorough treatment of the symmetric as well as the non-symmetric case, surveys the theory of hyperfinite Levy processes, and summarizes in an epilogue the model-theoretic genericity of hyperfinite stochastic processes theory.

Translated from the French, this book is an introduction to first-order model theory. Starting from scratch, it quickly reaches the essentials, namely, the back-and-forth method and compactness, which are illustrated with examples taken from algebra. It also introduces logic via the study of the models of arithmetic, and it gives complete but accessible exposition of stability theory.

Aggregation plays a central role in many of the technological tasks we are faced with. The importance of this process will become even greater as we move more and more toward becoming an information-cent.ered society, us is happening with the rapid growth of the Internet and the World Wirle Weh. Here we shall be faced with many issues related to the fusion of information. One very pressing issue here is the development of mechanisms to help search for information, a problem that clearly has a strong aggregation-related component. More generally, in order to model the sophisticated ways in which human beings process information, as well as going beyond the human capa bilities, we need provide a basket of aggregation tools. The centrality of aggregation in human thought can be be very clearly seen by looking at neural networks, a technology motivated by modeling the human brain. One can see that the basic operations involved in these networks are learning and aggregation. The Ordered Weighted Averaging (OWA) operators provide a parameter ized family of aggregation operators which include many of the well-known operators such as the maximum, minimum and the simple average."

Mathematical Principles of Fuzzy Logic provides a systematic study of the formal theory of fuzzy logic. The book is based on logical formalism demonstrating that fuzzy logic is a well-developed logical theory. It includes the theory of functional systems in fuzzy logic, providing an explanation of what can be represented, and how, by formulas of fuzzy logic calculi. It also presents a more general interpretation of fuzzy logic within the environment of other proper categories of fuzzy sets stemming either from the topos theory, or even generalizing the latter. This book presents fuzzy logic as the mathematical theory of vagueness as well as the theory of commonsense human reasoning, based on the use of natural language, the distinguishing feature of which is the vagueness of its semantics.

3. Textbook for a course in expert systems, if an emphasis is placed on Chapters 1 to 3 and on a selection of material from Chapters 4 to 7. There is also the option of using an additional commercially available sheU for a programming project. In assigning a programming project, the instructor may use any part of a great variety of books covering many subjects, such as car repair. Instructions for mostofthe "weekend mechanic" books are close stylisticaUy to expert system rules. Contents Chapter 1 gives an introduction to the subject matter; it briefly presents basic concepts, history, and some perspectives ofexpert systems. Then itpresents the architecture of an expert system and explains the stages of building an expert system. The concept of uncertainty in expert systems and the necessity of deal ing with the phenomenon are then presented. The chapter ends with the descrip tion of taxonomy ofexpert systems. Chapter 2 focuses on knowledge representation. Four basic ways to repre sent knowledge in expert systems are presented: first-order logic, production sys tems, semantic nets, and frames. Chapter 3 contains material about knowledge acquisition. Among machine learning techniques, a methodofrule learning from examples is explained in de tail. Then problems ofrule-base verification are discussed. In particular, both consistency and completeness oftherule base are presented."

The KK-theory of Kasparov is now approximately twelve years old; its power, utility and importance have been amply demonstrated. Nonethe less, it remains a forbiddingly difficult topic with which to work and learn. There are many reasons for this. For one thing, KK-theory spans several traditionally disparate mathematical regimes. For another, the literature is scattered and difficult to penetrate. Many of the major papers require the reader to supply the details of the arguments based on only a rough outline of proofs. Finally, the subject itself has come to consist of a number of difficult segments, each of which demands prolonged and intensive study. is to deal with some of these difficul Our goal in writing this book ties and make it possible for the reader to "get started" with the theory. We have not attempted to produce a comprehensive treatise on all aspects of KK-theory; the subject seems too vital to submit to such a treatment at this point. What seemed more important to us was a timely presen tation of the very basic elements of the theory, the functoriality of the KK-groups, and the Kasparov product."

Primarily consisting of talks presented at a workshop at the MSRI during its "Logic Year" 1989-90, this volume is intended to reflect the whole spectrum of activities in set theory. The first section of the book comprises the invited papers surveying the state of the art in a wide range of topics of set-theoretic research. The second section includes research papers on various aspects of set theory and its relation to algebra and topology. Contributors include: J.Bagaria, T. Bartoszynski, H. Becker, P. Dehornoy, Q. Feng, M. Foreman, M. Gitik, L. Harrington, S. Jackson, H. Judah, W. Just, A.S. Kechris, A. Louveau, S. MacLane, M. Magidor, A.R.D. Mathias, G. Melles, W.J. Mitchell, S. Shelah, R.A. Shore, R.I. Soare, L.J. Stanley, B. Velikovic, H. Woodin

In 1963, the first author introduced a course in set theory at the University of Illinois whose main objectives were to cover Godel's work on the con sistency of the Axiom of Choice (AC) and the Generalized Continuum Hypothesis (GCH), and Cohen's work on the independence of the AC and the GCH. Notes taken in 1963 by the second author were taught by him in 1966, revised extensively, and are presented here as an introduction to axiomatic set theory. Texts in set theory frequently develop the subject rapidly moving from key result to key result and suppressing many details. Advocates of the fast development claim at least two advantages. First, key results are high lighted, and second, the student who wishes to master the subject is com pelled to develop the detail on his own. However, an instructor using a "fast development" text must devote much class time to assisting his students in their efforts to bridge gaps in the text."

Semiring theory stands with a foot in each of two mathematical domains. The first being abstract algebra and the other the fields of applied mathematics such as optimization theory, the theory of discrete-event dynamical systems, automata theory, and formal language theory, as well as from the allied areas of theoretical computer science and theoretical physics. Most important applications of semiring theory in these areas turn out to revolve around the problem of finding the equalizer of a pair of affine maps between two semimodules. In this volume, we chart the state of the art on solving this problem, and present many specific cases of applications.

This book is essentially the third part of a trilogy, along with Semirings and their Applications, and Power Algebras over Semirings, both written by the same author and published by Kluwer Academic Publishers in 1999. While each book can be read independently of the others, to get the full force of the theory and applications one should have access to all three.

This work will be of interest to academic and industrial researchers and graduate students. The intent of the book is to bring the applications to the attention of the abstract mathematicians and to make the abstract mathematics available to those who are using these tools in an ad-hoc manner without realizing the full force of the theory.

The modern discussion on the concept of truthlikeness was started in 1960. In his influential Word and Object, W. V. O. Quine argued that Charles Peirce's definition of truth as the limit of inquiry is faulty for the reason that the notion 'nearer than' is only "defined for numbers and not for theories." In his contribution to the 1960 International Congress for Logic, Methodology, and Philosophy of Science at Stan ford, Karl Popper defended the opposite view by defining a compara tive notion of verisimilitude for theories. was originally introduced by the The concept of verisimilitude Ancient sceptics to moderate their radical thesis of the inaccessibility of truth. But soon verisimilitudo, indicating likeness to the truth, was confused with probabilitas, which expresses an opiniotative attitude weaker than full certainty. The idea of truthlikeness fell in disrepute also as a result of the careless, often confused and metaphysically loaded way in which many philosophers used - and still use - such concepts as 'degree of truth', 'approximate truth', 'partial truth', and 'approach to the truth'. Popper's great achievement was his insight that the criticism against truthlikeness - by those who urge that it is meaningless to speak about 'closeness to truth' - is more based on prejudice than argument."

Relational methods can be found at various places in computer science, notably in data base theory, relational semantics of concurrency, relationaltype theory, analysis of rewriting systems, and modern programming language design. In addition, they appear in algorithms analysis and in the bulk of discrete mathematics taught to computer scientists. This book is devoted to the background of these methods. It explains how to use relational and graph-theoretic methods systematically in computer science. A powerful formal framework of relational algebra is developed with respect to applications to a diverse range of problem areas. Results are first motivated by practical examples, often visualized by both Boolean 0-1-matrices and graphs, and then derived algebraically.

The first of a two volume set showcasing current research in model theory and its connections with number theory, algebraic geometry, real analytic geometry and differential algebra. Each volume contains a series of expository essays and research papers around the subject matter of a Newton Institute Semester on Model Theory and Applications to Algebra and Analysis. The articles convey outstanding new research on topics such as model theory and conjectures around Mordell-Lang; arithmetic of differential equations, and Galois theory of difference equations; model theory and complex analytic geometry; o-minimality; model theory and noncommutative geometry; definable groups of finite dimension; Hilbert's tenth problem; and Hrushovski constructions. With contributions from so many leaders in the field, this book will undoubtedly appeal to all mathematicians with an interest in model theory and its applications, from graduate students to senior researchers and from beginners to experts.

The second of a two volume set showcasing current research in model theory and its connections with number theory, algebraic geometry, real analytic geometry and differential algebra. Each volume contains a series of expository essays and research papers around the subject matter of a Newton Institute Semester on Model Theory and Applications to Algebra and Analysis. The articles convey outstanding new research on topics such as model theory and conjectures around Mordell-Lang; arithmetic of differential equations, and Galois theory of difference equations; model theory and complex analytic geometry; o-minimality; model theory and non-commutative geometry; definable groups of finite dimension; Hilbert's tenth problem; and Hrushovski constructions. With contributions from so many leaders in the field, this book will undoubtedly appeal to all mathematicians with an interest in model theory and its applications, from graduate students to senior researchers and from beginners to experts.

This is a motivated presentation of recent results on tree transducers, applied to studying the general properties of formal models and for providing semantics to context-free languages. The authors consider top-down tree transducers, macro tree transducers, attributed tree transducers, and macro attributed tree transducers. A unified terminology is used to define them, and their transformational capacities are compared. This handbook on tree transducers will serve as a base for further research.

One of the most remarkable recent occurrences in mathematics is the re-founding, on a rigorous basis, the idea of infinitesimal quantity, a notion which played an important role in the early development of the calculus and mathematical analysis. In this new and updated edition, basic calculus, together with some of its applications to simple physical problems, are presented through the use of a straightforward, rigorous, axiomatically formulated concept of 'zero-square', or 'nilpotent' infinitesimal - that is, a quantity so small that its square and all higher powers can be set, to zero. The systematic employment of these infinitesimals reduces the differential calculus to simple algebra and, at the same time, restores to use the "infinitesimal" methods figuring in traditional applications of the calculus to physical problems - a number of which are discussed in this book. This edition also contains an expanded historical and philosophical introduction.

Now approaching its tenth year, this hugely successful book presents an unusual attempt to publicise the field of Complex Dynamics. The text was originally conceived as a supplemented catalogue to the exhibition "Frontiers of Chaos," seen in Europe and the United States, and describes the context and meaning of these fascinating images. A total of 184 illustrations - including 88 full-colour pictures of Julia sets - are suggestive of a coffee-table book.
However, the invited contributions which round off the book lend the text the required formality. Benoit Mandelbrot gives a very personal account, in his idiosyncratic self-centred style, of his discovery of the fractals named after him and Adrien Douady explains the solved and unsolved problems relating to this amusingly complex set.

J. Richard Biichi is well known for his work in mathematical logic and theoretical computer science. (He himself would have sharply objected to the qualifier "theoretical," because he more or less identified science and theory, using "theory" in a broader sense and "science" in a narrower sense than usual.) We are happy to present here this collection of his papers. I (DS)1 worked with Biichi for many years, on and off, ever since I did my Ph.D. thesis on his Sequential Calculus. His way was to travel locally, not globally: When we met we would try some specific problem, but rarely dis cussed research we had done or might do. After he died in April 1984 I sifted through the manuscripts and notes left behind and was dumbfounded to see what areas he had been in. Essentially I knew about his work in finite au tomata, monadic second-order theories, and computability. But here were at least four layers on his writing desk, and evidently he had been working on them all in parallel. I am sure that many people who knew Biichi would tell an analogous story."

Approach your problems from the right end It isn't that they can't see the solution. It is and begin with the answers. Then one day, that they can't see the problem. perhaps you will find the final question. G. K. Chesterton. The Scandal of Father 'The Hermit Gad in Crane Feathers' in R. Brown'The point of a Pin'. van Gulik's TheChinese Maze Murders. Growing specialization and diversification have brought a host of monographs and textbooks on increasingly specialized topics. However, the "tree" of knowledge of mathematics and related fields does not grow only by putting forth new branches. It also happens, quite often in fact, that branches which were thought to be completely disparate are suddenly seen to be related. Further, the kind and level of sophistication of mathematics applied in various sciences has changed drastically in recent years: measure theory is used (non-trivially) in regional and theoretical economics; algebraic geometry interacts with physics; the Minkowsky lemma, coding theory and the structure of water meet one another in packing and covering theory; quantum fields, crystal defects and mathematical programming profit from homotopy theory; Lie algebras are relevant to filtering; and prediction and electrical engineering can use Stein spaces. And in addition to this there are such new emerging SUbdisciplines as "experimental mathematics," "CFD," "completely integrable systems," "chaos, synergetics and large-scale order," which are almost impossible to fit into the existing classification schemes. They draw upon widely different sections of mathematics.

Approach your problems from the right end It isn't that they can't see the solution. It is and begin with the answers. Then one day, that they can't see the problem. perhaps you will tind the tinal question. G. K. Chesterton. The Scandal of Father Brown 'The point of a Pin'. 'The Hermit CIad in Crane Feathers' in R. van Gulik's The Chinese Maze Murders. Growing specialization and diversification have brought a host of monographs and textbooks on increasingly specialized topics. However, the "tree" of knowledge of mathematics and related fields does not grow only by putting forth new branches. It also happens, quite of ten in fact, that branches which were thought to be completely disparate are suddenly seen to be related. Further, the kind and level of sophistication of mathematics applied in various sciences has changed drastically in recent years: measure theory is used (non-trivially) in regional and theoretical economics; algebraic geometry interacts with physics; the Minkowsky lemma, coding theory and the structure of water meet one another in packing and covering theory; quantum fields, crystal defects and mathematical programming profit from homotopy theory; Lie algebras are relevant to fiItering; and prediction and electrical engineering can use Stein spaces. And in addition to this there are such new emerging subdisciplines as "experimental mathematics," "CFD," "completely integrable systems," "chaos, synergetics and large-scale order," which are almost impossible to fit into the existing classification schemes. They draw upon widely different sections of mathematics.

This volume presents a unified approach to the mathematical theory of a wide class of non-additive set functions, the so called null-additive set functions, which also includes classical measure theory. It includes such important set functions as capacities, triangular set functions, some fuzzy measures, submeasures, decomposable measures, possibility measures, distorted probabilities, autocontinuous set functions, etc. The usefulness of the theory is demonstrated by applications in nonlinear differential and difference equations; fractal geometry in the theory of chaos; the approximation of functions in modular spaces by nonlinear singular integral operators; and in the theory of diagonal theorems as a universal method for proving general and fundamental theorems in functional analysis and measure theory. Audience: This book will be of value to researchers and postgraduate students in mathematics, as well as in such diverse fields as knowledge engineering, artificial intelligence, game theory, statistics, economics, sociology and industry.