Search

In his 1979 essay The Postmodern Condition: A Report on Knowledge philosopher Jean-François Lyotard noted that the advent of the computer opened up a stage of progress in which knowledge has become a commodity. Modernity and postmodernity appear as two stages of a process resulting from the conflict of science and narrative. As science attempts to distance itself from narrative, it must create its own legitimacy. This paper takes up this challenge with a focus on the question of imagery. The image is precisely what modern science seeks to free itself from in its quest for absolute transparency. This transparency is examined from the perspective of architecture, drawing on arguments from philosophy, quantum mechanics, theology and information theory. Natural science in the context of postmodernism Quantum mechanics and information theory New volume in the Applied Virtuality Book Series ; In his 1979 essay The Postmodern Condition: A Report on Knowledge philosopher Jean-François Lyotard noted that the advent of the computer opened up a stage of progress in which knowledge has become a commodity. Modernity and postmodernity appear as two stages of a process resulting from the conflict of science and narrative. As science attempts to distance itself from narrative, it must create its own legitimacy. This paper takes up this challenge with a focus on the question of imagery. The image is precisely what modern science seeks to free itself from in its quest for absolute transparency. This transparency is examined from the perspective of architecture, drawing on arguments from philosophy, quantum mechanics, theology and information theory. Natural science in the context of postmodernism Quantum mechanics and information theory New volume in the Applied Virtuality Book Series, Naturwissenschaft im Zeichen der Postmoderne Quantenmechanik und Informationstheorie Neuer Band der Reihe Applied Virtuality Book Series In seinem 1979 erschienenen Essay Das postmoderne Wissen stellte Jean-François Lyotard fest, dass die Einführung des Computers ein Stadium des Fortschritts definiert, in dem Wissen zur Ware wird. Moderne und Postmoderne erscheinen als zwei Stadien eines Prozesses, der aus dem Konflikt der Wissenschaft mit den Narrativen resultiert: Während die Wissenschaft versucht, sich vom Narrativen zu distanzieren, muss sie ihre eigene Legitimation schaffen. Die vorliegende Abhandlung greift die Herausforderung im Zeichen des Bildes auf. Das Bild ist genau das, wovon sich die moderne Wissenschaft auf der Suche nach absoluter Transparenz zu befreien versucht. Diese Transparenz wird unter architektonischen Gesichtspunkten untersucht, die von der Philosophie bis zur Quantenmechanik, von der Theologie bis zur Informationstheorie reichen.

Symbolic rewriting techniques are methods for deriving consequences from systems of equations, and are of great use when investigating the structure of the solutions. Such techniques appear in many important areas of research within computer algebra: • the Knuth-Bendix completion for groups, monoids and general term-rewriting systems, • the Buchberger algorithm for Gröbner bases, • the Ritt-Wu characteristic set method for ordinary differential equations, and • the Riquier-Janet method for partial differential equations. This volume contains invited and contributed papers to the Symbolic Rewriting Techniques workshop, which was held at the Centro Stefano Franscini in Ascona, Switzerland, from April 30 to May 4, 1995. That workshop brought together 40 researchers from various areas of rewriting techniques, the main goal being the investigation of common threads and methods. Following the workshops, each contribution was formally refereed and 14 papers were selected for publication.

The twenty-six papers in this volume reflect the wide and still expanding range of Anil Nerode's work. A conference on Logical Methods was held in honor of Nerode's sixtieth birthday (4 June 1992) at the Mathematical Sciences Institute, Cornell University, 1-3 June 1992. Some of the conference papers are here, but others are from students, co-workers and other colleagues. The intention of the conference was to look forward, and to see the directions currently being pursued, in the development of work by, or with, Nerode. Here is a brief summary of the contents of this book. We give a retrospective view of Nerode's work. A number of specific areas are readily discerned: recursive equivalence types, recursive algebra and model theory, the theory of Turing degrees and r.e. sets, polynomial-time computability and computer science. Nerode began with automata theory and has also taken a keen interest in the history of mathematics. All these areas are represented. The one area missing is Nerode's applied mathematical work relating to the environment. Kozen's paper builds on Nerode's early work on automata. Recursive equivalence types are covered by Dekker and Barback, the latter using directly a fundamental metatheorem of Nerode. Recursive algebra is treated by Ge & Richards (group representations). Recursive model theory is the subject of papers by Hird, Moses, and Khoussainov & Dadajanov, while a combinatorial problem in recursive model theory is discussed in Cherlin & Martin's paper. Cenzer presents a paper on recursive dynamics.

A so-called'effective'algorithm may require arbitrarily large finite amounts of time and space resources, and hence may not be practical in the real world. A'feasible'algorithm is one which only requires a limited amount of space and/or time for execution; the general idea is that a feasible algorithm is one which may be practical on today's or at least tomorrow's computers. There is no definitive analogue of Church's thesis giving a mathematical definition of feasibility; however, the most widely studied mathematical model of feasible computability is polynomial-time computability. Feasible Mathematics includes both the study of feasible computation from a mathematical and logical point of view and the reworking of traditional mathematics from the point of view of feasible computation. The diversity of Feasible Mathematics is illustrated by the. contents of this volume which includes papers on weak fragments of arithmetic, on higher type functionals, on bounded linear logic, on sub recursive definitions of complexity classes, on finite model theory, on models of feasible computation for real numbers, on vector spaces and on recursion theory. The vVorkshop on Feasible Mathematics was sponsored by the Mathematical Sciences Institute and was held at Cornell University, June 26-28, 1989.

