This book constitutes the refereed proceedings of the 10th International Conference on Theory and Applications of Satisfiability Testing, SAT 2007, held in Lisbon, Portugal in May 2007.

The 22 revised full papers presented together with 12 revised short papers and two invited talks cover all current research issues in propositional and quantified Boolean formula satisfiability testing.

In Single Digits, Marc Chamberland takes readers on a fascinating exploration of small numbers, from one to nine, looking at their history, applications, and connections to various areas of mathematics, including number theory, geometry, chaos theory, numerical analysis, and mathematical physics. For instance, why do eight perfect card shuffles leave a standard deck of cards unchanged? And, are there really "six degrees of separation" between all pairs of people? Chamberland explores these questions and covers vast numerical territory, such as illustrating the ways that the number three connects to chaos theory, the number of guards needed to protect an art gallery, problematic election results and so much more. The book's short sections can be read independently and digested in bite-sized chunks--especially good for learning about the Ham Sandwich Theorem and the Pizza Theorem. Appealing to high school and college students, professional mathematicians, and those mesmerized by patterns, this book shows that single digits offer a plethora of possibilities that readers can count on.

This unified approach to the foundations of mathematics in the theory of sets covers both conventional and finitary (constructive) mathematics. It is based on a philosophical, historical and mathematical analysis of the relation between the concepts of "natural number" and "set". The book contains an investigation of the logic of quantification over the universe of sets and a discussion of its role in second order logic, and the analysis of proof by induction and definition by recursion. The book should appeal to both philosophers and mathematicians with an interest in the foundations of mathematics.

This book constitutes the refereed proceedings of the 27th International Conference on Applications and Theory of Petri Nets and Other Models of Concurrency, ICATPN 2006, held in Turku, Finland in June 2006. The book presents 16 revised full papers and 6 revised tool papers together with 4 invited papers. All current issues on research and development in the area of Petri nets and modeling of concurrent systems are addressed.

Biomolecular computing has emerged as an interdisciplinary ?eld that draws - getherchemistry, computerscience, mathematics, molecularbiology, andphysics. Our knowledge of DNA nanotechnology and biomolecular computing increases dramatically with every passing year. The International Meeting on DNA C- puting has been a forum where scientists with di?erent backgrounds, yet sh- ing a common interest in biomolecular computing, meet and present their latest results. Continuing this tradition, the 10th International Meeting on DNA C- puting(DNA10)focusedonthecurrentexperimentalandtheoreticalresultswith the greatest impact. The meeting took place at the University of Milano-Bicocca, Milan, Italy, from June 7 to June 10, 2004, and it was organized by the University of Milano- Bicocca and the Department of Informatics of the University of Milano-Bicocca. Papersandposterpresentationsweresoughtinallareasthatrelatetobiomole- lar computing, including (but not restricted to): demonstrations of biomolecular computing (using DNA and/or other molecules), theoretical models of biomol- ularcomputing, biomolecularalgorithms, computationalprocessesinvitroandin vivo, analysis and theoretical models of laboratory techniques, biotechnological and other applications of DNA computing, DNA nanostructures, DNA devices such as DNA motors, DNA error evaluation and correction, in vitro evolution, molecular design, self-assembled systems, nucleic acid chemistry, and simulation tools. Authors were asked to choose between two di?erent tracks: Track A - Full paper, for authors who wished to submit a full paper for presentation at DNA10 (oral or poster), and publication in the conference p- ceedings. Track B - One-page abstract, for authors submitting experimental results, and who planned to submit their manuscript to a scienti?c journal, rather than publish it in the conference procee

AC, the axiom of choice, because of its non-constructive character, is the most controversial mathematical axiom. It is shunned by some, used indiscriminately by others. This treatise shows paradigmatically that disasters happen without AC and they happen with AC. Illuminating examples are drawn from diverse areas of mathematics, particularly from general topology, but also from algebra, order theory, elementary analysis, measure theory, game theory, and graph theory.

