This is an overview of the current state of knowledge along with open problems and perspectives, clarified in such fields as non-standard inferences in description logics, logic of provability, logical dynamics and computability theory. The book includes contributions concerning the role of logic today, including unexpected aspects of contemporary logic and the application of logic. This book will be of interest to logicians and mathematicians in general.

This is the first treatment in book format of proof-theoretic transformations - known as proof interpretations - that focuses on applications to ordinary mathematics. It covers both the necessary logical machinery behind the proof interpretations that are used in recent applications as well as - via extended case studies - carrying out some of these applications in full detail. This subject has historical roots in the 1950s. This book for the first time tells the whole story.

This book is an example of fruitful interaction between (non-classical) propo sitionallogics and (classical) model theory which was made possible due to categorical logic. Its main aim consists in investigating the existence of model completions for equational theories arising from propositional logics (such as the theory of Heyting algebras and various kinds of theories related to proposi tional modal logic ). The existence of model-completions turns out to be related to proof-theoretic facts concerning interpretability of second order propositional logic into ordinary propositional logic through the so-called 'Pitts' quantifiers' or 'bisimulation quantifiers'. On the other hand, the book develops a large number of topics concerning the categorical structure of finitely presented al gebras, with related applications to propositional logics, both standard (like Beth's theorems) and new (like effectiveness of internal equivalence relations, projectivity and definability of dual connectives such as difference). A special emphasis is put on sheaf representation, showing that much of the nice categor ical structure of finitely presented algebras is in fact only a restriction of natural structure in sheaves. Applications to the theory of classifying toposes are also covered, yielding new examples. The book has to be considered mainly as a research book, reporting recent and often completely new results in the field; we believe it can also be fruitfully used as a complementary book for graduate courses in categorical and algebraic logic, universal algebra, model theory, and non-classical logics. 1."

Based on several recent courses given to mathematical physics students, this volume is an introduction to bundle theory. It aims to provide newcomers to the field with solid foundations in topological K-theory. A fundamental theme, emphasized in the book, centers around the gluing of local bundle data related to bundles into a global object. One renewed motivation for studying this subject, comes from quantum field theory, where topological invariants play an important role.

The theory of Boolean algebras was created in 1847 by the English mat- matician George Boole. He conceived it as a calculus (or arithmetic) suitable for a mathematical analysis of logic. The form of his calculus was rather di?erent from the modern version, which came into being during the - riod 1864-1895 through the contributions of William Stanley Jevons, Aug- tus De Morgan, Charles Sanders Peirce, and Ernst Schr. oder. A foundation of the calculus as an abstract algebraic discipline, axiomatized by a set of equations, and admitting many di?erent interpretations, was carried out by Edward Huntington in 1904. Only with the work of Marshall Stone and Alfred Tarski in the 1930s, however, did Boolean algebra free itself completely from the bonds of logic and become a modern mathematical discipline, with deep theorems and - portantconnections toseveral otherbranchesofmathematics, includingal- bra,analysis, logic, measuretheory, probability andstatistics, settheory, and topology. For instance, in logic, beyond its close connection to propositional logic, Boolean algebra has found applications in such diverse areas as the proof of the completeness theorem for ?rst-order logic, the proof of the Lo ' s conjecture for countable ? rst-order theories categorical in power, and proofs of the independence of the axiom of choice and the continuum hypothesis ? in set theory. In analysis, Stone's discoveries of the Stone-Cech compac- ?cation and the Stone-Weierstrass approximation theorem were intimately connected to his study of Boolean algebras.