Mathematics and Computer Science III contains invited and contributed papers on combinatorics, random graphs and networks, algorithms analysis and trees, branching processes, constituting the Proceedings of the Third International Colloquium on Mathematics and Computer Science, held in Vienna in September 2004. It addresses a large public in applied mathematics, discrete mathematics and computer science, including researchers, teachers, graduate students and engineers.

The purpose of this annual series, Applied and Computational Control, Signals, and Circuits, is to keep abreast of the fast-paced developments in computational mathematics and scientific computing and their increasing use by researchers and engineers in control, signals, and circuits. The series is dedicated to fostering effective communication between mathematicians, computer scientists, computational scientists, software engineers, theorists, and practicing engineers. This interdisciplinary scope is meant to blend areas of mathematics (such as linear algebra, operator theory, and certain branches of analysis) and computational mathematics (numerical linear algebra, numerical differential equations, large scale and parallel matrix computations, numerical optimization) with control and systems theory, signal and image processing, and circuit analysis and design. The disciplines mentioned above have long enjoyed a natural synergy. There are distinguished journals in the fields of control and systems the­ ory, as well as signal processing and circuit theory, which publish high quality papers on mathematical and engineering aspects of these areas; however, articles on their computational and applications aspects appear only sporadically. At the same time, there has been tremendous recent growth and development of computational mathematics, scientific comput­ ing, and mathematical software, and the resulting sophisticated techniques are being gradually adapted by engineers, software designers, and other scientists to the needs of those applied disciplines.