This book constitutes the refereed proceedings of the 10th International Conference on Developments in Language Theory, DLT 2006, held in Santa Barbara, CA, June 2006. The book presents 36 revised full papers together with 4 invited papers. All important issues in language theory are addressed including grammars, acceptors and transducers for strings, trees, graphs, arrays; efficient text algorithms; algebraic theories for automata and languages; and more.

Hex: The Full Story is for anyone - hobbyist, professional, student, teacher - who enjoys board games, game theory, discrete math, computing, or history. hex was discovered twice, in 1942 by Piet Hein and again in 1949 by John F. nash. How did this happen? Who created the puzzle for Hein's Danish newspaper column? How are Martin Gardner, David Gale, Claude Shannon, and Claude Berge involved? What is the secret to playing Hex well? The answers are inside... Features New documents on Hein's creation of Hex, the complete set of Danish puzzles, and the identity of their composer Chapters on Gale's game Bridg-it, the game Rex, computer Hex, open Hex problems, and more Dozens of new puzzles and solutions Study guide for Hex players Supplemenetary text for a course in game theory, discrete math, computer science, or science history

This is a classic introduction to set theory in three parts. The first part gives a general introduction to set theory, suitable for undergraduates; complete proofs are given and no background in logic is required. Exercises are included, and the more difficult ones are supplied with hints. An appendix to the first part gives a more formal foundation to axiomatic set theory, supplementing the intuitive introduction given in the first part. The final part gives an introduction to modern tools of combinatorial set theory. This part contains enough material for a graduate course of one or two semesters. The subjects discussed include stationary sets, delta systems, partition relations, set mappings, measurable and real-valued measurable cardinals. Two sections give an introduction to modern results on exponentiation of singular cardinals, and certain deeper aspects of the topics are developed in advanced problems.

This is a classic introduction to set theory, suitable for students with no previous knowledge of the subject. Providing complete, up-to-date coverage, the book is based in large part on courses given over many years by Professor Hajnal. The first part introduces all the standard notions of the subject; the second part concentrates on combinatorial set theory. Exercises are included throughout and a new section of hints has been added to assist the reader.

Building on fuzzy logic and evolutionary computing, this book introduces fuzzy cooperative coevolution as a novel approach to systems design, conductive to explaining human decision process. Fuzzy cooperative coevolution is a methodology for constructing systems able to accurately predict the outcome of a decision-making process, while providing an understandable explanation of the underlying reasoning.

The central contribution of this work is the use of an advanced evolutionary technique, cooperative coevolution, for dealing with the simultaneous design of connective and operational parameters. Cooperative coevolution overcomes several limitations exhibited by other standard evolutionary approaches.

The applicability of fuzzy cooperative coevolution is validated by modeling the decision processes of three real-world problems, an iris data benchmark problem and two problems from breast cancer diagnosis.

Together, Models and Computability and its sister volume Sets and Proofs will provide readers with a comprehensive guide to the current state of mathematical logic. All the authors are leaders in their fields and are drawn from the invited speakers at 'Logic Colloquium '97' (the major international meeting of the Association of Symbolic Logic). It is expected that the breadth and timeliness of these two volumes will prove an invaluable and unique resource for specialists, post-graduate researchers, and the informed and interested nonspecialist.

The 8th International Conference on Theory and Applications of Satis?ability Testing(SAT2005)providedaninternationalforumforthemostrecentresearch on the satis?ablity problem (SAT). SAT is the classic problem of determining whether or not a propositional formula has a satisfying truth assignment. It was the ?rst problem shown by Cook to be NP-complete. Despite its seemingly specialized nature, satis?ability testing has proved to extremely useful in a wide range of di?erent disciplines, both from a practical as well as from a theoretical point of view. For example, work on SAT continues to provide insight into various fundamental problems in computation, and SAT solving technology has advanced to the point where it has become the most e?ective way of solving a number of practical problems. The SAT series of conferences are multidisciplinary conferences intended to bring together researchers from various disciplines who are interested in SAT. Topics of interest include, but are not limited to: proof systems and proof c- plexity; search algorithms and heuristics; analysis of algorithms; theories beyond the propositional; hard instances and random formulae; problem encodings; - dustrial applications; solvers and other tools. This volume contains the papers accepted for presentation at SAT 2005. The conference attracted a record number of 73 submissions. Of these, 26 papers were accepted for presentation in the technical programme. In addition, 16 - pers were accepted as shorter papers and were presented as posters during the technicalprogramme.Theacceptedpapersandposterpaperscoverthefullrange of topics listed in the call for papers.

