This monograph is a slightly revised version of my PhD thesis [86], com pleted in the Department of Computer Science at the University of Edin burgh in June 1988, with an additional chapter summarising more recent developments. Some of the material has appeared in the form of papers [50,88]. The underlying theme of the monograph is the study of two classical problems: counting the elements of a finite set of combinatorial structures, and generating them uniformly at random. In their exact form, these prob lems appear to be intractable for many important structures, so interest has focused on finding efficient randomised algorithms that solve them ap proxim~ly, with a small probability of error. For most natural structures the two problems are intimately connected at this level of approximation, so it is natural to study them together. At the heart of the monograph is a single algorithmic paradigm: sim ulate a Markov chain whose states are combinatorial structures and which converges to a known probability distribution over them. This technique has applications not only in combinatorial counting and generation, but also in several other areas such as statistical physics and combinatorial optimi sation. The efficiency of the technique in any application depends crucially on the rate of convergence of the Markov chain.

Time is a fascinating subject and has long since captured mankind's imagination, from the ancients to modern man, both adult and child alike. It has been studied across a wide range of disciplines, from the natural sciences to philosophy and logic. Today, thirty plus years since Prior's work in laying out foundations for temporal logic, and two decades on from Pnueli's seminal work applying of temporal logic in specification and verification of computer programs, temporal logic has a strong and thriving international research community within the broad disciplines of computer science and artificial intelligence. Areas of activity include, but are certainly not restricted to: Pure Temporal Logic, e. g. temporal systems, proof theory, model theory, expressiveness and complexity issues, algebraic properties, application of game theory; Specification and Verification, e. g. of reactive systems, ofreal-time components, of user interaction, of hardware systems, techniques and tools for verification, execution and prototyping methods; Temporal Databases, e. g. temporal representation, temporal query ing, granularity of time, update mechanisms, active temporal data bases, hypothetical reasoning; Temporal Aspects in AI, e. g. modelling temporal phenomena, in terval temporal calculi, temporal nonmonotonicity, interaction of temporal reasoning with action/knowledge/belief logics, temporal planning; Tense and Aspect in Natural Language, e. g. models, ontologies, temporal quantifiers, connectives, prepositions, processing tempo ral statements; Temporal Theorem Proving, e. g. translation methods, clausal and non-clausal resolution, tableaux, automata-theoretic approaches, tools and practical systems."

This is a monograph about logic. Specifically, it presents the mathe matical theory of the logic of bunched implications, BI: I consider Bl's proof theory, model theory and computation theory. However, the mono graph is also about informatics in a sense which I explain. Specifically, it is about mathematical models of resources and logics for reasoning about resources. I begin with an introduction which presents my (background) view of logic from the point of view of informatics, paying particular attention to three logical topics which have arisen from the development of logic within informatics: * Resources as a basis for semantics; * Proof-search as a basis for reasoning; and * The theory of representation of object-logics in a meta-logic. The ensuing development represents a logical theory which draws upon the mathematical, philosophical and computational aspects of logic. Part I presents the logical theory of propositional BI, together with a computational interpretation. Part II presents a corresponding devel opment for predicate BI. In both parts, I develop proof-, model- and type-theoretic analyses. I also provide semantically-motivated compu tational perspectives, so beginning a mathematical theory of resources. I have not included any analysis, beyond conjecture, of properties such as decidability, finite models, games or complexity. I prefer to leave these matters to other occasions, perhaps in broader contexts.