The present anthology has its origin in two international conferences that were arranged at Uppsala University in August 2004: "Logicism, Intuitionism and F- malism: What has become of them?" followed by "Symposium on Constructive Mathematics." The rst conference concerned the three major programmes in the foundations of mathematics during the classical period from Frege's Begrif- schrift in 1879 to the publication of Godel' ] s two incompleteness theorems in 1931: The logicism of Frege, Russell and Whitehead, the intuitionism of Brouwer, and Hilbert's formalist and proof-theoretic programme. The main purpose of the conf- ence was to assess the relevance of these foundational programmes to contemporary philosophy of mathematics. The second conference was announced as a satellite event to the rst, and was speci cally concerned with constructive mathematics-an activebranchofmathematicswheremathematicalstatements-existencestatements in particular-are interpreted in terms of what can be effectively constructed. C- structive mathematics may also be characterized as mathematics based on intuiti- isticlogicand, thus, beviewedasadirectdescendant ofBrouwer'sintuitionism. The two conferences were successful in bringing together a number of internationally renowned mathematicians and philosophers around common concerns. Once again it was con rmed that philosophers and mathematicians can work together and that real progress in the philosophy and foundations of mathematics is possible only if they do. Most of the papers in this collection originate from the two conferences, but a few additional papers of relevance to the issues discussed at the Uppsala c- ferences have been solicited especially for this volume."

The present book deals with coalition games in which expected pay-offs are only vaguely known. In fact, this idea about vagueness of expectations ap pears to be adequate to real situations in which the coalitional bargaining anticipates a proper realization of the game with a strategic behaviour of players. The vagueness being present in the expectations of profits is mod elled by means of the theory of fuzzy set and fuzzy quantities. The fuzziness of decision-making and strategic behaviour attracts the attention of mathematicians and its particular aspects are discussed in sev eral works. One can mention in this respect in particular the book "Fuzzy and Multiobjective Games for Conflict Resolution" by Ichiro Nishizaki and Masatoshi Sakawa (referred below as 43]) which has recently appeared in the series Studies in Fuzziness and Soft Computing published by Physica-Verlag in which the present book is also apperaing. That book, together with the one you carry in your hands, form in a certain sense a complementary pair. They present detailed views on two main aspects forming the core of game theory: strategic (mostly 2-person) games, and coalitional (or cooperative) games. As a pair they offer quite a wide overview of fuzzy set theoretical approaches to game theoretical models of human behaviour."

Thisvolumecontainsthepapersofthe20thInternationalConferenceonRewr- ing Techniques and Applications (RTA 2009), which was held from June 29 to July 1, 2009, in Bras' ?lia, Brazil as part of the 5th International Conference on Rewriting, Deduction, and Programming (RDP 2009) together with the Int- national Conference on Typed Lambda Calculi and Applications (TLCA 2009), the International School on Rewriting (ISR 2009), the 4th Workshop on Logical and Semantic Frameworks with Applications (LSFA 2009), the 10th Inter- tional Workshop on Rule-Based Programming (RULE 2009), the 8th Inter- tional Workshop on Functional and (Constraint) Logic Programming (WFLP 2009), the 9th International Workshop on Reduction Strategies in Rewriting and Programming (WRS 2009), and the annual meeting of the IFIP Working Group 1.6 on term rewriting. RTA is the major forum for the presentation of research on all aspects of rewriting.PreviousRTAconferenceswereheldinDijon(1985),Bordeaux(1987), Chapel Hill (1989), Como (1991), Montreal (1993), Kaiserslautern (1995), R- gers (1996), Sitges (1997), Tsukuba (1998), Trento (1999), Norwich (2000), Utrecht(2001),Copenhagen(2002),Valencia(2003),Aachen(2004),Nara(2005), Seattle (2006), Paris (2007), and Hagenberg (2008).

The capabilities of modern technology are rapidly increasing, spurred on to a large extent by the tremendous advances in communications and computing. Automated vehicles and global wireless connections are some examples of these advances. In order to take advantage of such enhanced capabilities, our need to model and manipulate our knowledge of the geophysical world, using compatible representations, is also rapidly increasing. In response to this one fundamental issue of great concern in modern geographical research is how to most effectively capture the physical world around us in systems like geographical information systems (GIS). Making this task even more challenging is the fact that uncertainty plays a pervasive role in the representation, analysis and use of geospatial information. The types of uncertainty that appear in geospatial information systems are not the just simple randomness of observation, as in weather data, but are manifested in many other forms including imprecision, incompleteness and granularization. Describing the uncertainty of the boundaries of deserts and mountains clearly require different tools than those provided by probability theory. The multiplicity of modalities of uncertainty appearing in GIS requires a variety of formalisms to model these uncertainties. In light of this it is natural that fuzzy set theory has become a topic of intensive interest in many areas of geographical research and applications This volume, Fuzzy Modeling with Spatial Information for Geographic Problems, provides many stimulating examples of advances in geographical research based on approaches using fuzzy sets and related technologies.

