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.

This textbook prepares graduate students for research in numerical analysis/computational mathematics by giving to them a mathematical framework embedded in functional analysis and focused on numerical analysis. This helps the student to move rapidly into a research program. The text covers basic results of functional analysis, approximation theory, Fourier analysis and wavelets, iteration methods for nonlinear equations, finite difference methods, Sobolev spaces and weak formulations of boundary value problems, finite element methods, elliptic variational inequalities and their numerical solution, numerical methods for solving integral equations of the second kind, and boundary integral equations for planar regions. The presentation of each topic is meant to be an introduction with certain degree of depth. Comprehensive references on a particular topic are listed at the end of each chapter for further reading and study.

Because of the relevance in solving real world problems, multivariable polynomials are playing an ever more important role in research and applications. In this third editon, a new chapter on this topic has been included and some major changes are made on two chapters from the previous edition. In addition, there are numerous minor changes throughout the entire text and new exercises are added.

Review of earlier edition:

..".the book is clearly written, quite pleasant to read, and contains a lot of important material; and the authors have done an excellent job at balancing theoretical developments, interesting examples and exercises, numerical experiments, and bibliographical references."

R. Glowinski, SIAM Review, 2003

Homology is a powerful tool used by mathematicians to study the properties of spaces and maps that are insensitive to small perturbations. This book uses a computer to develop a combinatorial computational approach to the subject. The core of the book deals with homology theory and its computation. Following this is a section containing extensions to further developments in algebraic topology, applications to computational dynamics, and applications to image processing. Included are exercises and software that can be used to compute homology groups and maps. The book will appeal to researchers and graduate students in mathematics, computer science, engineering, and nonlinear dynamics.

Starting at an introductory level, the book leads rapidly to important and often new results in synthetic differential geometry. From rudimentary analysis the book moves to such important results as: a new proof of De Rham's theorem; the synthetic view of global action, going as far as the Weil characteristic homomorphism; the systematic account of structured Lie objects, such as Riemannian, symplectic, or Poisson Lie objects; the view of global Lie algebras as Lie algebras of a Lie group in the synthetic sense; and lastly the synthetic construction of symplectic structure on the cotangent bundle in general. Thus while the book is limited to a naive point of view developing synthetic differential geometry as a theory in itself, the author nevertheless treats somewhat advanced topics, which are classic in classical differential geometry but new in the synthetic context. Audience: The book is suitable as an introduction to synthetic differential geometry for students as well as more qualified mathematicians.

without a properly developed inconsistent calculus based on infinitesimals, then in consistent claims from the history of the calculus might well simply be symptoms of confusion. This is addressed in Chapter 5. It is further argued that mathematics has a certain primacy over logic, in that paraconsistent or relevant logics have to be based on inconsistent mathematics. If the latter turns out to be reasonably rich then paraconsistentism is vindicated; while if inconsistent mathematics has seri ous restriytions then the case for being interested in inconsistency-tolerant logics is weakened. (On such restrictions, see this chapter, section 3. ) It must be conceded that fault-tolerant computer programming (e. g. Chapter 8) finds a substantial and important use for paraconsistent logics, albeit with an epistemological motivation (see this chapter, section 3). But even here it should be noted that if inconsistent mathematics turned out to be functionally impoverished then so would inconsistent databases. 2. Summary In Chapter 2, Meyer's results on relevant arithmetic are set out, and his view that they have a bearing on G8del's incompleteness theorems is discussed. Model theory for nonclassical logics is also set out so as to be able to show that the inconsistency of inconsistent theories can be controlled or limited, but in this book model theory is kept in the background as much as possible. This is then used to study the functional properties of various equational number theories."

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.

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

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.

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.

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).

Line graphs have the property that their least eigenvalue is greater than or equal to -2, a property shared by generalized line graphs and a finite number of so-called exceptional graphs. This book deals with all these families of graphs in the context of their spectral properties. The authors discuss the three principal techniques that have been employed, namely 'forbidden subgraphs', 'root systems' and 'star complements'. They bring together the major results in the area, including the recent construction of all the maximal exceptional graphs. Technical descriptions of these graphs are included in the appendices, while the bibliography provides over 250 references. This will be an important resource for all researchers with an interest in algebraic graph theory.

Category theory has experienced a resurgence in popularity recently because of new links with topology and mathematical physics. This book provides a clearly written account of higher order category theory and presents operads and multicategories as a natural language for its study. Tom Leinster has included necessary background material and applications as well as appendices containing some of the more technical proofs that might have disrupted the flow of the text.

