This IMA Volume in Mathematics and its Applications Coding Theory and Design Theory Part I: Coding Theory is based on the proceedings of a workshop which was an integral part of the 1987-88 IMA program on APPLIED COMBINATORICS. We are grateful to the Scientific Committee: Victor Klee (Chairman), Daniel Kleitman, Dijen Ray-Chaudhuri and Dennis Stanton for planning and implementing an exciting and stimulating year long program. We especially thank the Workshop Organizer, Dijen Ray-Chaudhuri, for organizing a workshop which brought together many of the major figures in a variety of research fields in which coding theory and design theory are used. A vner Friedman Willard Miller, Jr. PREFACE Coding Theory and Design Theory are areas of Combinatorics which found rich applications of algebraic structures. Combinatorial designs are generalizations of finite geometries. Probably, the history of Design Theory begins with the 1847 pa per of Reverand T. P. Kirkman "On a problem of Combinatorics," Cambridge and Dublin Math. Journal. The great Statistician R. A. Fisher reinvented the concept of combinatorial 2-design in the twentieth century. Extensive application of alge braic structures for construction of 2-designs (balanced incomplete block designs) can be found in R. C. Bose's 1939 Annals of Eugenics paper, "On the construction of balanced incomplete block designs." Coding Theory and Design Theory are closely interconnected. Hamming codes can be found (in disguise) in R. C. Bose's 1947 Sankhya paper "Mathematical theory of the symmetrical factorial designs.""

In April of 1996 an array of mathematicians converged on Cambridge, Massachusetts, for the Rotafest and Umbral Calculus Workshop, two con ferences celebrating Gian-Carlo Rota's 64th birthday. It seemed appropriate when feting one of the world's great combinatorialists to have the anniversary be a power of 2 rather than the more mundane 65. The over seventy-five par ticipants included Rota's doctoral students, coauthors, and other colleagues from more than a dozen countries. As a further testament to the breadth and depth of his influence, the lectures ranged over a wide variety of topics from invariant theory to algebraic topology. This volume is a collection of articles written in Rota's honor. Some of them were presented at the Rotafest and Umbral Workshop while others were written especially for this Festschrift. We will say a little about each paper and point out how they are connected with the mathematical contributions of Rota himself."

This present volume is the Proceedings of the 14th International Conference on Near rings and Nearfields held in Hamburg at the Universitiit der Bundeswehr Hamburg, from July 30 to August 06, 1995. This Conference was attended by 70 mathematicians and many accompanying persons who represented 22 different countries from all five continents. Thus it was the largest conference devoted entirely to nearrings and nearfields. The first of these conferences took place in 1968 at the Mathematische For schungsinstitut Oberwolfach, Germany. This was also the site of the conferences in 1972, 1976, 1980 and 1989. The other eight conferences held before the Hamburg Conference took place in eight different countries. For details about this and, more over, for a general historical overview of the development of the subject, we refer to the article "On the beginnings and development of near-ring theory" by G. Betsch [3]. During the last forty years the theory of nearrings and related algebraic struc tures like nearfields, nearmodules, nearalgebras and seminearrings has developed into an extensive branch of algebra with its own features. In its position between group theory and ring theory, this relatively young branch of algebra has not only a close relationship to these two more well-known areas of algebra, but it also has, just as these two theories, very intensive connections to many further branches of mathematics.

This volume presents a collection of papers on game theory dedicated to Michael Maschler. Through his dedication and contributions to game theory, Maschler has become an important figure particularly in the area of cooperative games. Game theory has since become an important subject in operations research, economics and management science. As befits such a volume, the main themes covered are cooperative games, coalitions, repeated games, and a cost allocation games. All the contributions are authoritative surveys of a particular topic, so together they will present an invaluable overview of the field to all those working on game theory problems.