1 2 Harald Atmanspacher and Hans Primas 1 Institute for Frontier Areas of Psychology, Freiburg, Germany, [email protected] 2 ETH Zurich, Switzerland, [email protected] Thenotionofrealityisofsupremesigni?canceforourunderstandingofnature, the world around us, and ourselves. As the history of philosophy shows, it has been under permanent discussion at all times. Traditional discourse about - ality covers the full range from basic metaphysical foundations to operational approaches concerning human kinds of gathering and utilizing knowledge, broadly speaking epistemic approaches. However, no period in time has ex- rienced a number of moves changing and, particularly, restraining traditional concepts of reality that is comparable to the 20th century. Early in the 20th century, quite an in?uential move of such a kind was due to the so-called Copenhagen interpretation of quantum mechanics, laid out essentially by Bohr, Heisenberg, and Pauli in the mid 1920s. Bohr's dictum, quoted by Petersen (1963, p.12), was that "it is wrong to think that the task of physics is to ?nd out how nature is. Physics concerns what we can say about nature." Although this standpoint was not left unopposed - Einstein, Schr] odinger, and others were convinced that it is the task of science to ?nd out about nature itself - epistemic, operational attitudes have set the fashion for many discussions in the philosophy of physics (and of science in general) until today."

This book reflects the progress made in the forty years since the appearance of Abraham Robinson 's revolutionary book Nonstandard Analysis in the foundations of mathematics and logic, number theory, statistics and probability, in ordinary, partial and stochastic differential equations and in education. The contributions are clear and essentially self-contained.

Extensively researched, this book traces the life and work of Abraham De Moivre as well as the state of probability and statistics in eighteenth-century Britain. It is the first extensive biography of De Moivre and is based on recently discovered material and translations, including some of De Moivre's letters. The book begins with discussions on De Moivre's early life in France and his initial work in pure mathematics with some excursions into celestial mechanics. It then describes his fundamental contributions to probability theory and applications, including those in finance and actuarial science. The author explores how De Moivre's wide network of personal and professional connections often motivated his research. The book also covers De Moivre's contemporaries and his impact on the field. Written in a clear, approachable style, this biography will appeal to historians and practitioners of the art of probability and statistics in a wide range of applications, including finance and actuarial science.

Categories and sheaves, which emerged in the middle of the last century as an enrichment for the concepts of sets and functions, appear almost everywhere in mathematics nowadays.

This book covers categories, homological algebra and sheaves in a systematic and exhaustive manner starting from scratch, and continues with full proofs to an exposition of the most recent results in the literature, and sometimes beyond.

The authors present the general theory of categories and functors, emphasising inductive and projective limits, tensor categories, representable functors, ind-objects and localization. Then they study homological algebra including additive, abelian, triangulated categories and also unbounded derived categories using transfinite induction and accessible objects. Finally, sheaf theory as well as twisted sheaves and stacks appear in the framework of Grothendieck topologies.

Parameterized complexity theory is a recent branch of computational complexity theory that provides a framework for a refined analysis of hard algorithmic problems. The central notion of the theory, fixed-parameter tractability, has led to the development of various new algorithmic techniques and a whole new theory of intractability.

This book is a state-of-the-art introduction to both algorithmic techniques for fixed-parameter tractability and the structural theory of parameterized complexity classes, and it presents detailed proofs of recent advanced results that have not appeared in book form before. Several chapters are each devoted to intractability, algorithmic techniques for designing fixed-parameter tractable algorithms, and bounded fixed-parameter tractability and subexponential time complexity. The treatment is comprehensive, and the reader is supported with exercises, notes, a detailed index, and some background on complexity theory and logic.

