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.

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.

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

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.

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;

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

Charles Chihara's new book develops and defends a structural view of the nature of mathematics, and uses it to explain a number of striking features of mathematics that have puzzled philosophers for centuries. The view is used to show that, in order to understand how mathematical systems are applied in science and everyday life, it is not necessary to assume that its theorems either presuppose mathematical objects or are even true.
Chihara builds upon his previous work, in which he presented a new system of mathematics, the constructibility theory, which did not make reference to, or resuppose, mathematical objects. Now he develops the project further by analyzing mathematical systems currently used by scientists to show how such systems are compatible with this nominalistic outlook. He advances several new ways of undermining the heavily discussed indispensability argument for the existence of mathematical objects made famous by Willard Quine and Hilary Putnam. And Chihara presents a rationale for the nominalistic outlook that is quite different from those generally put forward, which he maintains have led to serious misunderstandings.
A Structural Account of Mathematics will be required reading for anyone working in this field.

This monograph gives an introductory treatment of the most important iterative methods for constructing fixed points of nonlinear contractive type mappings. For each iterative method considered, it summarizes the most significant contributions in the area by presenting some of the most relevant convergence theorems. It also presents applications to the solution of nonlinear operator equations as well as the appropriate error analysis of the main iterative methods.

The 7th International Conference on Theory and Applications of Satis?ab- ity Testing (SAT 2004) was held 10-13 May 2004 in Vancouver, BC, Canada. The conference featured 9 technical paper sessions, 2 poster sessions, as well as the 2004 SAT Solver Competition and the 2004 QBF Solver Evaluation. It also included invited talks by Stephen A. Cook (University of Toronto) and Kenneth McMillan (Cadence Berkeley Labs). The 89 participants represented no less than 17 countries and four continents. SAT 2004 continued the series of meetings which started with the Workshops on Satis?ability held in Siena, Italy (1996), Paderborn, Germany (1998) and Renesse, The Netherlands (2000); the Workshop on Theory and Applications of Satis?ability Testing held in Boston, USA(2001);theSymposiumonTheoryandApplicationsofSatis?abilityTesting held in Cincinnati, USA (2002); and the 6th International Conference on Theory and Applications of Satis?ability Testing held in Santa Margherita Ligure, Italy (2003). The International Conference on Theory and Applications of Satis?ability Testing is the primary annual meeting for researchers studying the propo- tional satis?ability problem (SAT), a prominent problem in both theoretical and applied computer science. SAT lies at the heart of the most important open problem in complexity theory (P vsNP) and underlies many applications in, among other examples, arti?cial intelligence, operations research and electronic design engineering. The primary objective of the conferences is to bring together researchersfromvariousareasandcommunities, includingtheoreticalandexp- imental computer science as well as many relevant application areas, to promote collaboration and the communication of new theoretical and practical results in SAT-related research and its industrial applications

Model theory is a branch of mathematical logic that has found applications in several areas of algebra and geometry. It provides a unifying framework for the understanding of old results and more recently has led to significant new results, such as a proof of the Mordell-Lang conjecture for function fields in positive characteristic. Perhaps surprisingly, it is sometimes the most abstract aspects of model theory that are relevant to those applications. This book gives the necessary background for understanding both the model theory and the mathematics behind the applications. Aimed at graduate students and researchers, it contains introductory surveys by leading experts covering the whole spectrum of contemporary model theory (stability, simplicity, o-minimality and variations), and introducing and discussing the diverse areas of geometry (algebraic, diophantine, real analytic, p-adic, and rigid) to which the model theory is applied. The book begins with an introduction to model theory by David Marker. It then broadens into three components: pure model theory (Bradd Hart, Dugald Macpherson), geometry(Barry Mazur, Ed Bierstone and Pierre Milman, Jan Denef), and the model theory of fields (Marker, Lou van den Dries, Zoe Chatzidakis).

By presenting state-of-the-art results in logical reasoning and formal methods in the context of artificial intelligence and AI applications, this book commemorates the 60th birthday of JArg H. Siekmann.