These are the proceedings of the conference "Symbolic Computation, Number Theory, Special Functions, Physics and Combinatorics" held at the Department of Mathematics, University of Florida, Gainesville, from November 11 to 13, 1999. The main emphasis of the conference was Com puter Algebra (i. e. symbolic computation) and how it related to the fields of Number Theory, Special Functions, Physics and Combinatorics. A subject that is common to all of these fields is q-series. We brought together those who do symbolic computation with q-series and those who need q-series in cluding workers in Physics and Combinatorics. The goal of the conference was to inform mathematicians and physicists who use q-series of the latest developments in the field of q-series and especially how symbolic computa tion has aided these developments. Over 60 people were invited to participate in the conference. We ended up having 45 participants at the conference, including six one hour plenary speakers and 28 half hour speakers. There were talks in all the areas we were hoping for. There were three software demonstrations."

This book presents a collection of papers from the Spring 1995 Work shop on Computational Approaches to Processing the Prosody of Spon taneous Speech, hosted by the ATR Interpreting Telecommunications Re search Laboratories in Kyoto, Japan. The workshop brought together lead ing researchers in the fields of speech and signal processing, electrical en gineering, psychology, and linguistics, to discuss aspects of spontaneous speech prosody and to suggest approaches to its computational analysis and modelling. The book is divided into four sections. Part I gives an overview and theoretical background to the nature of spontaneous speech, differentiating it from the lab-speech that has been the focus of so many earlier analyses. Part II focuses on the prosodic features of discourse and the structure of the spoken message, Part ilIon the generation and modelling of prosody for computer speech synthesis. Part IV discusses how prosodic information can be used in the context of automatic speech recognition. Each section of the book starts with an invited overview paper to situate the chapters in the context of current research. We feel that this collection of papers offers interesting insights into the scope and nature of the problems concerned with the computational analysis and modelling of real spontaneous speech, and expect that these works will not only form the basis of further developments in each field but also merge to form an integrated computational model of prosody for a better understanding of human processing of the complex interactions of the speech chain."

The title of this book, Learning Discrete Mathematics with ISETL raises two issues. We have chosen the word "Learning" rather than "Teaching" because we think that what the student does in order to learn is much more important than what the professor does in order to teach. Academia is filled with outstanding mathematics teachers: excellent expositors, good organizers, hard workers, men and women who have a deep understanding of Mathematics and its applications. Yet, when it comes to ideas in Mathe matics, our students do not seem to be learning. It may be that something more is needed and we have tried to construct a book that might provide a different kind of help to the student in acquiring some of the fundamental concepts of Mathematics. In a number of ways we have made choices that seem to us to be the best for learning, even if they don't always completely agree with standard teaching practice. A second issue concerns students' writing programs. ISETL is a pro gramming language and by the phrase "with ISETL" in the title, we mean that our intention is for students to write code, think about what they have written, predict its results, and run their programs to check their predic tions. There is a trade-off here. On the one hand, it can be argued that students' active involvement with constructing Mathematics for themselves and solving problems is essential to understanding concepts."

Mathematical Foundations of Computer Science, Volume I is the first of two volumes presenting topics from mathematics (mostly discrete mathematics) which have proven relevant and useful to computer science. This volume treats basic topics, mostly of a set-theoretical nature (sets, functions and relations, partially ordered sets, induction, enumerability, and diagonalization) and illustrates the usefulness of mathematical ideas by presenting applications to computer science. Readers will find useful applications in algorithms, databases, semantics of programming languages, formal languages, theory of computation, and program verification. The material is treated in a straightforward, systematic, and rigorous manner. The volume is organized by mathematical area, making the material easily accessible to the upper-undergraduate students in mathematics as well as in computer science and each chapter contains a large number of exercises. The volume can be used as a textbook, but it will also be useful to researchers and professionals who want a thorough presentation of the mathematical tools they need in a single source. In addition, the book can be used effectively as supplementary reading material in computer science courses, particularly those courses which involve the semantics of programming languages, formal languages and automata, and logic programming.

"Singular Loci of Schubert Varieties" is a unique work at the crossroads of representation theory, algebraic geometry, and combinatorics. Over the past 20 years, many research articles have been written on the subject in notable journals. In this work, Billey and Lakshmibai have recreated and restructured the various theories and approaches of those articles and present a clearer understanding of this important subdiscipline of Schubert varieties - namely singular loci. The main focus, therefore, is on the computations for the singular loci of Schubert varieties and corresponding tangent spaces. The methods used include standard monomial theory, the nil Hecke ring, and Kazhdan-Lusztig theory. New results are presented with sufficient examples to emphasize key points. A comprehensive bibliography, index, and tables - the latter not to be found elsewhere in the mathematics literature - round out this concise work. After a good introduction giving background material, the topics are presented in a systematic fashion to engage a wide readership of researchers and graduate students.