The book will be of interest to computer scientists, mathematicians and graduate students engaged with algorithms and problem complexity.

These notes are devoted to the study of some classical problems in the Geometry of Banach spaces. The novelty lies in the fact that their solution relies heavily on techniques coming from Descriptive Set Theory. Thecentralthemeisuniversalityproblems.Inparticular, thetextprovides an exposition of the methods developed recently in order to treat questions of the following type: (Q) LetC be a class of separable Banach spaces such that every space X in the classC has a certain property, say property (P). When can we ?nd a separable Banach space Y which has property (P) and contains an isomorphic copy of every member ofC? We will consider quite classical properties of Banach spaces, such as "- ing re?exive," "having separable dual," "not containing an isomorphic copy of c," "being non-universal," etc. 0 It turns out that a positive answer to problem (Q), for any of the above mentioned properties, is possible if (and essentially only if) the classC is "simple." The "simplicity" ofC is measured in set theoretic terms. Precisely, if the classC is analytic in a natural "coding" of separable Banach spaces, then we can indeed ?nd a separable space Y which is universal for the class C and satis?es the requirements imposed above.

Edited in collaboration with FoLLI, the Association of Logic, Language and Information, this book constitutes the refereed proceedings of the Second International Workshop on Logic, Rationality, and Interaction, LORI 2009, held in Chongqing, China, in October 2009.

The 24 revised full papers presented together with 8 posters were carefully reviewed and selected from a flood of submissions. The workshops topics include but are not limited to semantic models for knowledge, for belief, and for uncertainty, dynamic logics of knowledge, information flow, and action, logical analysis of the structure of games, belief revision, belief merging, logics for preferences and utilities, logics of intentions, plans, and goals, logics of probability and uncertainty, argument systems and their role in interaction, as well as norms, normative interaction, and normative multiagent systems.

The kernel of this book consists of a series of lectures on in?nitary proof theory which I gave during my time at the Westfalische ] Wilhelms-Universitat ] in Munster ] . It was planned as a successor of Springer Lecture Notes in Mathematics 1407. H- ever, when preparing it, I decided to also include material which has not been treated in SLN 1407. Since the appearance of SLN 1407 many innovations in the area of - dinal analysis have taken place. Just to mention those of them which are addressed in this book: Buchholz simpli?ed local predicativity by the invention of operator controlled derivations (cf. Chapter 9, Chapter 11); Weiermann detected applications of methods of impredicative proof theory to the characterization of the provable recursive functions of predicative theories (cf. Chapter 10); Beckmann improved Gentzen's boundedness theorem (which appears as Stage Theorem (Theorem 6. 6. 1) in this book) to Theorem 6. 6. 9, a theorem which is very satisfying in itself - though its real importance lies in the ordinal analysis of systems, weaker than those treated here. Besides these innovations I also decided to include the analysis of the theory (? -REF) as an example of a subtheory of set theory whose ordinal analysis only 2 0 requires a ?rst step into impredicativity. The ordinal analysis of(? -FXP) of non- 0 1 0 monotone? -de?nable inductive de?nitions in Chapter 13 is an application of the 1 analysis of(? -REF)."

The Shape of Space, Third Edition maintains the standard of excellence set by the previous editions. This lighthearted textbook covers the basic geometry and topology of two- and three-dimensional spaces-stretching students' minds as they learn to visualize new possibilities for the shape of our universe. Written by a master expositor, leading researcher in the field, and MacArthur Fellow, its informal exposition and engaging exercises appeal to an exceptionally broad audience, from liberal arts students to math undergraduate and graduate students looking for a clear intuitive understanding to supplement more formal texts, and even to laypeople seeking an entertaining self-study book to expand their understanding of space. Features of the Third Edition: Full-color figures throughout "Picture proofs" have replaced algebraic proofs Simpler handles-and-crosscaps approach to surfaces Updated discussion of cosmological applications Intuitive examples missing from many college and graduate school curricula About the Author: Jeffrey R. Weeks is a freelance geometer living in Canton, New York. With support from the U.S. National Science Foundation, the MacArthur Foundation and several science museums, his work spans pure mathematics, applications in cosmology and-closest to his heart-exposition for the general public.