I am very happy to have this opportunity to introduce Luca Vigano's book on Labelled Non-Classical Logics. I put forward the methodology of labelled deductive systems to the participants of Logic Colloquium'90 (Labelled Deductive systems, a Position Paper, In J. Oikkonen and J. Vaananen, editors, Logic Colloquium '90, Volume 2 of Lecture Notes in Logic, pages 66-68, Springer, Berlin, 1993), in an attempt to bring labelling as a recognised and significant component of our logic culture. It was a response to earlier isolated uses of labels by various distinguished authors, as a means to achieve local proof theoretic goals. Labelling was used in many different areas such as resource labelling in relevance logics, prefix tableaux in modal logics, annotated logic programs in logic programming, proof tracing in truth maintenance systems, and various side annotations in higher-order proof theory, arithmetic and analysis. This widespread local use of labels was an indication of an underlying logical pattern, namely the simultaneous side-by-side manipulation of several kinds of logical information. It was clear that there was a need to establish the labelled deductive systems methodology. Modal logic is one major area where labelling can be developed quickly and sys tematically with a view of demonstrating its power and significant advantage. In modal logic the labels can play a double role."

Readership This book is devoted to the study of compiler transformations that are needed to expose the parallelism hiddenin a program. This book is notan introductory book to parallel processing, nor is it an introductory book to parallelizing compilers. Weassume thatreaders are familiar withthebooks High Performance Compilers for Parallel Computingby Wolfe [121] and Super- compilers for Parallel and Vector Computers by Zima and Chapman [125], and that they want to know more about scheduling transformations. In this book we describe both task graph scheduling and loop nest scheduling. Taskgraphschedulingaims atexecuting tasks linked by prece- dence constraints; it is a run-time activity. Loop nest scheduling aims at ex- ecutingstatementinstances linked bydata dependences;it is a compile-time activity. We are mostly interested in loop nestscheduling,butwe also deal with task graph scheduling for two main reasons: (i) Beautiful algorithms and heuristics have been reported in the literature recently; and (ii) Several graphscheduling, like list scheduling, are the basis techniques used in task ofthe loop transformations implemented in loop nest scheduling. As for loop nest scheduling our goal is to capture in a single place the fantastic developments of the last decade or so. Dozens of loop trans- formations have been introduced (loop interchange, skewing, fusion, dis- tribution, etc.) before a unifying theory emerged. The theory builds upon the pioneering papers of Karp, Miller, and Winograd [65] and of Lam- port [75], and it relies on sophisticated mathematical tools (unimodular transformations, parametric integer linear programming, Hermite decom- position, Smithdecomposition, etc.).

This book is de- voted to some topical prob- lems and various applica- tions of Operator Theory and to its interplay with many other fields of analysis as modern approximation the- ory, theory of dynamic sys- tems, harmonic analysis and complex analysis. It consists of 20 carefully selected sur- veys and research-expository papers. Their scope gives a representative status report on the field drawing a pic- ture of a rapidly developing domain of analysis. An abun- dance of references completes the picture. All papers included in the volume originate from lectures delivered at the l1th edition of the International Workshop on Operator The- ory and its Applications (IWOTA-2000, June 13-16, Bordeaux). Some information about the conference, including the complete list of participants, can be found on forthcoming pages. The editors are indebted to A.Sudakov for helping them in polishing and assembling original TeX files. A. Borichev and N. Nikolski Talence, May 2001 v vii International Workshop on Operator Theory and Its Applications (June 13-June 16, 2000, Universite Bordeaux 1) The International Workshop on Operator Theory and its Applications (IWOTA) is a satellite meeting of the international symposium on the Mathe- matical Theory of Networks and Systems (MNTS). In 2000, the MNTS is held in Perpignan, France, June 19-23. IWOTA 2000 was the eleventh workshop of this kind.

The theoretical foundations of Neural Networks and Analog Computation conceptualize neural networks as a particular type of computer consisting of multiple assemblies of basic processors interconnected in an intricate structure. Examining these networks under various resource constraints reveals a continuum of computational devices, several of which coincide with well-known classical models. On a mathematical level, the treatment of neural computations enriches the theory of computation but also explicated the computational complexity associated with biological networks, adaptive engineering tools, and related models from the fields of control theory and nonlinear dynamics. The material in this book will be of interest to researchers in a variety of engineering and applied sciences disciplines. In addition, the work may provide the base of a graduate-level seminar in neural networks for computer science students.

It is said that business re-engineering is part of our transition to a post-industrial society. The purpose of this book is to present an approach to how to reorganize businesses using the discipline of software engineering as a guiding paradigm. The author's thesis is that software engineering provides the necessary analytical expertise for defining business processes and the tools to transform process descriptions to support systems.
The author begins by introducing the concepts and needs for business reengineering and principles and practice of software engineering. He then shows how by concentrating on processes, a business can define the information base required and how it is to be constructed. As a result, any manager or technically-minded person will learn how to implement the reengineering of a business.

The main TOPIC of this book is that of Groebner bases and their applications. The main PURPOSE of this book is that of bridging the current gap in the literature between theory and real computation. The book can be used by teachers and students alike as a comprehensive guide to both the theory and the practice of Computational Commutative Algebra. It has been made as self-contained as possible, and thus is ideally suited as a textbook for graduate or advanced undergraduate courses. Numerous applications are described, covering fields as disparate as algebraic geometry and financial markets. To aid a deeper understanding of these applications there are 44 tutorials aimed at illustrating how the theory can be used in these cases. The computational aspects of the tutorials can be carried out with the computer algebra system CoCoA, an introduction to which appears in an appendix. Besides the tutorials there are plenty of exercises, some of a theoretical nature and others more practical.

The past twenty years have shown a rapid growth in the theoretical understanding, useful applications and widespread acceptance of multigrid in the applied sciences, and new tasks continue to arise that are better addressed from a special multigrid point of view. These developments have served to make multigrid one of the key techniques in modern computing methods. Most prominent among the new issues are parallel computing and adaptive computations. Multigrid methods also have considerable impact on computational fluid dynamics. This influence is reflected in the present, carefully screened selection of contributions presented at the Fourth European Multigrid Conference in Amsterdam in 1993, all of which reflect the latest developments in this dynamic field.

Domain theory is a rich interdisciplinary area at the intersection of logic, computer science, and mathematics. This volume contains selected papers presented at the International Symposium on Domain Theory which took place in Shanghai in October 1999. Topics of papers range from the encounters between topology and domain theory, sober spaces, Lawson topology, real number computability and continuous functionals to fuzzy modelling, logic programming, and pi-calculi. This book is a valuable reference for researchers and students interested in this rapidly developing area of theoretical computer science.

Search games and rendezvous problems have received growing attention in computer science within the past few years. Rendezvous problems emerge naturally, for instance, to optimize performance and convergence of mobile robots. This gives a new algorithmic point of view to the theory. Furthermore, modern topics such as the spreading of gossip or disease in social networks have lead to new challenging problems in search and rendezvous.

"Search Theory: A Game Theoretic Perspective" introduces the first integrated approach to Search and Rendezvous from the perspectives ofbiologists, computer scientists and mathematicians. This contributed volume covers a wide range of topics including rendezvous problems and solutions, rendezvous on graphs, search games on biology, mobility in governed social networks, search and security, and more. Most chapters also include case studies or a survey, in addition to a chapter on the future direction of Search and Rendezvous research.

This book targets researchers and practitioners working in computer science, mathematics and biology as a reference book. Advanced level students focused on these fields will also find this book valuable as a secondary text book orreference."

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

The importance of having ef cient and effective methods for data mining and kn- ledge discovery (DM&KD), to which the present book is devoted, grows every day and numerous such methods have been developed in recent decades. There exists a great variety of different settings for the main problem studied by data mining and knowledge discovery, and it seems that a very popular one is formulated in terms of binary attributes. In this setting, states of nature of the application area under consideration are described by Boolean vectors de ned on some attributes. That is, by data points de ned in the Boolean space of the attributes. It is postulated that there exists a partition of this space into two classes, which should be inferred as patterns on the attributes when only several data points are known, the so-called positive and negative training examples. The main problem in DM&KD is de ned as nding rules for recognizing (cl- sifying) new data points of unknown class, i. e. , deciding which of them are positive and which are negative. In other words, to infer the binary value of one more attribute, called the goal or class attribute. To solve this problem, some methods have been suggested which construct a Boolean function separating the two given sets of positive and negative training data points.

Rubinstein is the pioneer of the well-known score function and cross-entropy methods.

Accessible to a broad audience of engineers, computer scientists, mathematicians, statisticians and in general anyone, theorist and practitioner, who is interested in smart simulation, fast optimization, learning algorithms, and image processing.

Per Martin-Loef's work on the development of constructive type theory has been of huge significance in the fields of logic and the foundations of mathematics. It is also of broader philosophical significance, and has important applications in areas such as computing science and linguistics. This volume draws together contributions from researchers whose work builds on the theory developed by Martin-Loef over the last twenty-five years. As well as celebrating the anniversary of the birth of the subject it covers many of the diverse fields which are now influenced by type theory. It is an invaluable record of areas of current activity, but also contains contributions from N. G. de Bruijn and William Tait, both important figures in the early development of the subject. Also published for the first time is one of Per Martin-Loef's earliest papers.

One of the key concerns in modern control theory is the design of steering strategies. The implementation of such strategies is done by a regulator. Presented here is a self-contained introduction to the mathematical background of this type of regulator design. The topics selected address the matter of greatest interest to the control community, at present, namely, when the design objective is the reduction of the influence of exogeneous disturbances upon the output of the system. In a first scenario the disturbance signal is regarded as a deterministic time series with known dynamics but unknown parameters. The design objective is then the asymptotic disturbance compensation. In a second scenario, no information about the disturbance signal is available apart from some bounds. Here, in an H-approach, control strategies are worked out which will prove efficient for all such disturbances. The intention of this book is to present ideas and methods on such a level that the beginning graduate student will be able to follow current research. New results are included, especially for nonlinear control systems, and as a service to the reader, an extensive appendix presents topics from linear algebra, invariant manifolds and calculus of variations, information which is hardly to be found in standard textbooks. Contents: Introduction * The problem of output regulation * Introduction * Problem statement * Output regulation via full information * Output regulation via full error feedback * A particular case * Well-posedness and robustness * The construction of a robust regulator * Disturbance attenuation via H-methods * Introduction * Problem statement * A characterization of the L2-gain of a linear system * Disturbance attenuation via full information * Disturbance attenuation via measured feedback * Full information regulators * Problem statement * Time-dependent control strategies * Examples * Time-independent control strategies * The local case * Nonlinear observers * Problem statement * Time-dependent observers * Error feedback regulators * Examples * Nonlinear H-techniques * Introduction * Construction of the saddle-point * The local scenario * Disturbance attenuation via linearization * Matrix equations * Linear matrix equations * Algebraic Riccati equations * Invariant manifolds * Existence theorem * Outflowing manifolds * Asymptotic phase * Convergence for T (1) * A special case * Dichotomies and Lyapunov functions * Hamilton-Jacobi-Bellman-Isaacs equation * Introduction * Method of characteristics * The equation of Isaacs * The Hamiltonian version of Isaacs' equation * Bibliography

This book offers a comprehensive collection of the most advanced numerical techniques for the efficient and effective solution of simulation and optimization problems governed by systems of time-dependent differential equations. The contributions present various approaches to time domain decomposition, focusing on multiple shooting and parareal algorithms. The range of topics covers theoretical analysis of the methods, as well as their algorithmic formulation and guidelines for practical implementation. Selected examples show that the discussed approaches are mandatory for the solution of challenging practical problems. The practicability and efficiency of the presented methods is illustrated by several case studies from fluid dynamics, data compression, image processing and computational biology, giving rise to possible new research topics. This volume, resulting from the workshop Multiple Shooting and Time Domain Decomposition Methods, held in Heidelberg in May 2013, will be of great interest to applied mathematicians, computer scientists and all scientists using mathematical methods.

This book examines how fuzzy methods can be employed to manage service levels in business and IT alignment. It starts by mapping the dependencies of service level agreements, coming up with gradual and bi-polar concepts to eventually classify the level of coupling by intuitionistic fuzzy sets. The second part presents an approach to analyze the impact of service failures using intuitionistic fuzzy methods (IFSFIA). Lastly, the third part of the book extends the concept towards business and IT-aligned service-level engineering and provides two use cases.

Authored by engineers for engineers, this book is designed to be a practical and easy-to-understand solution sourcebook for real-world high-resolution and spot-light SAR image processing. Widely-used algorithms are presented for both system errors and propagation phenomena as well as numerous formerly-classified image examples. As well as providing the details of digital processor implementation, the text presents the polar format algorithm and two modern algorithms for spot-light image formation processing - the range migration algorithm and the chirp scaling algorithm. Bearing practical needs in mind, the authors have included an entire chapter devoted to SAR system performance including image quality metrics and image quality assessment. Another chapter contains image formation processor design examples for two operational fine-resolution SAR systems. This is a reference for radar engineers, managers, system developers, and for students in high-resolution microwave imaging courses. It includes 662 equations, 265 figures, and 55 tables.

Machine learning methods are now an important tool for scientists, researchers, engineers and students in a wide range of areas. This book is written for people who want to adopt and use the main tools of machine learning, but aren't necessarily going to want to be machine learning researchers. Intended for students in final year undergraduate or first year graduate computer science programs in machine learning, this textbook is a machine learning toolkit. Applied Machine Learning covers many topics for people who want to use machine learning processes to get things done, with a strong emphasis on using existing tools and packages, rather than writing one's own code. A companion to the author's Probability and Statistics for Computer Science, this book picks up where the earlier book left off (but also supplies a summary of probability that the reader can use). Emphasizing the usefulness of standard machinery from applied statistics, this textbook gives an overview of the major applied areas in learning, including coverage of:* classification using standard machinery (naive bayes; nearest neighbor; SVM)* clustering and vector quantization (largely as in PSCS)* PCA (largely as in PSCS)* variants of PCA (NIPALS; latent semantic analysis; canonical correlation analysis)* linear regression (largely as in PSCS)* generalized linear models including logistic regression* model selection with Lasso, elasticnet* robustness and m-estimators* Markov chains and HMM's (largely as in PSCS)* EM in fairly gory detail; long experience teaching this suggests one detailed example is required, which students hate; but once they've been through that, the next one is easy* simple graphical models (in the variational inference section)* classification with neural networks, with a particular emphasis onimage classification* autoencoding with neural networks* structure learning

Advanced research on the description of distributed systems and on design calculi for software and hardware is presented in this volume. Distinguished researchers give an overview of the latest state of the art.

This thesis describes experimental work in the field of trapped-ion quantum computation. It outlines the theory of Raman interactions, examines the various sources of error in two-qubit gates, and describes in detail experimental explorations of the sources of infidelity in implementations of single- and two-qubit gates. Lastly, it presents an experimental demonstration of a mixed-species entangling gate.

Despite the ample number of articles on parallel-vector computational algorithms published over the last 20 years, there is a lack of texts in the field customized for senior undergraduate and graduate engineering research. Parallel-Vector Equation Solvers for Finite Element Engineering Applications aims to fill this gap, detailing both the theoretical development and important implementations of equation-solution algorithms. The mathematical background necessary to understand their inception balances well with descriptions of their practical uses. Illustrated with a number of state-of-the-art FORTRAN codes developed as examples for the book, Dr. Nguyen's text is a perfect choice for instructors and researchers alike.