The 30 revised reviewed papers are written by former and current students and colleagues of JArg Siekmann; also included is an appraisal of the scientific career of JArg Siekmann entitled "A Portrait of a Scientist: Logics, AI, and Politics." The papers are organized in four parts on logic and deduction, applications of logic, formal methods and security, and agents and planning.

This is the concluding volume of the second edition of the standard text on design theory. Since the first edition there has been extensive development of the theory and this book has been thoroughly rewritten to reflect this. In particular the growing importance of discrete mathematics to many parts of engineering and science have made designs a useful tool for applications, and this fact has been acknowledged here with the inclusion of an additional chapter on applications. It is suitable for advanced courses and as a reference work, not only for researchers in discrete mathematics or finite algebra, but also for those working in computer and communications engineering and other mathematically oriented disciplines. Exercises are included throughout, and the book concludes with an extensive and updated bibliography of well over 1800 items.

This book presents in detail a complete set of best-fit algorithms for general curves and surfaces in space. Such best-fit algorithms approximate and estimate curve and surface parameters by minimizing the shortest distances between the curve or surface and the measurement point.

After reviewing the basics for representing curves and surfaces in space and fitting in general, the author presents three algorithms for orthogonal distance fitting combining numerical methods and minimizational methods. These algorithms are applied to implicit and parametric curves and surfaces in 2D and 3D space possessing a broad variety of algorithmic features. Finally, an appendix provides practical information for applying the general orthogonal distance fitting algorithms to fit special model features.

Obvious application areas of the algorithms presented are robot navigation, including the navigation of autonomous vehicles or the grasping of work pieces, as well as factory digitization in general.

During 1996-97 MSRI held a full academic-year program on combinatorics, with special emphasis on its connections to other branches of mathematics, such as algebraic geometry, topology, commutative algebra, representation theory, and convex geometry. The rich combinatorial problems arising from the study of various algebraic structures are the subject of this book, which features work done or presented at the program's seminars. The text contains contributions on matroid bundles, combinatorial representation theory, lattice points in polyhedra, bilinear forms, combinatorial differential topology and geometry, Macdonald polynomials and geometry, enumeration of matchings, the generalized Baues problem, and Littlewood-Richardson semigroups. These expository articles, written by some of the most respected researchers in the field, present the state of the art to graduate students and researchers in combinatorics as well as in algebra, geometry, and topology.

"This engagingly written text provides a useful pedagogical introduction to an extensive class of geometrical phenomena in the optics of polarization and phase, including simple explanations of much of the underlying mathematics." -Michael Berry, University of Bristol, UK "The author covers a vast number of topics in great detail, with a unifying mathematical treatment. It will be a useful reference for both beginners and experts...." -Enrique Galvez, Charles A. Dana Professor of Physics and Astronomy, Colgate University "a firm and comprehensive grounding both for those looking to acquaint themselves with the field and those of us that need reminding of the things we thought we knew, but hitherto did not understand: an essential point of reference." -Miles Padgett, Kelvin Chair of Natural Philosophy and Vice Principal (Research), University of Glasgow This book focuses on the various forms of wavefield singularities, including optical vortices and polarization singularities, as well as orbital angular momentum and associated applications. It highlights how an understanding of singular optics provides a completely different way to look at light. Whereas traditional optics focuses on the shape and structure of the non-zero portions of the wavefield, singular optics describes a wave's properties from its null regions. The contents cover the three main areas of the field: the study of generic features of wavefields, determination of unusual properties of vortices and wavefields that contain singularities, and practical applications of vortices and other singularities.

The British Combinatorial Conference is one of the most well-known meetings for combinatorialists. This volume collects the invited talks from the 1999 conference held at the University of Kent, and together these span a broad range of combinatorial topics. The nine talks are from: S. Ball, J. Dinitz, M. Dyer, K. Metsch, J. Pach, R. Thomas, C. Thomassen, N. Wormald, plus a special contribution from W. T. Tutte. All researchers into combinatorics will find that this volume is an outstanding and up-to-date resource.