An Introduction to Mathematical Proofs presents fundamental material on logic, proof methods, set theory, number theory, relations, functions, cardinality, and the real number system. The text uses a methodical, detailed, and highly structured approach to proof techniques and related topics. No prerequisites are needed beyond high-school algebra. New material is presented in small chunks that are easy for beginners to digest. The author offers a friendly style without sacrificing mathematical rigor. Ideas are developed through motivating examples, precise definitions, carefully stated theorems, clear proofs, and a continual review of preceding topics. Features Study aids including section summaries and over 1100 exercises Careful coverage of individual proof-writing skills Proof annotations and structural outlines clarify tricky steps in proofs Thorough treatment of multiple quantifiers and their role in proofs Unified explanation of recursive definitions and induction proofs, with applications to greatest common divisors and prime factorizations About the Author: Nicholas A. Loehr is an associate professor of mathematics at Virginia Technical University. He has taught at College of William and Mary, United States Naval Academy, and University of Pennsylvania. He has won many teaching awards at three different schools. He has published over 50 journal articles. He also authored three other books for CRC Press, including Combinatorics, Second Edition, and Advanced Linear Algebra.

The symposium "Languages: From Formal to Natural," celebrating the 65th birthday of Nissim Francez, was held on May 24-25, 2009 at the Technion, Haifa. The symposium consisted of two parts, a veri?cation day and a language day, and covered all areas of Nissim's past and present research interests, areas which he has inspiringly in?uenced and to which he has contributed so much. This volume comprises severalpapers presentedat the symposium, as wellas additional articles that were contributed by Nissim's friends and colleagues who were unable to attend the event. We thank the authors for their contributions. Wearealsogratefultothereviewersfor their dedicated and timely work. Nissim Francez was born on January 19, 1944. In 1962 he started his mat- matical education at the Hebrew University. He received a BSc in Mathematics in 1965, and, after four years of military service, started his MSc studies in Computer Science at the Weizmann Institute of Science under the supervision of Amir Pnueli. After completing the MSc program in 1971, Nissim continued his studies toward a PhD, again, at the Weizmann Institute of Science and, again, under the supervisionof Amir Pnueli. Nissim wasawardeda PhDin Computer Science in 1976.

The discipline of formal concept analysis (FCA) is concerned with the form- ization of concepts and conceptual thinking. Built on the solid foundation of lattice and order theory, FCA is ?rst and foremost a mathematical discipline. However,its motivation andguiding principles arebasedon strongphilosophical underpinnings. In practice, FCA provides a powerful framework for the qua- tative, formal analysis of data, as demonstrated by numerous applications in diverse areas. Likewise, it emphasizes the aspect of human-centered information processing by employing visualization techniques capable of revealing inherent structure in data in an intuitively graspable way. FCA thereby contributes to structuring and navigating the ever-growing amount of information available in our evolving information society and supports the process of turning data into information and ultimately into knowledge. In response to an expanding FCA community, the International Conference on Formal Concept Analysis (ICFCA) was established to provide an annual opportunity for the exchange of ideas. Previous ICFCA conferences were held in Darmstadt (2003), Sydney (2004), Lens (2005), Dresden (2006), Clermont- Ferrand (2007), as well as Montreal (2008) and are evidence of vivid ongoing interest and activities in FCA theory and applications. ICFCA 2009 took place during May 21-24 at the University of Applied S- ences in Darmstadt. Beyond serving as a host of the very ?rst ICFCA in 2003, Darmstadt can be seen as the birthplace of FCA itself, where this discipline was introduced in the early 1980s and elaborated over the subsequent decades.

This book constitutes the thoroughly refereed post-conference proceedings of the 19th International Workshop on Recent Trends in Algebraic Development Techniques, WADT 2008, held in Pisa, Italy, on June 13-16, 2008.