Agent Cities [4] is an ambitious project whose main aim is the construction of a worldwide, publicly accessible network of agent-based FIPA platforms!. In March 2003 there are around 50 active platforms. Each of them supports agents that offer services similar to those that can be found in a real city (facilities, amenities, attractions, information and commercial services). It is expected that, in the near future, it will be possible to implement intelligent complex compound services (e.g. agents that are able to help a user to plan a weekend away, including tasks such as booking air tickets, selecting and booking a room in an appropriate hotel, buying tickets for the theatre and reserving a table in a restaurant that is near the theatre and offers the user's favourite meal). The main aim of our work was to develop a set of agents that could offer to the citizens and visitors of a city not the usual leisure-oriented services but health-care related services. This interest is related with previous work that our research group had done in the last years in the application of AI techniques (especially agent-based technology) to the medical domain (see e.g. [6]). Therefore, we decided to design and implement a multi-agent system with the following features: • The user may request information about all the medical centres available in a particular geographical area.

The field of computational learning theory arose out of the desire to for­ mally understand the process of learning. As potential applications to artificial intelligence became apparent, the new field grew rapidly. The learning of geo­ metric objects became a natural area of study. The possibility of using learning techniques to compensate for unsolvability provided an attraction for individ­ uals with an immediate need to solve such difficult problems. Researchers at the Center for Night Vision were interested in solving the problem of interpreting data produced by a variety of sensors. Current vision techniques, which have a strong geometric component, can be used to extract features. However, these techniques fall short of useful recognition of the sensed objects. One potential solution is to incorporate learning techniques into the geometric manipulation of sensor data. As a first step toward realizing such a solution, the Systems Research Center at the University of Maryland, in conjunction with the Center for Night Vision, hosted a Workshop on Learning and Geometry in January of 1991. Scholars in both fields came together to learn about each others'field and to look for common ground, with the ultimate goal of providing a new model of learning from geometrical examples that would be useful in computer vision. The papers in the volume are a partial record of that meeting.

This book is primarily a research monograph that presents in a unified man­ ner some recent research on a class of hybrid dynamical systems (HDS). The book is intended both for researchers and advanced postgraduate stu­ dents working in the areas of control engineering, theoretical computer science, or applied mathematics and with an interest in the emerging field of hybrid dynamical systems. The book assumes competence in the basic mathematical techniques of modern control theory. The material presented in this book derives from a period of fruitful research collaboration between the authors that began in 1994 and is still ongoing. Some of the material contained herein has appeared as isolated results in journal papers and conference proceedings. This work presents this material in an integrated and coherent manner and also presents many new results. Much of the material arose from joint work with students and colleagues, and the authors wish to acknowledge the major contributions made by Ian Petersen, Efstratios Skafidas, Valery Ugrinovskii, David Cook, Iven Mareels, and Bill Moran. There is currently no precise definition of a hybrid dynamical system; however, in broad terms it is a dynamical system that involves a mixture of discrete-valued and continuous-valued variables. Since the early 1990s, a bewildering array of results have appeared under the umbrella of HDS, ranging from the analysis of elementary on-off control systems to sophis­ ticated mathematical logic-based descriptions of large real-time software systems.

This is the first book that sums up test-related modeling of digital circuits and systems by a new structural-decision-diagrams model. The model represents structural and functional information jointly and opens a new area of research.The book introduces and discusses applications of two types of structural decision diagrams (DDs): low-level, structurally synthesized binary DDs (SSBDDs) and high-level DDs (HLDDs) that enable diagnostic modeling of complex digital circuits and systems.Topics and features:Provides the definition, properties and techniques for synthesis, compression and optimization of SSBDDs and HLDDsProvides numerous working examples that illustrate the key points of the textDescribes applications of SSBDDs and HLDDs for various electronic design automation (EDA) tasks, such as logic-level fault modeling and simulation, multi-valued simulation, timing-critical path identification, and test generationDiscusses the advantages of the proposed model to traditional binary decision diagrams and other traditional design representationsCombines SSBDDs with HLDDs for multi-level representation of digital systems for enabling hierarchical and cross-level solving of complex test-related tasksThis unique book is aimed at researchers working in the fields of computer science and computer engineering, focusing on test, diagnosis and dependability of digital systems. It can also serve as a reference for graduate- and advanced undergraduate-level computer engineering and electronics courses.Three authors are affiliated with the Dept. of Computer Systems at the Tallinn University of Technology, Estonia: Raimund Ubar is a retired Professor, Jaan Raik and Maksim Jenihhin are tenured Professors. Artur Jutman, PhD, is a researcher at the same university and the CEO of Testonica Lab Ltd., Estonia.

'An important topic, which is on the boundary between numerical analysis and computer science …. I found the book well written and containing much interesting material, most of the time disseminated in specialized papers published in specialized journals difficult to find. Moreover, there are very few books on these topics and they are not recent.'Numerical Algorithms (review of the first edition) This unique book provides concepts and background necessary to understand and build algorithms for computing the elementary functions. The author presents and structures the algorithms (hardware-oriented as well as software-oriented), and also discusses issues related to accurate floating-point implementation. The purpose is not to give'cookbook recipes'that allow one to implement a given function, but rather to provide the reader with tools necessary to build, or adapt, algorithms to their specific computing environment. The expanded second edition contains a number of revisions and additions, which incorporate numerous new results obtained during the last few years. New algorithms invented since 1997 – such as Matula's bipartite method, another table-based method due to Ercegovac, Lang, Tisserand, and Muller – as well as a new chapter on multiple-precision arithmetic have been added. In addition, the section on correct rounding of elementary functions has been fully reworked, also in the context of new results. Finally, the introductory presentation of floating-point arithmetic has been expanded, with more emphasis given to the use of the fused multiply-accumulate instruction. The book is an up-to-date presentation of information needed to understand and accurately use mathematical functions and algorithms in computational work and design. Graduates, professionals, and researchers in scientific computing, software engineering, and computer engineering will find the book a useful reference and resource.

Logicians have developed beautiful algorithmic techniques for the construction of computably enumerable sets. This textbook presents these techniques in a unified way that should appeal to computer scientists. Specifically, the book explains, organizes, and compares various algorithmic techniques used in computability theory (which was formerly called'classical recursion theory'). This area of study has produced some of the most beautiful and subtle algorithms ever developed for any problems. These algorithms are little-known outside of a niche within the mathematical logic community. By presenting them in a style familiar to computer scientists, the intent is to greatly broaden their influence and appeal. Topics and features: · All other books in this field focus on the mathematical results, rather than on the algorithms. · There are many exercises here, most of which relate to details of the algorithms. · The proofs involving priority trees are written here in greater detail, and with more intuition, than can be found elsewhere in the literature. · The algorithms are presented in a pseudocode very similar to that used in textbooks (such as that by Cormen, Leiserson, Rivest, and Stein) on concrete algorithms. · In addition to their aesthetic value, the algorithmic ideas developed for these abstract problems might find applications in more practical areas. Graduate students in computer science or in mathematical logic constitute the primary audience. Furthermore, when the author taught a one-semester graduate course based on this material, a number of advanced undergraduates, majoring in computer science or mathematics or both, took the course and flourished in it. Kenneth J. Supowit is an Associate Professor Emeritus, Department of Computer Science & Engineering, Ohio State University, Columbus, Ohio, US.

This unique textbook, in contrast to a standard logic text, provides the reader with a logic that actually can be used in practice to express and reason about mathematical ideas.The book is an introduction to simple type theory, a classical higher-order version of predicate logic that extends first-order logic. It presents a practice-oriented logic called Alonzo that is based on Alonzo Church's formulation of simple type theory known as Church's type theory. Unlike traditional predicate logics, Alonzo admits undefined expressions. The book illustrates, using Alonzo, how simple type theory is suited ideally for reasoning about mathematical structures and constructing libraries of mathematical knowledge.Topics and features:Offers the first book-length introduction to simple type theory as a predicate logicProvides the reader with a logic that is close to mathematical practicePresents the tools needed to build libraries of mathematical knowledgeEmploys two semantics, one for mathematics and one for logicEmphasizes the model-theoretic view of predicate logicIncludes several important topics, such as definite description and theory morphisms, not usually found in standard logic textbooksAimed at students of computing and mathematics at the graduate or upper-undergraduate level, this book is also well-suited for mathematicians, computing professionals, engineers, and scientists who need a practical logic for expressing and reasoning about mathematical ideas.William M. Farmer is a Professor in the Department of Computing and Software at McMaster University in Hamilton, Ontario, Canada.

-Ecclesiastes 12:12 Programs are invariably subjected to many rorms or transrormation. After an initial version of a program has been designed and developed, it undergoes debugging and certification. In addition, most long-lived pro­ grams have a liCe-cycle that includes modifications to meet amended specifications and extensions for expanded capabilities. Such evolution­ ary aspects of programming are the topic of this monograph. We present rormal methods for manipulating programs and illustrate their applica­ tion with numerous examples. Such methods could be incorporated in semi-automated programming environments, where they would serve to ease the burden on the programmer. We begin by describing a method whereby a given program that achieves one goal can be modified to achieve a different goal or a pro­ gram that computes wrong results can be debugged to achieve the 2 Preface intended results. The abstraction of a set of cognate programs to obtain a program schema, and the instantiation of abstract schemata to solve concrete problems, are approached from the same perspective. In addition, we describe synthesis rules for generating code from specifications and annotation rules for making assertions about code. The synthesis rules may be used when a program is first being developed, or when, in the course of modifying a program, the need arises to rewrite a program segment. Annotation rules may be used for the purpose of determining what an incorrect program really does before attempting to debug it or how a correct program works before attempting to modify it.

Perspicuity is part of proof. If the process by means of which I get a result were not surveyable, I might indeed make a note that this number is what comes out - but what fact is this supposed to confirm for me? I don't know'what is supposed to come out'.... 1 -L. Wittgenstein A feasible computation uses small resources on an abstract computa­ tion device, such as a'lUring machine or boolean circuit. Feasible math­ ematics concerns the study of feasible computations, using combinatorics and logic, as well as the study of feasibly presented mathematical structures such as groups, algebras, and so on. This volume contains contributions to feasible mathematics in three areas: computational complexity theory, proof theory and algebra, with substantial overlap between different fields. In computational complexity theory, the polynomial time hierarchy is characterized without the introduction of runtime bounds by the closure of certain initial functions under safe composition, predicative recursion on notation, and unbounded minimization (S. Bellantoni); an alternative way of looking at NP problems is introduced which focuses on which pa­ rameters of the problem are the cause of its computational complexity and completeness, density and separation/collapse results are given for a struc­ ture theory for parametrized problems (R. Downey and M. Fellows); new characterizations of PTIME and LINEAR SPACE are given using predicative recurrence over all finite tiers of certain stratified free algebras (D.

The elementary functions (sine, cosine, exponentials, logarithms...) are the most commonly used mathematical functions. Computing them quickly and accurately is a major goal in computer arithmetic. This book gives the theoretical background necessary to understand and/or build algorithms for computing these functions, presents algorithms (hardware-oriented as well as software-oriented), and discusses issues related to the accurate floating-point implementation of these functions. My purpose was not to give'cooking recipes'that allow to implement some given functions on some given floating-point systems, but to provide the reader with the knowledge that is necessary to build, or adapt algorithms to his or her computing environment. When writing this book, I have had in mind two different audiences: specialists, who will have to design floating-point systems (hardware or soft­ ware parts) orto do research on algorithms, and inquiring minds, who just want to know what kind of methods are used to compute the math functions in current computers or pocket calculators. Because of this, the book is in­ tended to be helpful as well for postgraduate and advanced undergraduate students in computer science or applied mathematics as for professionals engaged in the design of algorithms, programs or circuits that implement floating-point arithmetic, or simply for engineers or scientists who want to improve their culture in that domain.

These proceedings contain the main topics and results presented at the Fourth International Conference on Multivariate Approximation. The meeting took place during the week of September 24-29, 2000 at the now well-known'Haus Bommerholz', the guest-house of the University of Dortmund. It hosted 43 participants from 16 countries, and the program included 9 invited one-hour lectures, 21 contributed talks, and two problem sessions. The articles collected here are carefully peer-refereed and suitably edited for publication. Following the tradition of this series of conferences, the meeting was aimed at advancing selected topics of Multivariate Approximation Theory. These include approximation on compact sets (such as spheres, balls, or compact ho­ mogeneous manifolds), spherical designs and energy functionals, interpolation by radial basis functions and by splines, frame theory and Gabor analysis, re­ finable function systems and subdivision, properties of harmonic, polyharmonic and blending functions, sampling and data compression, among others. The editors would like to express their thanks to all who have given their sup­ port to the conference, and to the preparation of this book. In particular, our thanks go to the Deutsche Forschungsgemeinschaft for their funding of the con­ ference, to the University of Dortmund, and to the staff of Haus Bommerholz for their help running the conference, and to the Universities of Dortmund and Duisburg for the financial support of this proceedings volume.

Interest in the area of control of systems defined by partial differential Equations has increased strongly in recent years. A major reason has been the requirement of these systems for sensible continuum mechanical modelling and optimization or control techniques which account for typical physical phenomena. Particular examples of problems on which substantial progress has been made are the control and stabilization of mechatronic structures, the control of growth of thin films and crystals, the control of Laser and semi-conductor devices, and shape optimization problems for turbomachine blades, shells, smart materials and microdiffractive optics. This volume contains original articles by world reknowned experts in the fields of optimal control of partial differential equations, shape optimization, numerical methods for partial differential equations and fluid dynamics, all of whom have contributed to the analysis and solution of many of the problems discussed. The collection provides a state-of-the-art overview of the most challenging and exciting recent developments in the field. It is geared towards postgraduate students and researchers dealing with the theoretical and practical aspects of a wide variety of high technology problems in applied mathematics, fluid control, optimal design, and computer modelling.

Presenting mobile software agents for Internet service monitoring, this research monograph discusses newly standardized Internet technologies that allow service providers to offer secured Internet services with quality guarantees. Yet, today the customers of such services have no independent tool to verify (monitor) the service quality. This book shows why mobile software agents are best fit to fill the gap. Key features: - An introduction to standard Internet service enabling and managing technology such as IPSec, DiffServ and SNMP - A generic service monitoring architecture based on mobile agents - An object-oriented implementation of the architecture based on the Java programming language - Several implementations of mobile software agents that can monitor new and emerging Internet services such as virtual private networks (VPN) The book is addressed to mobile agent researchers looking for new and fruitful application areas. It will also be a valuable resource for innovative internet providers who are looking for a service monitoring infrastructure going beyond monthly reports.

One of the major concerns of theoretical computer science is the classifi­ cation of problems in terms of how hard they are. The natural measure of difficulty of a function is the amount of time needed to compute it (as a function of the length of the input). Other resources, such as space, have also been considered. In recursion theory, by contrast, a function is considered to be easy to compute if there exists some algorithm that computes it. We wish to classify functions that are hard, i.e., not computable, in a quantitative way. We cannot use time or space, since the functions are not even computable. We cannot use Turing degree, since this notion is not quantitative. Hence we need a new notion of complexity-much like time or spac~that is quantitative and yet in some way captures the level of difficulty (such as the Turing degree) of a function.

In this monograph we study two generalizations of standard unification, E-unification and higher-order unification, using an abstract approach orig­ inated by Herbrand and developed in the case of standard first-order unifi­ cation by Martelli and Montanari. The formalism presents the unification computation as a set of non-deterministic transformation rules for con­ verting a set of equations to be unified into an explicit representation of a unifier (if such exists). This provides an abstract and mathematically elegant means of analysing the properties of unification in various settings by providing a clean separation of the logical issues from the specification of procedural information, and amounts to a set of'inference rules'for unification, hence the title of this book. We derive the set of transformations for general E-unification and higher­ order unification from an analysis of the sense in which terms are'the same'after application of a unifying substitution. In both cases, this results in a simple extension of the set of basic transformations given by Herbrand­ Martelli-Montanari for standard unification, and shows clearly the basic relationships of the fundamental operations necessary in each case, and thus the underlying structure of the most important classes of term unifi­ cation problems.

The book introduces new techniques which imply rigorous lower bounds on the complexity of some number theoretic and cryptographic problems. These methods and techniques are based on bounds of character sums and numbers of solutions of some polynomial equations over finite fields and residue rings. It also contains a number of open problems and proposals for further research. We obtain several lower bounds, exponential in terms of logp, on the de­ grees and orders of • polynomials; • algebraic functions; • Boolean functions; • linear recurring sequences; coinciding with values of the discrete logarithm modulo a prime p at suf­ ficiently many points (the number of points can be as small as pI/He). These functions are considered over the residue ring modulo p and over the residue ring modulo an arbitrary divisor d of p - 1. The case of d = 2 is of special interest since it corresponds to the representation of the right­ most bit of the discrete logarithm and defines whether the argument is a quadratic residue. We also obtain non-trivial upper bounds on the de­ gree, sensitivity and Fourier coefficients of Boolean functions on bits of x deciding whether x is a quadratic residue. These results are used to obtain lower bounds on the parallel arithmetic and Boolean complexity of computing the discrete logarithm. For example, we prove that any unbounded fan-in Boolean circuit. of sublogarithmic depth computing the discrete logarithm modulo p must be of superpolynomial size.

'Classical and Quantum computing'provides a self-contained, systematic and comprehensive introduction to all the subjects and techniques important in scientific computing. The style and presentation are readily accessible to undergraduates and graduates. A large number of examples, accompanied by complete C++ and Java code wherever possible, cover every topic. Features and benefits:- Comprehensive coverage of the theory with many examples- Topics in classical computing include boolean algebra, gates, circuits, latches, error detection and correction, neural networks, Turing machines, cryptography, genetic algorithms - For the first time, genetic expression programming is presented in a textbook- Topics in quantum computing include mathematical foundations, quantum algorithms, quantum information theory, hardware used in quantum computingThis book serves as a textbook for courses in scientific computing and is also very suitable for self-study. Students, professionals and practitioners in computer science, applied mathematics and physics will benefit from using the book and the included software simulations.

In 1994 Peter Shor [65] published a factoring algorithm for a quantum computer that finds the prime factors of a composite integer N more efficiently than is possible with the known algorithms for a classical com­ puter. Since the difficulty of the factoring problem is crucial for the se­ curity of a public key encryption system, interest (and funding) in quan­ tum computing and quantum computation suddenly blossomed. Quan­ tum computing had arrived. The study of the role of quantum mechanics in the theory of computa­ tion seems to have begun in the early 1980s with the publications of Paul Benioff [6]'[7] who considered a quantum mechanical model of computers and the computation process. A related question was discussed shortly thereafter by Richard Feynman [35] who began from a different perspec­ tive by asking what kind of computer should be used to simulate physics. His analysis led him to the belief that with a suitable class of'quantum machines'one could imitate any quantum system.

Developments in both computer hardware and Perhaps the greatest impact has been felt by the software over the decades have fundamentally education community. Today, it is nearly changed the way people solve problems. impossible to find a college or university that has Technical professionals have greatly benefited not introduced mathematical computation in from new tools and techniques that have allowed some form, into the curriculum. Students now them to be more efficient, accurate, and creative have regular access to the amount of in their work. computational power that were available to a very exclusive set of researchers five years ago. This Maple V and the new generation of mathematical has produced tremendous pedagogical computation systems have the potential of challenges and opportunities. having the same kind of revolutionary impact as high-level general purpose programming Comparisons to the calculator revolution of the languages (e.g. FORTRAN, BASIC, C), 70's are inescapable. Calculators have application software (e.g. spreadsheets, extended the average person's ability to solve Computer Aided Design - CAD), and even common problems more efficiently, and calculators have had. Maple V has amplified our arguably, in better ways. Today, one needs at mathematical abilities: we can solve more least a calculator to deal with standard problems problems more accurately, and more often. In in life -budgets, mortgages, gas mileage, etc. specific disciplines, this amplification has taken For business people or professionals, the excitingly different forms.

From the original hard cover edition:In the modern age of almost universal computer usage, practically every individual in a technologically developed society has routine access to the most up-to-date cryptographic technology that exists, the so-called RSA public-key cryptosystem. A major component of this system is the factorization of large numbers into their primes. Thus an ancient number-theory concept now plays a crucial role in communication among millions of people who may have little or no knowledge of even elementary mathematics. Hans Riesel's highly successful first edition of this book has now been enlarged and updated with the goal of satisfying the needs of researchers, students, practitioners of cryptography, and non-scientific readers with a mathematical inclination. It includes important advances in computational prime number theory and in factorization as well as re-computed and enlarged tables, accompanied by new tables reflecting current research by both the author and his coworkers and by independent researchers. The book treats four fundamental problems: the number of primes below a given limit, the approximate number of primes, the recognition of primes and the factorization of large numbers. The author provides explicit algorithms and computer programs, and has attempted to discuss as many of the classically important results as possible, as well as the most recent discoveries. The programs include are written in PASCAL to allow readers to translate the programs into the language of their own computers. The independent structure of each chapter of the book makes it highly readable for a wide variety of mathematicians, students of applied number theory, and others interested in both study and research in number theory and cryptography. ​

Starting with Cook's pioneering work on NP-completeness in 1970, polynomial complexity theory, the study of polynomial-time com­ putability, has quickly emerged as the new foundation of algorithms. On the one hand, it bridges the gap between the abstract approach of recursive function theory and the concrete approach of analysis of algorithms. It extends the notions and tools of the theory of computability to provide a solid theoretical foundation for the study of computational complexity of practical problems. In addition, the theoretical studies of the notion of polynomial-time tractability some­ times also yield interesting new practical algorithms. A typical exam­ ple is the application of the ellipsoid algorithm to combinatorial op­ timization problems (see, for example, Lovasz [1986]). On the other hand, it has a strong influence on many different branches of mathe­ matics, including combinatorial optimization, graph theory, number theory and cryptography. As a consequence, many researchers have begun to re-examine various branches of classical mathematics from the complexity point of view. For a given nonconstructive existence theorem in classical mathematics, one would like to find a construc­ tive proof which admits a polynomial-time algorithm for the solution. One of the examples is the recent work on algorithmic theory of per­ mutation groups. In the area of numerical computation, there are also two tradi­ tionally independent approaches: recursive analysis and numerical analysis.

This book is a revised edition of the monograph which appeared under the same title in the series Research Notes in Theoretical Computer Science, Pit­ man, in 1986. In addition to a general effort to improve typography, English, and presentation, the main novelty of this second edition is the integration of some new material. Part of it is mine (mostly jointly with coauthors). Here is brief guide to these additions. I have augmented the account of categorical combinatory logic with a description of the confluence properties of rewriting systems of categor­ ical combinators (Hardin, Yokouchi), and of the newly developed cal­ culi of explicit substitutions (Abadi, Cardelli, Curien, Hardin, Levy, and Rios), which are similar in spirit to the categorical combinatory logic, but are closer to the syntax of A-calculus (Section 1.2). The study of the full abstraction problem for PCF and extensions of it has been enriched with a new full abstraction result: the model of sequential algorithms is fully abstract with respect to an extension of PCF with a control operator (Cartwright, Felleisen, Curien). An order­ extensional model of error-sensitive sequential algorithms is also fully abstract for a corresponding extension of PCF with a control operator and errors (Sections 2.6 and 4.1). I suggest that sequential algorithms lend themselves to a decomposition of the function spaces that leads to models of linear logic (Lamarche, Curien), and that connects sequentiality with games (Joyal, Blass, Abramsky) (Sections 2.1 and 2.6).

This monograph studies the logical aspects of domains as used in de­ notational semantics of programming languages. Frameworks of domain logics are introduced; these serve as foundations for systematic derivations of proof systems from denotational semantics of programming languages. Any proof system so derived is guaranteed to agree with denotational se­ mantics in the sense that the denotation of any program coincides with the set of assertions true of it. The study focuses on two categories for dena­ tational semantics: SFP domains, and the less standard, but important, category of stable domains. The intended readership of this monograph includes researchers and graduate students interested in the relation between semantics of program­ ming languages and formal means of reasoning about programs. A basic knowledge of denotational semantics, mathematical logic, general topology, and category theory is helpful for a full understanding of the material. Part I SFP Domains Chapter 1 Introduction This chapter provides a brief exposition to domain theory, denotational se­ mantics, program logics, and proof systems. It discusses the importance of ideas and results on logic and topology to the understanding of the relation between denotational semantics and program logics. It also describes the motivation for the work presented by this monograph, and how that work fits into a more general program. Finally, it gives a short summary of the results of each chapter. 1. 1 Domain Theory Programming languages are languages with which to perform computa­ tion.

This is the second volume in a series of innovative proceedings entirely devoted to the connections between mathematics and computer science. Here mathematics and computer science are directly confronted and joined to tackle intricate problems in computer science with deep and innovative mathematical approaches. The book serves as an outstanding tool and a main information source for a large public in applied mathematics, discrete mathematics and computer science, including researchers, teachers, graduate students and engineers. It provides an overview of the current questions in computer science and the related modern and powerful mathematical methods. The range of applications is very wide and reaches beyond computer science.

Interactive Operations Research with Maple: Methods and Models has two ob­ jectives: to provide an accelerated introduction to the computer algebra system Maple and, more importantly, to demonstrate Maple's usefulness in modeling and solving a wide range of operations research (OR) problems. This book is written in a format that makes it suitable for a one-semester course in operations research, management science, or quantitative methods. A nwnber of students in the departments of operations research, management science, oper­ ations management, industrial and systems engineering, applied mathematics and advanced MBA students who are specializing in quantitative methods or opera­ tions management will find this text useful. Experienced researchers and practi­ tioners of operations research who wish to acquire a quick overview of how Maple can be useful in solving OR problems will find this an excellent reference. Maple's mathematical knowledge base now includes calculus, linear algebra, ordinary and partial differential equations, nwnber theory, logic, graph theory, combinatorics, statistics and transform methods. Although Maple's main strength lies in its ability to perform symbolic manipulations, it also has a substantial knowledge of a large nwnber of nwnerical methods and can plot many different types of attractive-looking two-dimensional and three-dimensional graphs. After almost two decades of continuous improvement of its mathematical capabilities, Maple can now boast a user base of more than 300,000 academics, researchers and students in different areas of mathematics, science and engineering.

Structured matrices serve as a natural bridge between the areas of algebraic computations with polynomials and numerical matrix computations, allowing cross-fertilization of both fields. This book covers most fundamental numerical and algebraic computations with Toeplitz, Hankel, Vandermonde, Cauchy, and other popular structured matrices. Throughout the computations, the matrices are represented by their compressed images, called displacements, enabling both a unified treatment of various matrix structures and dramatic saving of computer time and memory. The resulting superfast algorithms allow further dramatic parallel acceleration using FFT and fast sine and cosine transforms. Included are specific applications to other fields, in particular, superfast solutions to: various fundamental problems of computer algebra; the tangential Nevanlinna--Pick and matrix Nehari problems The primary intended readership for this work includes researchers, algorithm designers, and advanced graduate students in the fields of computations with structured matrices, computer algebra, and numerical rational interpolation. The book goes beyond research frontiers and, apart from very recent research articles, includes yet unpublished results. To serve a wider audience, the presentation unfolds systematically and is written in a user-friendly engaging style. Only some preliminary knowledge of the fundamentals of linear algebra is required. This makes the material accessible to graduate students and new researchers who wish to study the rapidly exploding area of computations with structured matrices and polynomials. Examples, tables, figures, exercises, extensive bibliography, and index lend this text to classroom use or self-study.

Hundreds of novel and innovative computer algebra'recipes'will enable readers starting at the second year undergraduate level to easily and rapidly solve and explore most problems they encounter in their classical mechanics studies. Using the powerful computer algebra system MAPLE (Release 8) - no prior knowledge of MAPLE is presumed - the relevant command structures are explained on a need-to-know basis as the recipes are developed. This new problem-solving guide can serve in the classroom or for self-study, for reference, or as a text for an on-line course.

Philosophy of the Text This text presents an introductory survey of the basic concepts and applied mathematical methods of nonlinear science as well as an introduction to some simple related nonlinear experimental activities. Students in engineering, phys­ ics, chemistry, mathematics, computing science, and biology should be able to successfully use this book. In an effort to provide the reader with a cutting edge approach to one of the most dynamic, often subtle, complex, and still rapidly evolving, areas of modern research-nonlinear physics-we have made extensive use of the symbolic, numeric, and plotting capabilities of the Maple software sys­ tem applied to examples from these disciplines. No prior knowledge of Maple or computer programming is assumed, the reader being gently introduced to Maple as an auxiliary tool as the concepts of nonlinear science are developed. The CD-ROM provided with this book gives a wide variety of illustrative non­ linear examples solved with Maple. In addition, numerous annotated examples are sprinkled throughout the text and also placed on the CD. An accompanying set of experimental activities keyed to the theory developed in Part I of the book is given in Part II. These activities allow the student the option of'hands on'experience in exploring nonlinear phenomena in the REAL world. Although the experiments are easy to perform, they give rise to experimental and theoretical complexities which are not to be underestimated.

Advancements in digital sensor technology, digital image analysis techniques, as well as computer software and hardware have brought together the fields of computer vision and photogrammetry, which are now converging towards sharing, to a great extent, objectives and algorithms. The potential for mutual benefits by the close collaboration and interaction of these two disciplines is great, as photogrammetric know-how can be aided by the most recent image analysis developments in computer vision, while modern quantitative photogrammetric approaches can support computer vision activities. Devising methodologies for automating the extraction of man-made objects (e.g. buildings, roads) from digital aerial or satellite imagery is an application where this cooperation and mutual support is already reaping benefits. The valuable spatial information collected using these interdisciplinary techniques is of improved qualitative and quantitative accuracy. This book offers a comprehensive selection of high-quality and in-depth contributions from world-wide leading research institutions, treating theoretical as well as implementational issues, and representing the state-of-the-art on this subject among the photogrammetric and computer vision communities.

Humanity's most basic intellectual quest to decipher nature and master it has led to numerous efforts to build machines that simulate the world or communi­ cate with it [Bus70, Tur36, MP43, Sha48, vN56, Sha41, Rub89, NK91, Nyc92]. The computational power and dynamic behavior of such machines is a central question for mathematicians, computer scientists, and occasionally, physicists. Our interest is in computers called artificial neural networks. In their most general framework, neural networks consist of assemblies of simple processors, or'neurons,'each of which computes a scalar activation function of its input. This activation function is nonlinear, and is typically a monotonic function with bounded range, much like neural responses to input stimuli. The scalar value produced by a neuron affects other neurons, which then calculate a new scalar value of their own. This describes the dynamical behavior of parallel updates. Some of the signals originate from outside the network and act as inputs to the system, while other signals are communicated back to the environment and are thus used to encode the end result of the computation.

'This is a delightful little paperback which presents a day-by-day transcription of a course taught jointly by Pólya and Tarjan at Stanford University. Woods, the teaching assistant for the class, did a very good job of merging class notes into an interesting mini-textbook; he also included the exercises, homework, and tests assigned in the class (a very helpful addition for other instructors in the field). The notes are very well illustrated throughout and Woods and the Birkhäuser publishers produced a very pleasant text. One can count on [Pólya and Tarjan] for new insights and a fresh outlook. Both instructors taught by presenting a succession of examples rather than by presenting a body of theory…[The book] is very well suited as supplementary material for any introductory class on combinatorics; as such, it is very highly recommended. Finally, for all of us who like the topic and delight in observing skilled professionals at work, this book is entertaining and, yes, instructive, reading.'Mathematical Reviews (Review of the original hardcover edition)'The mathematical community welcomes this book as a final contribution to honour the teacher G. Pólya.'Zentralblatt MATH (Review of the original hardcover edition)

There is a growing interest in the use of ontologies for multi-agent system app- cations. On the one hand, the agent paradigm is successfully employed in those applications where autonomous, loosely-coupled, heterogeneous, and distributed systems need to interoperate in order to achieve a common goal. On the other hand, ontologies have established themselves as a powerful tool to enable kno- edge sharing, and a growing number of applications have bene?ted from the use of ontologies as a means to achieve semantic interoperability among heterogeneous, distributed systems. In principle ontologies and agents are a match made in heaven, that has failed to happen. What makes a simple piece of software an agent is its ability to communicate in a ”social” environment, to make autonomous decisions, and to be proactive on behalf of its user. Communication ultimately depends on und- standing the goals, preferences, and constraints posed by the user. Autonomy is theabilitytoperformataskwithlittleornouserintervention,whileproactiveness involves acting autonomously with no need for user prompting. Communication, but also autonomy and proactiveness, depend on knowledge. The ability to c- municate depends on understanding the syntax (terms and structure) and the semantics of a language. Ontologies provide the terms used to describe a domain and the semantics associated with them. In addition, ontologies are often comp- mented by some logical rules that constrain the meaning assigned to the terms. These constraints are represented by inference rules that can be used by agents to perform the reasoning on which autonomy and proactiveness are based.

Constraint satisfaction problems are significant in the domain of automated reasoning for artificial intelligence. They can be applied to the modeling and solving of a wide range of combinatorial applications such as planning, scheduling and resource sharing in a variety of practical domains such as transportation, production, supply-chains, network management and human resource management. In this book we study new techniques for solving constraint satisfaction problems, with a special focus on solution adaptation applied to agent reasoning.

Building effective and user-friendly transportation systems is one of the big challenges for engineers in the 21st century. There is an increasing need to understand, model, and govern such systems at both the individual (micro) and the society (macro) level. Still, this raises significant technical problems, as transportation systems may contain thousands of autonomous,'intelligent'entities that need to be simulated and/or controlled. Therefore, traffic and transportation scenarios are extraordinarily appealing for Distributed Artificial Intelligence, and (multi-) agent technology in particular. This book gives an overview of recent advances in agent-based transportation systems. It includes both a state-of-the-art survey and reports on cutting-edge research in the field.

'...A comprehensive, complete and clear exposition that serves as an excellent foundation for more advanced topics in system theory and control.'- IEEE Transactions on Automatic Control'[The authors] have contributed an expertly written and high quality textbook...and are to be congratulated.... Because of its mathematical sophistication and completeness the present book is highly recommended for use, both as a textbook as well as a reference.'- Automatica Linear systems theory plays a broad and fundamental role in electrical, mechanical, chemical and aerospace engineering, communications, and signal processing. A thorough introduction to systems theory with emphasis on control is presented in this self-contained textbook. The book examines the fundamental properties that govern the behavior of systems by developing their mathematical descriptions. Linear time-invariant, time-varying, continuous-time, and discrete-time systems are covered. Rigorous development of classic and contemporary topics in linear systems, as well as extensive coverage of stability and polynomial matrix/fractional representation, provide the necessary foundation for further study of systems and control. Linear Systems is written as a textbook for a challenging one-semester graduate course; a solutions manual is available to instructors upon adoption of the text. The book's flexible coverage and self-contained presentation also make it an excellent reference guide or self-study manual. For a treatment of linear systems that focuses primarily on the time-invariant case using streamlined presentation of the material with less formal and more intuitive proofs, see the authors'companion book entitled A Linear Systems Primer.

The theory of finite automata on finite stings, infinite strings, and trees has had a dis­ tinguished history. First, automata were introduced to represent idealized switching circuits augmented by unit delays. This was the period of Shannon, McCullouch and Pitts, and Howard Aiken, ending about 1950. Then in the 1950s there was the work of Kleene on representable events, of Myhill and Nerode on finite coset congruence relations on strings, of Rabin and Scott on power set automata. In the 1960s, there was the work of Btichi on automata on infinite strings and the second order theory of one successor, then Rabin's 1968 result on automata on infinite trees and the second order theory of two successors. The latter was a mystery until the introduction of forgetful determinacy games by Gurevich and Harrington in 1982. Each of these developments has successful and prospective applications in computer science. They should all be part of every computer scientist's toolbox. Suppose that we take a computer scientist's point of view. One can think of finite automata as the mathematical representation of programs that run us­ ing fixed finite resources. Then Btichi's SIS can be thought of as a theory of programs which run forever (like operating systems or banking systems) and are deterministic. Finally, Rabin's S2S is a theory of programs which run forever and are nondeterministic. Indeed many questions of verification can be decided in the decidable theories of these automata.