A First Course in Logic is an introduction to first-order logic suitable for first and second year mathematicians and computer scientists. There are three components to this course: propositional logic; Boolean algebras; and predicate/first-order, logic. Logic is the basis of proofs in mathematics - how do we know what we say is true? - and also of computer science - how do I know this program will do what I think it will? Surprisingly little mathematics is needed to learn and understand logic (this course doesn't involve any calculus). The real mathematical prerequisite is an ability to manipulate symbols: in other words, basic algebra. Anyone who can write programs should have this ability.

Semigroups, Automata, Universal Algebra, Varieties

This volume contains the proceedings of the 25th International Conference on Application and Theory of Petri Nets (ICATPN 2004). The aim of the Petri net conferences is to create a forum for discussing progress in the application and theory of Petri nets. Typically, the conferenceshave 100-150participants, one third of these c- ing from industry, whereas the others are from universities and research insti- tions. The conferences always take place in the last week of June. The conference and a number of other activities are coordinated by a ste- ing committee with the following members: Wil van der Aalst (The Neth- lands), JonathanBillington(Australia), JrgDesel(Germany), SusannaDonatelli (Italy), SergeHaddad(France), KurtJensen(Denmark), MaciejKoutny(United Kingdom), Sadatoshi Kumagai(Japan), GiorgioDe Michelis (Italy), Tadao- rata (USA), Carl Adam Petri (Germany, Honorary Member), Wolfgang Reisig (Germany), GrzegorzRozenberg(TheNetherlands, Chairman)andManuelSilva (Spain). The 2004 conference was organized by the Department of Computer Science of the University of Bologna, Italy. We would like to thank the organizing c- mittee, chaired by Roberto Gorrieri, for the e?ort invested in making the event successful. We are also grateful to the following sponsoring institutions and - ganizations: Associazione Italiana per l'Informatica ed il Calcolo Automatico (AICA), Microsoft Research, and Network Project & Solutions (NPS Group). We received a total of 62 submissions from 26 di?erent countries. The p- gramcommittee?nallyselected19regularpapersand5toolpresentationpapers. This volume comprises the papers that were accepted for presentation. Invited lectures were given by Gianfranco Ciardo, Roberto Gorrieri, Thomas A. H- zinger, Wojciech Penczek, Lucia Pomello and William H. Sanders. Their papers are also included in this volume.

The very ?rst model of concurrent and distributed systems was introduced by C.A. Petri in his seminal Ph.D. thesis in 1964. Petri nets has remained a central model for concurrentsystemsfor40 years,andthey areoften usedasa yardstick for other models of concurrency. As a matter of fact, many other models have been developed since then, and this research area is ?ourishing today. The goal of the 4th Advanced Course on Petri Nets held in Eichsta ..tt, Germany in September 2003 was to present applications and the theory of Petri Nets in the context of a whole range of other models. We believe that in this way the participants of the course received a broad and in-depth picture of research in concurrent and distributed systems. It is also the goal of this volume to convey this picture. The volume is based on lectures given at the Advanced Course, but in order to provide a balanced p- sentation of the ?eld, some of the lectures are not included, and some material not presented in Eichst. att is covered here. In particular, a series of introductory lectures was not included in this volume, as the material they covered is well - tablishedby now,andwellpresentedelsewhere (e.g.,inW. ReisigandG. Roz- berg, eds., "Lectures on Petri Nets," LNCS 1491, 1492, Springer-Verlag, 1997 - these two volumes are based on the 3rd Advanced Course on Petri Nets).

The Beauty of Mathematics in Computer Science explains the mathematical fundamentals of information technology products and services we use every day, from Google Web Search to GPS Navigation, and from speech recognition to CDMA mobile services. The book was published in Chinese in 2011 and has sold more than 600,000 copies. Readers were surprised to find that many daily-used IT technologies were so tightly tied to mathematical principles. For example, the automatic classification of news articles uses the cosine law taught in high school. The book covers many topics related to computer applications and applied mathematics including: Natural language processing Speech recognition and machine translation Statistical language modeling Quantitive measurement of information Graph theory and web crawler Pagerank for web search Matrix operation and document classification Mathematical background of big data Neural networks and Google's deep learning Jun Wu was a staff research scientist in Google who invented Google's Chinese, Japanese, and Korean Web Search Algorithms and was responsible for many Google machine learning projects. He wrote official blogs introducing Google technologies behind its products in very simple languages for Chinese Internet users from 2006-2010. The blogs had more than 2 million followers. Wu received PhD in computer science from Johns Hopkins University and has been working on speech recognition and natural language processing for more than 20 years. He was one of the earliest engineers of Google, managed many products of the company, and was awarded 19 US patents during his 10-year tenure there. Wu became a full-time VC investor and co-founded Amino Capital in Palo Alto in 2014 and is the author of eight books.

This book is devoted to the 6th International Conference on Theory and - plications of Satis?ability Testing (SAT 2003) held in Santa Margherita Ligure (Genoa,Italy), during May5-8,2003. SAT 2003followedthe WorkshopsonS- is?ability held in Siena (1996), Paderborn (1998), and Renesse (2000), and the Workshop on Theory and Applications of Satis?ability Testing held in Boston (2001) and in Cincinnati (2002). As in the last edition, the SAT event hosted a SAT solvers competition, and, starting from the 2003 edition, also a Quanti?ed Boolean Formulas (QBFs) solvers comparative evaluation. There were 67 submissions of high quality, authored by researchers from all over the world. All the submissions were thoroughly evaluated, and as a result 42 were selected for oral presentations, and 16 for a poster presentation. The presentations covered the whole spectrum of research in propositional and QBF satis?ability testing, including proof systems, search techniques, probabilistic analysis of algorithms and their properties, problem encodings, industrial app- cations, speci?c tools, case studies and empirical results. Further, the program was enriched by three invited talks, given by Riccardo Zecchina (on "Survey Propagation: from Analytic Results on Random k-SAT to a Message-Passing - gorithm for Satis?ability"), Toby Walsh (on "Challenges in SAT (and QBF)") and Wolfgang Kunz (on "ATPG Versus SAT: Comparing Two Paradigms for Boolean Reasoning"). SAT 2003 thus provided a unique forum for the presen- tion and discussion of research related to the theory and applications of pro- sitional and QBF satis?ability testing.

The aim of contextual logic is to provide a formal theory of elementary logic, which is based on the doctrines of concepts, judgements, and conclusions. Concepts are mathematized using Formal Concept Analysis (FCA), while an approach to the formalization of judgements and conclusions is conceptual graphs, based on Peirce's existential graphs. Combining FCA and a mathematization of conceptual graphs yields so-called concept graphs, which offer a formal and diagrammatic theory of elementary logic.

Expressing negation in contextual logic is a difficult task. Based on the author's dissertation, this book shows how negation on the level of judgements can be implemented. To do so, cuts (syntactical devices used to express negation) are added to concept graphs. As we can express relations between objects, conjunction and negation in judgements, and existential quantification, the author demonstrates that concept graphs with cuts have the expressive power of first-order predicate logic. While doing so, the author distinguishes between syntax and semantics, and provides a sound and complete calculus for concept graphs with cuts. The author's treatment is mathematically thorough and consistent, and the book gives the necessary background on existential and conceptual graphs.

This volume, "Petri Net Technology for Communication-Based Systems," is a state-of-the-artreportin the seriesAdvances in Petri Nets. It showshowvarious well-established and new Petri net notions and techniques can be used for m- elingcommunication-basedsystems, withspecialfocusonwork?owmanagement and business processes. In the last 6 years this topic has been studied by the DFG Forschergruppe Petri Net Technology in Berlin in close cooperation with the international c- munity. The main results of this cooperation were presented at the 1st and 2nd InternationalColloquiaonPetriNetTechnologiesforModelingCommunication- Based Systems, held in Berlin in 1999 and 2001, respectively. A careful selection of contributions by members of the DFG Forschergruppe and by international experts in this ?eld are presented in this volume. Taking into account the fru- ful discussions during the two colloquia and the cross-refereeing process for the accepted papers, a high degree of common understanding was achieved, leading to a highly comprehensive presentation in this volume. The topics of the papers in this volume can be roughly classi?ed into the following two areas: - Petri net technology and - application to communication-based systems. Since most papers comprise aspects of both areas, we chose an alphabetic order. However, in the following we give a rough overview of the contributions in both areas according to the main focus of the corresponding papers.

The main subjects of the Developments in Language Theory (DLT) conf- ence series are formal languages, automata, conventional and unconventional computation theory, and applications of automata and language theory. T- ical, but not exclusive, topics of interest include: grammars and acceptors for strings, graphs, and arrays; e?cient text algorithms; combinatorial and al- braic properties of languages; decision problems; relations to complexity theory andlogic;picturedescriptionandanalysis;cryptography;concurrency;andDNA and quantum computing. The members of the steering committee of DLT are: J. Berstel (Paris), M. Ito(Kyoto), W. Kuich(Vienna), G. P? aun(BucharestandSeville), A. Restivo (Palermo), G. Rozenberg (chair, Leiden), A. Salomaa (Turku) and W. Thomas (Aachen). The ?rst DLT conference was organized by G. Rozenberg and A. Salomaa in Turku in 1993. After this, the DLT conferences were held in every odd year: Magdeburg(1995), Thessaloniki(1997), Aachen(1999)andVienna(2001). Since 2001, a DLT conference has been organized in every odd year in Europe and in every even year outside Europe. The last two DLT conferences were organized in Kyoto, Japan in 2002 and Szeged, Hungary in 2003. The titles of the volumes of the past DLT conferences are the following: 1. Developments in Language Theory. At the Crossroads of Mathematics, C- puter Science and Biology (edited by G. Rozenberg and A. Salomaa) (1994) (World Scienti?c) 2. Developments in Language Theory II. At the Crossroads of Mathematics, Computer Science and Biology (edited by J. Dassow, G. Rozenberg and A. Salomaa) (1996) (World Scienti?c) 3. Proceedings of the Third International Conference on Developments in L- guageTheory(edite

The great three-volume Principia Mathematica (CUP 1927) is deservedly the most famous work ever written on the foundations of mathematics. Its aim is to deduce all the fundamental propositions of logic and mathematics from a small number of logical premises and primitive ideas, establishing that mathematics is a development of logic. This abridged text of Volume I contains the material that is most relevant to an introductory study of logic and the philosophy of mathematics (more advanced students will of course wish to refer to the complete edition). It contains the whole of the preliminary sections (which present the authors' justification of the philosophical standpoint adopted at the outset of their work); the whole of Part I (in which the logical properties of propositions, propositional functions, classes and relations are established); section A of Part II (dealing with unit classes and couples); and Appendices A and C (which give further developments of the argument on the theory of deduction and truth functions).

This text presents methods of modern set theory as tools that can be usefully applied to other areas of mathematics. The author describes numerous applications in abstract geometry and real analysis and, in some cases, in topology and algebra. The book begins with a tour of the basics of set theory, culminating in a proof of Zorn's Lemma and a discussion of some of its applications. The author then develops the notions of transfinite induction and descriptive set theory, with applications to the theory of real functions. The final part of the book presents the tools of "modern" set theory: Martin's Axiom, the Diamond Principle, and elements of forcing. Written primarily as a text for beginning graduate or advanced level undergraduate students, this book should also interest researchers wanting to learn more about set theoretical techniques applicable to their fields.

The refereed proceedings of the 24th International Conference on Applications and Theory of Petri Nets, ICATPN 2003, held in Eindhoven, The Netherlands, in June 2003. The 25 revised full papers presented together with 6 invited contributions were carefully reviewed and selected from 77 submissions. All current issues on research and development in the area of Petri nets are addressed, in particular concurrent systems design and analysis, model checking, networking, business process modeling, formal methods in software engineering, agent systems, systems specification, systems validation, discrete event systems, protocols, and prototyping.