The 18 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 33 presentations at the workshop.

The papers focus on the algebraic approaches to the specification and development of systems, and address topics such as formal methods for system development, specification languages and methods, systems and techniques for reasoning about specifications, specification development systems, methods and techniques for concurrent, distributed and mobile systems, and algebraic and co-algebraic foundations.

AccordingtoHolzmann 14], protocol speci?cationscomprise ?veelements: the service the protocol provides toits users; the set of messages that are exchanged between protocol entities; the format of each message; the rules governingm- sage exchange (procedures); and the assumptionsabout the environment in which the protocol is intended tooperate. In protocol standards documents, information related to the operatingenvironment isusually writteninformally andmayoccur in several di?erentplaces 37]. This informal speci?cation style canlead to misunderstandings andpossibly incompatible implementations. In contrast, executableformalmodelsrequireprecisespeci?cations oftheoperating environment. Ofparticularsigni?canceisthecommunicationmediumorchannel over which the protocol operates. Channelscan havedi?erent characteristics depending on the physical media (e. g. optical ?bre, copper, cable orunguided media (radio)) they employ. The characteristics also depend on the levelof the protocol inacomputer protocol architecture. Forexample, the link-leveloperates over a singlemedium, whereas the network, transport andapplication levelsmayoperate over a network, or network of networks such as the Internet, which couldemploy several di?erent physical media. Channels (such as satellite links) can be noisy resulting in bit errors in packets. To correct biterrors in packets, many importantprotocols (such the Internet's TransmissionControl Protocol 27]) use CyclicRedundancy Checks (CRCs) 28] to detect errors. On detectingan error, the receiver discards the packet andrelies on the sender to retransmit itforrecovery, known as Au- maticRepeatreQuest(ARQ) 28]. Thisisachievedbythereceiveracknowledging the receipt of good packets, andby the transmitter maintainingatimer. When the timer expires before an acknowledgementhasbeen received, the transmitter retransmits packets that havebeen sent but are as yet notacknowledged. It may also be possibleforpacketsto be lost due to routers in networks discarding packets when congested

This volume contains the papers presented at SAT 2009: 12th International Conference on Theory and Applications of Satis?ability Testing, held from June 30 to July 3, 2009 in Swansea (UK). The International Conference on Theory and Applications of Satis?ability Testing (SAT) started in 1996 as a series of workshops, and, in parallel with the growthof SAT, developedinto the main eventfor SAT research. This year'sc- ference testi?ed to the strong interest in SAT, regarding theoretical research, - searchonalgorithms, investigationsintoapplications, anddevelopmentofsolvers and software systems. As a core problem of computer science, SAT is central for many research areas, and has deep interactions with many mathematical s- jects. Major impulses for the development of SAT came from concrete practical applications as well as from fundamental theoretical research. This fruitful c- laboration can be seen in virtually all papers of this volume. There were 86 submissions (completed papers within the scope of the c- ference). Each submission was reviewed by at least three, and on average 4. 0 Programme Committee members. The Committee decided to accept 45 papers, consisting of 34 regular and 11 short papers (restricted to 6 pages). A main n- elty was a "shepherding process," where 29% of the papers were accepted only conditionally, and requirements on necessary improvements were formulated by the ProgrammeCommittee and its installment monitored by the "shepherd" for thatpaper(using possibly severalroundsoffeedback).

The theory of sets, described in the preface to this book as 'Georg Cantor's magnificent theory' was first developed in the 1870s, and was recognised as one of the most important new branches of mathematical science. W. H. Young and his wife Grace Chisholm Young wrote this book, published in 1906, as a 'simple presentation'; but they warn that it is effectively a work in progress: the writing 'has necessarily involved attempts to extend the frontier of existing knowledge, and to fill in gaps which broke the connexion between isolated parts of the subject.' The Young's were a dynamic force in mathematical research: William had been Grace's tutor at Girton College; she was subsequently the first woman to be awarded a Ph. D by the University of G ttingen. Cantor himself said of the book: 'It is a pleasure for me to see with what diligence, skill and success you have worked.'