A practical introduction to the development of proofs and certified programs using Coq.

An invaluable tool for researchers, students, and engineers interested in formal methods and the development of zero-fault software.

Assessing the degree to which two objects, an object and a query, or two concepts are similar or compatible is a fundamental component of human reasoning and consequently is critical in the development of automated diagnosis, classification, information retrieval and decision systems. The assessment of similarity has played an important role in such diverse disciplines such as taxonomy, psychology, and the social sciences. Each discipline has proposed methods for quantifying similarity judgments suitable for its particular applications. This book presents a unified approach to quantifying similarity and compatibility within the framework of fuzzy set theory and examines the primary importance of these concepts in approximate reasoning. Examples of the application of similarity measures in various areas including expert systems, information retrieval, and intelligent database systems are provided.

Henkin-Keisler models emanate from a modification of the Henkin construction introduced by Keisler to motivate the definition of ultraproducts. Keisler modified the Henkin construction at that point at which `new' individual constants are introduced and did so in a way that illuminates a connection between Henkin-Keisler models and ultraproducts. The resulting construction can be viewed both as a specialization of the Henkin construction and as an alternative to the ultraproduct construction. These aspects of the Henkin-Keisler construction are utilized here to present a perspective on ultraproducts and their applications accessible to the reader familiar with Henkin's proof of the completeness of first order logic and naive set theory. This approach culminates in proofs of various forms of the Keisler-Shelah characterizations of elementary equivalence and elementary classes via Henkin-Keisler models. The presentation is self-contained and proofs of more advanced results from set theory are introduced as needed. Audience: Logicians in philosophy, computer science, linguistics and mathematics.

The theory of quasivarieties constitutes an independent direction in algebra and mathematical logic and specializes in a fragment of first-order logic-the so-called universal Horn logic. This treatise uniformly presents the principal directions of the theory from an effective algebraic approach developed by the author himself. A revolutionary exposition, this influential text contains a number of results never before published in book form, featuring in-depth commentary for applications of quasivarieties to graphs, convex geometries, and formal languages. Key features include coverage of the Birkhoff-Mal'tsev problem on the structure of lattices of quasivarieties, helpful exercises, and an extensive list of references.

This book contains the lectures given at the NATO ASI 910820 "Cellular Automata and Cooperative Systems" Meeting which was held at the Centre de Physique des Houches, France, from June 22 to July 2, 1992. This workshop brought together mathematical physicists, theoretical physicists and mathe maticians working in fields related to local interacting systems, cellular and probabilistic automata, statistical physics, and complexity theory, as well as applications of these fields. We would like to thank our sponsors and supporters whose interest and help was essential for the success of the meeting: the NATO Scientific Affairs Division, the DRET (Direction des Recherches, Etudes et Techniques), the Ministere des Affaires Etrangeres, the National Science Foundation. We would also like to thank all the secretaries who helped us during the preparation of the meeting, in particular Maryse Cohen-Solal (CPT, Marseille) and Janice Nowinski (Courant Institute, New York). We are grateful for the fine work of Mrs. Gladys Cavallone in preparing this volume."

This volume presents the results of approximately 15 years of work from researchers around the world on the use of fuzzy set theory to represent imprecision in databases. The maturity of the research in the discipline and the recent developments in commercial/industrial fuzzy databases provided an opportunity to produce this survey. Fuzzy Databases: Principles and Applications is self-contained providing background material on fuzzy sets and database theory. It is comprehensive covering all of the major approaches and models of fuzzy databases that have been developed including coverage of commercial/industrial systems and applications. Background and introductory material are provided in the first two chapters. The major approaches in fuzzy databases comprise the second part of the volume. This includes the use of similarity and proximity measures as the fuzzy techniques used to extend the relational data modeling and the use of possibility theory approaches in the relational model. Coverage includes extensions to the data model, querying approaches, functional dependencies and other topics including implementation issues, information measures, database security, alternative fuzzy data models, the IFO model, and the network data models. A number of object-oriented extensions are also discussed. The use of fuzzy data modeling in geographical information systems (GIS) and use of rough sets in rough and fuzzy rough relational data models are presented. Major emphasis has been given to applications and commercialization of fuzzy databases. Several specific industrial/commercial products and applications are described. These include approaches to developing fuzzy front-end systems andspecial-purpose systems incorporating fuzziness.

A partially ordered group is an algebraic object having the structure of a group and the structure of a partially ordered set which are connected in some natural way. These connections were established in the period between the end of 19th and beginning of 20th century. It was realized that ordered algebraic systems occur in various branches of mathemat ics bound up with its fundamentals. For example, the classification of infinitesimals resulted in discovery of non-archimedean ordered al gebraic systems, the formalization of the notion of real number led to the definition of ordered groups and ordered fields, the construc tion of non-archimedean geometries brought about the investigation of non-archimedean ordered groups and fields. The theory of partially ordered groups was developed by: R. Dedekind, a. Holder, D. Gilbert, B. Neumann, A. I. Mal'cev, P. Hall, G. Birkhoff. These connections between partial order and group operations allow us to investigate the properties of partially ordered groups. For exam ple, partially ordered groups with interpolation property were intro duced in F. Riesz's fundamental paper 1] as a key to his investigations of partially ordered real vector spaces, and the study of ordered vector spaces with interpolation properties were continued by many functional analysts since. The deepest and most developed part of the theory of partially ordered groups is the theory of lattice-ordered groups. In the 40s, following the publications of the works by G. Birkhoff, H. Nakano and P."

Belief change is an emerging field of artificial intelligence and information science dedicated to the dynamics of information and the present book provides a state-of-the-art picture of its formal foundations. It deals with the addition, deletion and combination of pieces of information and, more generally, with the revision, updating and fusion of knowledge bases. The book offers an extensive coverage of, and seeks to reconcile, two traditions in the kinematics of belief that often ignore each other - the symbolic and the numerical (often probabilistic) approaches. Moreover, the work encompasses both revision and fusion problems, even though these two are also commonly investigated by different communities. Finally, the book presents the numerical view of belief change, beyond the probabilistic framework, covering such approaches as possibility theory, belief functions and convex gambles. The work thus presents a unified view of belief change operators, drawing from a widely scattered literature embracing philosophical logic, artificial intelligence, uncertainty modelling and database systems. The material is a clearly organised guide to the literature on the dynamics of epistemic states, knowledge bases and uncertain information, suitable for scholars and graduate students familiar with applied logic, knowledge representation and uncertain reasoning.

The book aims at surveying results in the application of fuzzy sets and fuzzy logic to economics and engineering. New results include fuzzy non-linear regression, fully fuzzified linear programming, fuzzy multi-period control, fuzzy network analysis, each using an evolutionary algorithm; fuzzy queuing decision analysis using possibility theory; fuzzy differential equations; fuzzy difference equations; fuzzy partial differential equations; fuzzy eigenvalues based on an evolutionary algorithm; fuzzy hierarchical analysis using an evolutionary algorithm; fuzzy integral equations. Other important topics covered are fuzzy input-output analysis; fuzzy mathematics of finance; fuzzy PERT (project evaluation and review technique). No previous knowledge of fuzzy sets is needed. The mathematical background is assumed to be elementary calculus.

This self-contained title demonstrates an important interplay between abstract and concrete operator theory. Key ideas are developed in a step-by-step approach, beginning with required background and historical material, and culminating in the final chapters with state-of-the-art topics. Good examples, bibliography and index make this text a valuable classroom or reference resource.

The IOth International Congress of Logic, Methodology and Philosophy of Science, which took place in Florence in August 1995, offered a vivid and comprehensive picture of the present state of research in all directions of Logic and Philosophy of Science. The final program counted 51 invited lectures and around 700 contributed papers, distributed in 15 sections. Following the tradition of previous LMPS-meetings, some authors, whose papers aroused particular interest, were invited to submit their works for publication in a collection of selected contributed papers. Due to the large number of interesting contributions, it was decided to split the collection into two distinct volumes: one covering the areas of Logic, Foundations of Mathematics and Computer Science, the other focusing on the general Philosophy of Science and the Foundations of Physics. As a leading choice criterion for the present volume, we tried to combine papers containing relevant technical results in pure and applied logic with papers devoted to conceptual analyses, deeply rooted in advanced present-day research. After all, we believe this is part of the genuine spirit underlying the whole enterprise of LMPS studies."

This is the only monograph devoted to the expressibility of finitely axiomatizable theories, a classical subject in mathematical logic. The volume summarizes investigations in the field that have led to much of the current progress, treating systematically all positive results concerning expressibility. Also included in this unique text are solutions to both the Vaught-Morely problem and the Hanf problem, and a number of new natural questions that provide prospects for further development of the theory.

The parametric lambda calculus is a metamodel for reasoning about various kinds of computations. Its syntactic definition is based on the notion of "sets of input values," and different lambda calculi can be obtained from it by instantiating such sets in suitable ways.

The parametric lambda calculus is used as a tool for presenting in a uniform way basic notions of programming languages, and for studying with a uniform approach some lambda calculi modeling different kinds of computations, such as call-by-name, both in its lazy and non-lazy versions, and call-by-value. The parametric presentation allows us both to prove in one step all the fundamental properties of different calculi, and to compare them with each other.

The book includes some classical results in the field of lambda calculi, but completely rephrased using the parametric approach, together with some new results. The lambda calculi are presented from a computer science viewpoint, with particular emphasis on their semantics, both operational and denotational.

This book is dedicated to researchers, and can be used as a textbook for masters or Ph.D. courses on the foundations of computer science.

In opposition to the classical set theory of natural language, Nov k's highly original monograph offers a theory based on alternative and fuzzy sets. This new approach is firmly grounded in semantics and pragmatics, and accounts for the vagueness inherent in natural language-filling a large gap in our current knowledge. The theory will foster fruitful debate among researchers in linguistics and artificial intellegence.

The explanation of the formal duality of Kerdock and Preparata codes is one of the outstanding results in the field of applied algebra in the last few years. This result is related to the discovery of large sets of quad riphase sequences over Z4 whose correlation properties are better than those of the best binary sequences. Moreover, the correlation properties of sequences are closely related to difference properties of certain sets in (cyclic) groups. It is the purpose of this book to illustrate the connection between these three topics. Most articles grew out of lectures given at the NATO Ad vanced Study Institute on "Difference sets, sequences and their correlation properties." This workshop took place in Bad Windsheim (Germany) in August 1998. The editors thank the NATO Scientific Affairs Division for the generous support of this workshop. Without this support, the present collection of articles would not have been realized."

The popular literature on mathematical logic is rather extensive and written for the most varied categories of readers. College students or adults who read it in their free time may find here a vast number of thought-provoking logical problems. The reader who wishes to enrich his mathematical background in the hope that this will help him in his everyday life can discover detailed descriptions of practical (and quite often -- not so practical ) applications of logic. The large number of popular books on logic has given rise to the hope that by applying mathematical logic, students will finally learn how to distinguish between necessary and sufficient conditions and other points of logic in the college course in mathematics. But the habit of teachers of mathematical analysis, for example, to stick to problems dealing with sequences without limit, uniformly continuous functions, etc. has, unfortunately, led to the writing of textbooks that present prescriptions for the mechanical construction of definitions of negative concepts which seem to obviate the need for any thinking on the reader's part. We are most certainly not able to enumerate everything the reader may draw out of existing books on mathematical logic, however.

Starting at the very beginning with Aristotle's founding contributions, logic has been graced by several periods in which the subject has flourished, attaining standards of rigour and conceptual sophistication underpinning a large and deserved reputation as a leading expression of human intellectual effort. It is widely recognized that the period from the mid-19th century until the three-quarter mark of the century just past marked one of these golden ages, a period of explosive creativity and transforming insights. It has been said that ignorance of our history is a kind of amnesia, concerning which it is wise to note that amnesia is an illness. It would be a matter for regret, if we lost contact with another of logic's golden ages, one that greatly exceeds in reach that enjoyed by mathematical symbolic logic. This is the period between the 11th and 16th centuries, loosely conceived of as the Middle Ages. The logic of this period does not have the expressive virtues afforded by the symbolic resources of uninterpreted calculi, but mediaeval logic rivals in range, originality and intellectual robustness a good deal of the modern record. The range of logic in this period is striking, extending from investigation of quantifiers and logic consequence to inquiries into logical truth; from theories of reference to accounts of identity; from work on the modalities to the stirrings of the logic of relations, from theories of meaning to analyses of the paradoxes, and more. While the scope of mediaeval logic is impressive, of greater importance is that nearly all of it can be read by the modern logician with at least some prospect of profit. The last thing that mediaeval logic is, is a museum piece.
"Mediaeval and Renaissance Logic" is an indispensable research tool for anyone interested in the development of logic, including researchers, graduate and senior undergraduate students in logic, history of logic, mathematics, history of mathematics, computer science and AI, linguistics, cognitive science, argumentation theory, philosophy, and the history of ideas.
- Provides detailed and comprehensive chapters covering the entire range of modal logic
- Contains the latest scholarly discoveries and interpretative insights that answer many questions in the field of logic

In decision theory there are basically two appr hes to the modeling of individual choice: one is based on an absolute representation of preferences leading to a ntDnerical expression of preference intensity. This is utility theory. Another approach is based on binary relations that encode pairwise preference. While the former has mainly blossomed in the Anglo-Saxon academic world, the latter is mostly advocated in continental Europe, including Russia. The advantage of the utility theory approach is that it integrates uncertainty about the state of nature, that may affect the consequences of decision. Then, the problems of choice and ranking from the knowledge of preferences become trivial once the utility function is known. In the case of the relational approach, the model does not explicitly accounts for uncertainty, hence it looks less sophisticated. On the other hand it is more descriptive than normative in the first stand because it takes the pairwise preference pattern expressed by the decision-maker as it is and tries to make the best out of it. Especially the preference relation is not supposed to have any property. The main problem with the utility theory approach is the gap between what decision-makers are and can express, and what the theory would like them to be and to be capable of expressing. With the relational approach this gap does not exist, but the main difficulty is now to build up convincing choice rules and ranking rules that may help the decision process.

This book is concerned with cardinal number valued functions defined for any Boolean algebra. Examples of such functions are independence, which assigns to each Boolean algebra the supremum of the cardinalities of its free subalgebras, and cellularity, which gives the supremum of cardinalities of sets of pairwise disjoint elements. Twenty-one such functions are studied in detail, and many more in passing. The questions considered are the behaviour of these functions under algebraic operations such as products, free products, ultraproducts, and their relationships to one another. Assuming familiarity with only the basics of Boolean algebras and set theory, through simple infinite combinatorics and forcing, the book reviews current knowledge about these functions, giving complete proofs for most facts. A special feature of the book is the attention given to open problems, of which 185 are formulated. Based on Cardinal Functions on Boolean Algebras (1990) and Cardinal Invariants on Boolean Algebras (1996) by the same author, the present work is much larger than either of these. It contains solutions to many of the open problems of the earlier volumes. Among the new topics are continuum cardinals on Boolean algebras, with a lengthy treatment of the reaping number. Diagrams at the end of the book summarize the relationships between the functions for many important classes of Boolean algebras, including interval algebras, tree algebras and superatomic algebras.

This book describes the latest Russian research covering the structure and algorithmic properties of Boolean algebras from the algebraic and model-theoretic points of view. A significantly revised version of the author's Countable Boolean Algebras (Nauka, Novosibirsk, 1989), the text presents new results as well as a selection of open questions on Boolean algebras. Other current features include discussions of the Kottonen algebras in enrichments by ideals and automorphisms, and the properties of the automorphism groups.

Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications focuses on discrete mathematics and combinatorial algorithms interacting with real world problems in computer science, operations research, applied mathematics and engineering. The book contains eleven chapters written by experts in their respective fields, and covers a wide spectrum of high-interest problems across these discipline domains. Among the contributing authors are Richard Karp of UC Berkeley and Robert Tarjan of Princeton; both are at the pinnacle of research scholarship in Graph Theory and Combinatorics. The chapters from the contributing authors focus on "real world" applications, all of which will be of considerable interest across the areas of Operations Research, Computer Science, Applied Mathematics, and Engineering. These problems include Internet congestion control, high-speed communication networks, multi-object auctions, resource allocation, software testing, data structures, etc. In sum, this is a book focused on major, contemporary problems, written by the top research scholars in the field, using cutting-edge mathematical and computational techniques.

The book is an authoritative and up-to-date introduction to the field of analysis and potential theory dealing with the distribution zeros of classical systems of polynomials such as orthogonal polynomials, Chebyshev, Fekete and Bieberbach polynomials, best or near-best approximating polynomials on compact sets and on the real line. The main feature of the book is the combination of potential theory with conformal invariants, such as module of a family of curves and harmonic measure, to derive discrepancy estimates for signed measures if bounds for their logarithmic potentials or energy integrals are known a priori.

Mathematical Problems from Applied Logic II presents chapters from selected, world renowned, logicians. Important topics of logic are discussed from the point of view of their further development in light of requirements arising from their successful application in areas such as Computer Science and AI language. Fields covered include: logic of provability, applications of computability theory to biology, psychology, physics, chemistry, economics, and other basic sciences; computability theory and computable models; logic and space-time geometry; hybrid systems; logic and region-based theory of space.