Search

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

This book collects a selection of the articles presented at the virtual conference “Game Theory and Applications”, organized in St. Petersburg in the summer of 2022. The articles in this collection cover all the main applications of game theory, interpolating mathematical methods with economics, biology, sociology, mobile systems, and social networks. Scholars in the field will find this to be a valuable contribution.

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.

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.

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.

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

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.

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.

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

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.