This book provides users with cutting edge methods and technologies in the area of big data and visual analytics, as well as an insight to the big data and data analytics research conducted by world-renowned researchers in this field. The authors present comprehensive educational resources on big data and visual analytics covering state-of-the art techniques on data analytics, data and information visualization, and visual analytics. Each chapter covers specific topics related to big data and data analytics as virtual data machine, security of big data, big data applications, high performance computing cluster, and big data implementation techniques. Every chapter includes a description of an unique contribution to the area of big data and visual analytics. This book is a valuable resource for researchers and professionals working in the area of big data, data analytics, and information visualization. Advanced-level students studying computer science will also find this book helpful as a secondary textbook or reference.

Efficient transfer between science and society is crucial for their future development. The rapid progress of information technology and computer systems offers a large potential and new perspectives for solving complex problems. Mathematical modelling and simulation have become important tools not only in scientific investigations but also in analysing, planning and controlling technological and economic processes. Mathematics, imbedded in an interdisciplinary concept, has become a key technology.

The book covers the results of a variety of major projects in industrial mathematics following an initiative of the German Federal Ministry of Education and Research. All projects are collaborations of industrial companies and university-based researchers, and range from automotive industry to computer technology and medical visualisation. In general, the projects presented in this volume prove that new mathematical ideas and methods can be decisive for the solution of industrial and economic problems.

Computational geometry as an area of research in its own right emerged in the early seventies of this century. Right from the beginning, it was obvious that strong connections of various kinds exist to questions studied in the considerably older field of combinatorial geometry. For example, the combinatorial structure of a geometric problem usually decides which algorithmic method solves the problem most efficiently. Furthermore, the analysis of an algorithm often requires a great deal of combinatorial knowledge. As it turns out, however, the connection between the two research areas commonly referred to as computa tional geometry and combinatorial geometry is not as lop-sided as it appears. Indeed, the interest in computational issues in geometry gives a new and con structive direction to the combinatorial study of geometry. It is the intention of this book to demonstrate that computational and com binatorial investigations in geometry are doomed to profit from each other. To reach this goal, I designed this book to consist of three parts, acorn binatorial part, a computational part, and one that presents applications of the results of the first two parts. The choice of the topics covered in this book was guided by my attempt to describe the most fundamental algorithms in computational geometry that have an interesting combinatorial structure. In this early stage geometric transforms played an important role as they reveal connections between seemingly unrelated problems and thus help to structure the field."

The theory of Groebner bases is a main tool for dealing with rings of differential operators. This book reexamines the concept of Groebner bases from the point of view of geometric deformations. The algorithmic methods introduced in this book are particularly useful for studying the systems of multidimensional hypergeometric PDE's introduced by Gelfand, Kapranov, and Zelevinsky. A number of original research results are contained in the book, and many open problems are raised for future research in this rapidly growing area of computational mathematics.

Taking into account the various criss-crossing among mathematical subject, Physical Combinatorics presents new results and exciting ideas from three viewpoints; representation theory, integrable models, and combinatorics. This work is concerned with combinatorial aspects arising in the theory of exactly solvable models and representation theory. Recent developments in integrable models reveal an unexpected link between representation theory and statistical mechanics through combinatorics.

Dedicated to Arto Salomaa, a towering figure of theoretical computer science, on the occasion of his 65th birthday, this book is a tribute to him on behalf of the theoretical computer science community. The contributions are written by internationally recognized scientists and cover most of Salomaa's many research areas. Due to its representative selection of classic and cutting edge trends in theoretical computer science, the book constitutes a comprehensive state-of-the-art survey. The contributions are in such central areas as automata theory, algorithms and complexity, and combinatorics of words. But not only that, they take up new areas such as regular sets and biocomputing. While some are survey articles of fundamental topics, most are original research papers.

