The finite - infinite interplay is central in human thinking, from ancient philosophers and mathematicians (Zeno, Pythagoras), to modern mathe­ matics (Cantor, Hilbert) and computer science (Turing, Godel). Recent developments in mathematics and computer science suggest a) radically new answers to classical questions (e. g. , does infinity exist?, where does infinity come from?, how to reconcile the finiteness of the human brain with the infinity of ideas it produces?), b) new questions of debate (e. g. , what is the role played by randomness?, are computers capable of handling the infinity through unconventional media of computation?, how can one approximate efficiently the finite by the infinite and, conversely, the infinite by finite?). Distinguished authors from around the world, many of them architects of the mathematics and computer science for the new century, contribute to the volume. Papers are as varied as Professor Marcus' activity, to whom this volume is dedicated. They range from real analysis to DNA com­ puting, from linguistics to logic, from combinatorics on words to symbolic dynamics, from automata theory to geography, and so on, plus an incursion into the old history of conceptions about infinity and a list of philosophical "open problems". They are mainly mathematical and theoretical computer science texts, but not all of them are purely mathematical.

FA (DFA, NFA), PDA, LBA, Turing Machine

This book discusses the use of the real numbers in theorem proving. Typ­ ically, theorem provers only support a few 'discrete' datatypes such as the natural numbers. However the availability of the real numbers opens up many interesting and important application areas, such as the verification of float­ ing point hardware and hybrid systems. It also allows the formalization of many more branches of classical mathematics, which is particularly relevant for attempts to inject more rigour into computer algebra systems. Our work is conducted in a version of the HOL theorem prover. We de­ scribe the rigorous definitional construction of the real numbers, using a new version of Cantor's method, and the formalization of a significant portion of real analysis. We also describe an advanced derived decision procedure for the 'Tarski subset' of real algebra as well as some more modest but practically useful tools for automating explicit calculations and routine linear arithmetic reasoning.

This book contains the refereed proceedings of the 20th International Conference on Theorem Proving in Higher Order Logics, TPHOLs 2007, held in Kaiserslautern, Germany, September 2007. Among the topics of this volume are formal semantics of specification, modeling, and programming languages, specification and verification of hardware and software, formalization of mathematical theories, advances in theorem prover technology, as well as industrial application of theorem provers.

This Festschrift volume is published in memory of William W. McCune who passed away in 2011. William W. McCune was an accomplished computer scientist all around but especially a fantastic system builder and software engineer.
The volume includes 13 full papers, which are presenting research in all aspects of automated reasoning and its applications to mathematics. These papers have been thoroughly reviewed and selected out of 15 submissions received in response to the call for paper issued in September 2011. The topics covered are: strategies, indexing, superposition-based theorem proving, model building, application of automated reasoning to mathematics, as well as to program verification, data mining, and computer formalized mathematics.

Over time, basic research tends to lead to specialization – increasingly narrow t- ics are addressed by increasingly focussed communities, publishing in increasingly con ned workshops and conferences, discussing increasingly incremental contri- tions. Already the community of programming languages is split into various s- communities addressing different aspects and paradigms (functional, imperative, relational, and object-oriented). Only a few people manage to maintain a broader view, and even fewer step back in order to gain an understanding about the basic principles, their interrelation, and their impact in a larger context.

Fundamental Problems in Computing is in honor of Professor Daniel J. Rosenkrantz, a distinguished researcher in Computer Science. Professor Rosenkrantz has made seminal contributions to many subareas of Computer Science including formal languages and compilers, automata theory, algorithms, database systems, very large scale integrated systems, fault-tolerant computing and discrete dynamical systems. For many years, Professor Rosenkrantz served as the Editor-in-Chief of the Journal of the Association for Computing Machinery (JACM), a very prestigious archival journal in Computer Science. His contributions to Computer Science have earned him many awards including the Fellowship from ACM and the ACM SIGMOD Contributions Award.

Challenges arise when the size of a group of cooperating agents is scaled to hundreds or thousands of members. In domains such as space exploration, military and disaster response, groups of this size (or larger) are required to achieve extremely complex, distributed goals. To effectively and efficiently achieve their goals, members of a group need to cohesively follow a joint course of action while remaining flexible to unforeseen developments in the environment.

"I prefer to view formal methods as tools. the use of which might be helpful." E. W. Dijkstra Algebraic specifications are about to be accepted by industry. Many projects in which algebraic specifications have been used as a design tool have been carried out. What prevents algebraic specifications from breaking through is the absence of introductory descriptions and tools supporting the construction of algebraic specifications. On the one hand. interest from industry will stimulate people to make introductions and tools. whereas on the other hand the existence of introductions and tools will stimulate industry to use algebraic specifications.

The title of this book contains the words ALGORITHMIC LANGUAGE, in the singular. This is meant to convey the idea that it deals not so much with the diversity of program­ ming languages, but rather with their commonalities. The task of formal program develop­ It allows classifying ment proved to be the ideal frame for demonstrating this unity. concepts and distinguishing fundamental notions from notational features; and it leads immediately to a systematic disposition. This approach is supported by didactic, practical, and theoretical considerations.

We have all experienced delays and frustrations as a result of the notorious ‘computer glitch.’ However, the more dependent we become on computational systems in our daily lives, the more we must ensure that they are safe, reliable and user-friendly.

The LNCS journal Transactions on Rough Sets is devoted to the entire spectrum of rough sets related issues, from logical and mathematical foundations, through all aspects of rough set theory and its applications, such as data mining, knowledge discovery, and intelligent information processing, to relations between rough sets and other approaches to uncertainty, vagueness, and incompleteness, such as fuzzy sets and theory of evidence. Volume XVI includes extensions of papers from the Rough Sets and Knowledge Technology Conference which was held in Banff, Canada, in October 2011. In addition this book contains a long paper based on a PhD thesis. The papers cover both theory and applications of rough, fuzzy and near sets. They offer a continuation of a number of research streams which have grown out of the seminal work by Zdzislaw Pawlak during the first decade of the 21st century.

Computational logic is a fast-growing field with applications in artificial intelligence, constraint solving, and the design and verification of software and hardware systems. Written with graduate and advanced undergraduate students in mind, this textbook introduces computational logic from the foundations of first-order logic to state-of-the-art decision procedures for arithmetic, data structures, and combination theories.

Is the exponential function computable? Are union and intersection of closed subsets of the real plane computable? Are differentiation and integration computable operators? Is zero finding for complex polynomials computable? Is the Mandelbrot set decidable? And in case of computability, what is the computational complexity? Computable analysis supplies exact definitions for these and many other similar questions and tries to solve them.

Mathematical Logic for Computer Science is a mathematics textbook with theorems and proofs, but the choice of topics has been guided by the needs of computer science students. The method of semantic tableaux provides an elegant way to teach logic that is both theoretically sound and yet sufficiently elementary for undergraduates. To provide a balanced treatment of logic, tableaux are related to deductive proof systems.