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.

The International Congresses of Logic, Methodology and Philosophy of Science, which are held every fourth year, give a cross-section of ongoing research in logic and philosophy of science. Both the invited lectures and the many contributed papers are conductive to this end. At the 9th Congress held in Uppsala in 1991 there were 54 invited lectures and around 650 contributed papers divided into 15 different sections. Some of the speakers who presented contributed papers that attracted special interest were invited to submit their papers for publication, and the result is the present volume. A few papers appear here more or less as they were presented at the Congress whereas others are expansions or elaborations of the talks given at the Congress. A selection of this kind, containing 38 papers drawn from the 650 contributed papers presented at the Uppsala Congress, cannot do justice to all facets of the field as it appeared at the Congress. But it should allow the reader to get a representative survey of contemporary research in large areas of philosophical logic and philosophy of science. About half of the papers of the volume appear in sections listed at the Congress under the heading Philosophical and Foundational Problems about the Sciences. The section Foundations of Logic, Mathematics and Computer Science is represented by three papers, Foundations of Physical Sciences by six papers, Foundations of Biological Sciences by three papers, Foundations of Cognitive Science and AI by one paper, and Foundations of Linguistics by three papers.

The purpose of the book is to take stock of the situation concerning Algebra via Category Theory in the last fifteen years, where the new and synthetic notions of Mal'cev, protomodular, homological and semi-abelian categories emerged. These notions force attention on the fibration of points and allow a unified treatment of the main algebraic: homological lemmas, Noether isomorphisms, commutator theory.
The book gives full importance to examples and makes strong connections with Universal Algebra. One of its aims is to allow appreciating how productive the essential categorical constraint is: knowing an object, not from inside via its elements, but from outside via its relations with its environment.
The book is intended to be a powerful tool in the hands of researchers in category theory, homology theory and universal algebra, as well as a textbook for graduate courses on these topics.

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.

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

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.

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.

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.

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.

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;

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.