The problems of ocean dynamics present more and more com plex tasks for investigators, based on the continuously sophisti cation of theoretical models, which are applied with the help of universal and efficient algorithms of numerical mathematics. The present level of our knowledge in the field of mathemat ical physics and numerical mathematics allows one to give rather complete theoretical analysis of basic statements of problems as well as numerical algorithms. Our task is to perform such analy sis and also to analyze the results of calculations in order to improve our knowledge of the mechanism of large-scale hy drological processes occurring in the World Ocean. The new level of numerical mathematics has essentially influenced, the formation of new solution methods of ocean dynamics prob lems, among which an important one is the splitting method, which has been already widely practised in various fields of science and engineering. A number of monographs by N. N. Yanenko, A. A. Samarsky, G. . Marchuk (Rozhdestvensky and Yanenko 1968; Samarsky and Andreyev 1976; Marchuk 1970, 1980b) and others are devoted to the description of this methods. But the methods of the splitting theory require extensive creative work for their application to concrete problems, which are peculiar, as a rule, in problem formulation. The success of the application of these methods is related to the deep understanding of the essence of the described processes. In the last decades fundamental works of Arakawa, K."

Matroids appear in diverse areas of mathematics, from combinatorics to algebraic topology and geometry, and "Coxeter Matroids" provides an intuitive and interdisciplinary treatment of their theory. In this text, matroids are examined in terms of symmetric and finite reflection groups; also, symplectic matroids and the more general coxeter matroids are carefully developed. The Gelfand-Serganova theorem, which allows for the geometric interpretation of matroids as convex polytopes with certain symmetry properties, is presented, and in the final chapter, matroid representations and combinatorial flag varieties are discussed. With its excellent bibliography and index and ample references to current research, this work will be useful for graduate students and research mathematicians.

Imaging Heat and Mass Transfer Processes: Visualization and Analysis applies Schlieren and shadowgraph techniques to complex heat and mass transfer processes. Several applications are considered where thermal and concentration fields play a central role. These include vortex shedding and suppression from stationary and oscillating bluff bodies such as cylinders, convection around crystals growing from solution, and buoyant jets. Many of these processes are unsteady and three dimensional. The interpretation and analysis of images recorded are discussed in the text.

In the past two decades, breakthroughs in computer technology have made a tremendous impact on optimization. In particular, availability of parallel computers has created substantial interest in exploring the use of parallel processing for solving discrete and global optimization problems. The chapters in this volume cover a broad spectrum of recent research in parallel processing of discrete and related problems. The topics discussed include distributed branch-and-bound algorithms, parallel genetic algorithms for large scale discrete problems, simulated annealing, parallel branch-and-bound search under limited-memory constraints, parallelization of greedy randomized adaptive search procedures, parallel optical models of computing, randomized parallel algorithms, general techniques for the design of parallel discrete algorithms, parallel algorithms for the solution of quadratic assignment and satisfiability problems. The book will be a valuable source of information to faculty, students and researchers in combinatorial optimization and related areas.

A study of topology and geometry, beginning with a comprehensible account of the extraordinary and rather mysterious impact of mathematical physics, and especially gauge theory, on the study of the geometry and topology of manifolds. The focus of the book is the Yang-Mills-Higgs field and some considerable effort is expended to make clear its origin and significance in physics. Much of the mathematics developed here to study these fields is standard, but the treatment always keeps one eye on the physics and sacrifices generality in favor of clarity. The author brings readers up the level of physics and mathematics needed to conclude with a brief discussion of the Seiberg-Witten invariants. A large number of exercises are included to encourage active participation on the part of the reader.

This textbook thoroughly outlines combinatorial algorithms for generation, enumeration, and search. Topics include backtracking and heuristic search methods applied to various combinatorial structures, such as:
· Combinations
· Permutations
· Graphs
· Designs
·
Many classical areas are covered as well as new research topics not included in most existing texts, such as:
· Group algorithms
· Graph isomorphism
· Hill-climbing
· Heuristic search algorithms
·
This work serves as an exceptional textbook for a modern course in combinatorial algorithms, providing a unified and focused collection of recent topics of interest in the area. The authors, synthesizing material that can only be found scattered through many different sources, introduce the most important combinatorial algorithmic techniques - thus creating an accessible, comprehensive text that students of mathematics, electrical engineering, and computer science can understand without needing a prior course on combinatorics.