The Symposium on Logical Foundations of Computer Science series provides a forum for the fast-growing body of work in the logical foundations of computer science, e.g., those areas of fundamental theoretical logic related to computer science. The LFCS series began with "Logic at Botik," Pereslavl-Zalessky,1989, which was co-organized by Albert R. Meyer (MIT) and Michael Taitslin (Tver). After that, organization passed to Anil Nerode. Currently LFCS is governed by a Steering Committee consisting of Anil Nerode (General Chair), Stephen Cook, Dirk van Dalen, Yuri Matiyasevich, John McCarthy, J. Alan Robinson, Gerald Sacks, and Dana Scott. The 2009 Symposium on Logical Foundations of Computer Science (LFCS 2009) took place in Howard Johnson Plaza Resort, Deer?eld Beach, Florida, USA, during January 3-6. This volume contains the extended abstracts of talks selected by the Program Committee for presentation at LFCS 2009. The scope of the symposium is broad and contains constructive mathematics and type theory; automata and automatic structures; computability and r- domness; logical foundations of programming; logical aspects of computational complexity; logic programmingand constraints;automated deduction and int- active theorem proving; logical methods in protocol and program veri?cation; logical methods in program speci?cation and extraction; domain theory l- ics; logical foundations of database theory; equational logic and term rewriting; lambda andcombinatorycalculi;categoricallogicandtopologicalsemantics;l- ear logic; epistemic and temporal logics; intelligent and multiple agent system logics; logics of proof and justi?cation; nonmonotonic reasoning; logic in game theory and social software; logic of hybrid systems; distributed system logics;

This tract presents an exposition of methods for testing sets of special functions for completeness and basis properties, mostly in L2 and L2 spaces. The first chapter contains the theoretical background to the subject, largely in a general Hilbert space setting, and theorems in which the structure of Hilbert space is revealed by properties of its bases are dealt with. Later parts of the book deal with methods: for example, the Vitali criterion, together with its generalisations and applications, is discussed in some detail, and there is an introduction to the theory of stability of bases. The last chapter deals with complete sets as eigenfunctions of differential and a table of a wide variety of bases and complete sets of special functions. Dr Higgins' account will be useful to graduate students of mathematics and professional mathematicians, especially Banach spaces. The emphasis on methods of testing and their applications will also interest scientists and engineers engaged in fields such as the sampling theory of signals in electrical engineering and boundary value problems in mathematical physics.

In the last century, developments in mathematics, philosophy, physics, computer science, economics and linguistics have proven important for the development of logic. There has been an influx of new ideas, concerns, and logical systems reflecting a great variety of reasoning tasks in the sciences. This book embodies the multi-dimensional interplay between logic and science, presenting contributions from the world's leading scholars on new trends and possible developments for research.

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.

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.

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 study of higher dimensional categories has mostly been developed in the globular form of 2-categories, n-categories, omega-categories and their weak versions. Here we study a different form: double categories, n-tuple categories and multiple categories, with their weak and lax versions.We want to show the advantages of this form for the theory of adjunctions and limits. Furthermore, this form is much simpler in higher dimension, starting with dimension three where weak 3-categories (also called tricategories) are already quite complicated, much more than weak or lax triple categories.This book can be used as a textbook for graduate and postgraduate studies, and as a basis for research. Notions are presented in a 'concrete' way, with examples and exercises; the latter are endowed with a solution or hints. Part I, devoted to double categories, starts at basic category theory and is kept at a relatively simple level. Part II, on multiple categories, can be used independently by a reader acquainted with 2-dimensional categories.

Einstein's equations stem from General Relativity. In the context of Riemannian manifolds, an independent mathematical theory has developed around them. This is the first book which presents an overview of several striking results ensuing from the examination of Einstein 's equations in the context of Riemannian manifolds. Parts of the text can be used as an introduction to modern Riemannian geometry through topics like homogeneous spaces, submersions, or Riemannian functionals.

This book, suitable for interested post-16 school pupils or undergraduates looking for a supplement to their course text, develops our modern view of space-time and its implications in the theories of gravity and cosmology. While aspects of this topic are inevitably abstract, the book seeks to ground thinking in observational and experimental evidence where possible. In addition, some of Einstein's philosophical thoughts are explored and contrasted with our modern views. Written in an accessible yet rigorous style, Jonathan Allday, a highly accomplished writer, brings his trademark clarity and engagement to these fascinating subjects, which underpin so much of modern physics. Features: Restricted use of advanced mathematics, making the book suitable for post-16 students and undergraduates Contains discussions of key modern developments in quantum gravity, and the latest developments in the field, including results from the Laser Interferometer Gravitational-Wave Observatory (LIGO) Accompanied by appendices on the CRC Press website featuring detailed mathematical arguments for key derivations