The theory of matroids is unique in the extent to which it connects such disparate branches of combinatorial theory and algebra as graph theory, lattice theory, design theory, combinatorial optimization, linear algebra, group theory, ring theory and field theory. Furthermore, matroid theory is alone among mathematical theories because of the number and variety of its equivalent axiom systems. Indeed, matroids are amazingly versatile and the approaches to the subject are varied and numerous. This book is a primer in the basic axioms and constructions of matroids. The contributions by various leaders in the field include chapters on axiom systems, lattices, basis exchange properties, orthogonality, graphs and networks, constructions, maps, semi-modular functions and an appendix on cryptomorphisms. The authors have concentrated on giving a lucid exposition of the individual topics; explanations of theorems are preferred to complete proofs and original work is thoroughly referenced. In addition, exercises are included for each topic.

Gian-Carlo Rota was one of the most original and colourful mathematicians of the 20th century. His work on the foundations of combinatorics focused on the algebraic structures that lie behind diverse combinatorial areas, and created a new area of algebraic combinatorics. Written by two of his former students, this book is based on notes from his influential graduate courses and on face-to-face discussions. Topics include sets and valuations, partially ordered sets, distributive lattices, partitions and entropy, matching theory, free matrices, doubly stochastic matrices, Moebius functions, chains and antichains, Sperner theory, commuting equivalence relations and linear lattices, modular and geometric lattices, valuation rings, generating functions, umbral calculus, symmetric functions, Baxter algebras, unimodality of sequences, and location of zeros of polynomials. Many exercises and research problems are included, and unexplored areas of possible research are discussed. A must-have for all students and researchers in combinatorics and related areas.

Professor Rogers has written this economical and logical exposition of the theory of packing and covering at a time when the simplest general results are known and future progress seems likely to depend on detailed and complicated technical developments. The book treats mainly problems in n-dimensional space, where n is larger than 3. The approach is quantative and many estimates for packing and covering densities are obtained. The introduction gives a historical outline of the subject, stating results without proof, and the succeeding chapters contain a systematic account of the general results and their derivation. Some of the results have immediate applications in the theory of numbers, in analysis and in other branches of mathematics, while the quantative approach may well prove to be of increasing importance for further developments.

nullane de tantis gregibus tibi digna videtur? rara avis in terra nigroque simillima cygno. Juvenal Sat. VI 161, 165. 1966-JNC visits AN at CornelI. An idea emerges. 1968-JNC is at V. c. L. A. for the Logic Year. The Los Angeles ma- script appears. 1970-AN visits JNC at Monash. 1971-The Australian manuscript appears. 1972-JNC visits AN at Cornell. Here is the result. We gratefully acknowledge support from Cornell Vniversity, Vni- versity of California at Los Angeles, Monash Vniversity and National Science Foundation Grants GP 14363, 22719 and 28169. We are deeply indebted to the many people who have helped uso Amongst the mathe- maticians, we are particularly grateful to J. C. E. Dekker, John Myhill, Erik Ellentuck, Peter AczeI, Chris Ash, Charlotte ehell, Ed Eisenberg, Dave Gillam, Bill Gross, Alan Hamilton, Louise Hay, Georg Kreisel, Phil Lavori, Ray Liggett, Al Manaster, Michael D. Morley, Joe Rosen- stein, Graham Sainsbury, Bob Soare and Michael Venning. Last, but by no means least, we thank Anne-Marie Vandenberg, Esther Monroe, Arletta Havlik, Dolores Pendell, and Cathy Stevens and the girls of the Mathematics Department of VCLA in 1968 for hours and hours of excellent typing. Thanksgiving November 1972 J. N. Crossley Ithaca, New Y ork Anil Nerode Contents O. Introduction ...1 Part 1. Categories and Functors 3 1. Categories ...3 2. Morphism Combinatorial Functors 3 3. Combinatorial Functors ...18 Part H. Model Theory . . 18 4. Countable Atomic Models 18 5. Copying . 22 6. Dimension ...26 Part III.