This book presents a selection of the papers presented at EUROCODE '90, the symposium on coding theory held in Udine, Italy, November 1990. It gives the state of the art on coding in Europe and ranges from theoretical top- ics like algebraic geometry and combinatorial coding to applications like modulation, real-space decoding and VLSI implementation. The book is divided into eight sections: - Algebraic codes - Combinatorial codes - Geometric codes - Protection of information - Convolutional codes - Information theory - Modulation - Applications of coding. Five of the sections are introduced by an invited contribution.

The AAECC conferences focus on the algebraic aspects of modern computer science, which includes the most up-to-date and advanced topics. The topic of error-correcting codes is one where theory and implementation are unifiedinto a subject both of mathematical beauty and of practical importance. Algebraic algorithms are not only interesting theoretically but also important in computer and communication engineering and many other fields. This volume contains the proceedings of the 9th AAECC conference, held in New Orleans, LA, in October 1991. Researchers from Europe, America, Japan and other regions of the world presented papers at the conference. The papers present new results of recent theoretical and application-oriented research in the field.

These proceedings reflect the main activities of the Paris S minaire d'Alg bre 1989-1990, with a series of papers in Invariant Theory, Representation Theory and Combinatorics. It contains original works from J. Dixmier, F. Dumas, D. Krob, P. Pragacz and B.J. Schmid, as well as a new presentation of Derived Categories by J.E. Bj rk and as introduction to the deformation theory of Lie equations by J.F. Pommaret. J. Dixmier: Sur les invariants du groupe sym trique dans certaines repr sentations II.- B.J. Schmid: Finite groups and invariant theory.- J.E. Bj rk: Derived categories.- P. Pragacz: Algebro-Geometric applications of Schur S- and Q-polynomials.- F. Dumas: Sous-corps de fractions rationnelles des corps gauches de s ries de Laurent.- D. Krob: Expressions rationnelles sur un anneau.- J.F. Pommaret: Deformation theory of algebraic and Geometric structures.- M. van den Bergh: Differential operators on semi-invariants for tori and weighted projective spaces.

Parallelism or concurrency is one of the fundamental concepts in computer science. But in spite of its importance, theoretical methods to handle concurrency are not yet sufficiently developed. This volume presents a comprehensive study of Mazurkiewicz' trace theory from an algebraic-combinatorial point of view. This theory is recognized as an important tool for a rigorous mathematical treatment of concurrent systems. The volume covers several different research areas, and contains not only known results but also various new results published nowhere else. Chapter 1 introduces basic concepts. Chapter 2 gives a straight path to Ochmanski's characterization of recognizable trace languages and to Zielonka's theory of asynchronous automata. Chapter 3 applies the theory of traces to Petri nets. A kind of morphism between nets is introduced which generalizes the concept of synchronization. Chapter 4 provides a new bridge between the theory of string rewriting and formal power series. Chapter 5 is an introduction to a combinatorial theory of rewriting on traces which can be used as an abstract calculus for transforming concurrent processes.

The fields of integer programming and combinatorial optimization continue to be areas of great vitality, with an ever increasing number of publications and journals appearing. A classified bibliography thus continues to be necessary and useful today, even more so than it did when the project, of which this is the fifth volume, was started in 1970 in the Institut fur Okonometrie und Operations Research of the University of Bonn. The pioneering first volume was compiled by Claus Kastning during the years 1970 - 1975 and appeared in 1976 as Volume 128 of the series Lecture Notes in Economics and Mathematical Systems published by the Springer Verlag. Work on the project was continued by Dirk Hausmann, Reinhardt Euler, and Rabe von Randow, and resulted in the publication of the second, third, and fourth volumes in 1978, 1982, and 1985 (Volumes 160, 197, and 243 of the above series). The present book constitutes the fifth volume of the bibliography and covers the period from autumn 1984 to the end of 1987. It contains 5864 new publications by 4480 authors and was compiled by Rabe von Randow. Its form is practically identical to that of the first four volumes, some additions having been made to the subject list.

The central theme of this volume is commutative algebra, with emphasis on special graded algebras, which are increasingly of interest in problems of algebraic geometry, combinatorics and computer algebra. Most of the papers have partly survey character, but are research-oriented, aiming at classification and structural results.

This volume presents papers from the 2nd Scandinavian Workshop on Algorithm Theory. The contributions describe original research on algorithms and data structures, in all areas, including combinatorics, computational geometry, parallel computing, and graph theory. The majority of the papers focus on the design and complexity analysis of: data structures, text algorithms, and sequential and parallel algorithms for graph problems and for geometric problems. Examples of tech- niques presented include: - efficient ways to find approximation algorithms for the maximum independent set problem and for graph coloring; - exact estimation of the expected search cost for skip lists; - construction of canonical representations of partial 2-trees and partial 3-trees in linear time; - efficient triangulation of planar point sets and convex polygons.

This volume comprises 17 contributions that present advanced topics in graph domination, featuring open problems, modern techniques, and recent results. The book is divided into 3 parts. The first part focuses on several domination-related concepts: broadcast domination, alliances, domatic numbers, dominator colorings, irredundance in graphs, private neighbor concepts, game domination, varieties of Roman domination and spectral graph theory. The second part covers domination in hypergraphs, chessboards, and digraphs and tournaments. The third part focuses on the development of algorithms and complexity of signed, minus and majority domination, power domination, and alliances in graphs. The third part also includes a chapter on self-stabilizing algorithms. Of extra benefit to the reader, the first chapter includes a glossary of commonly used terms. The book is intended to provide a reference for established researchers in the fields of domination and graph theory and graduate students who wish to gain knowledge of the topics covered as well as an overview of the major accomplishments and proof techniques used in the field.

A famous theorem in the theory of linear spaces states that every finite linear space has at least as many lines as points. This result of De Bruijn and Erd-s led to the conjecture that every linear space with "few lines" canbe obtained from a projective plane by changing only a small part of itsstructure. Many results related to this conjecture have been proved in the last twenty years. This monograph surveys the subject and presents several new results, such as the recent proof of the Dowling-Wilsonconjecture. Typical methods used in combinatorics are developed so that the text can be understood without too much background. Thus the book will be of interest to anybody doing combinatorics and can also help other readers to learn the techniques used in this particular field.

The Pontryagin-van Kampen duality theorem and the Bochner theorem on positive-definite functions are known to be true for certain abelian topological groups that are not locally compact. The book sets out to present in a systematic way the existing material. It is based on the original notion of a nuclear group, which includes LCA groups and nuclear locally convex spaces together with their additive subgroups, quotient groups and products. For (metrizable, complete) nuclear groups one obtains analogues of the Pontryagin duality theorem, of the Bochner theorem and of the L vy-Steinitz theorem on rearrangement of series (an answer to an old question of S. Ulam). The book is written in the language of functional analysis. The methods used are taken mainly from geometry of numbers, geometry of Banach spaces and topological algebra. The reader is expected only to know the basics of functional analysis and abstract harmonic analysis.

This volume presents the proceedings of the 14th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '88), held from June 15 to 17, 1988 in Amsterdam, The Netherlands. It contains 31 papers on new or current developments in the area of graph-based algorithms. The topics covered include e.g. structural graph theory, parallel graph algorithms, graph-based modeling (in database theory and VLSI), computational geometry and applied graph theory. The book contains the revised versions of all the papers presented at the workshop. The revisions are based on comments and suggestions received by the authors during and after the workshop.

The problem of uniform distribution of sequences initiated by Hardy, Little wood and Weyl in the 1910's has now become an important part of number theory. This is also true, in relation to combinatorics, of what is called Ramsey theory, a theory of about the same age going back to Schur. Both concern the distribution of sequences of elements in certain collection of subsets. But it was not known until quite recently that the two are closely interweaving bear ing fruits for both. At the same time other fields of mathematics, such as ergodic theory, geometry, information theory, algorithm theory etc. have also joined in. (See the survey articles: V. T. S6s: Irregularities of partitions, Lec ture Notes Series 82, London Math. Soc. , Surveys in Combinatorics, 1983, or J. Beck: Irregularities of distributions and combinatorics, Lecture Notes Series 103, London Math. Soc. , Surveys in Combinatorics, 1985. ) The meeting held at Fertod, Hungary from the 7th to 11th of July, 1986 was to emphasize this development by bringing together a few people working on different aspects of this circle of problems. Although combinatorics formed the biggest contingent (see papers 2, 3, 6, 7, 13) some number theoretic and analytic aspects (see papers 4, 10, 11, 14) generalization of both (5, 8, 9, 12) as well as irregularities of distribution in the geometric theory of numbers (1), the most important instrument in bringing about the above combination of ideas are also represented.

This book contains a selection of papers presented at a Symposium on coding theory: "3 Journees sur le Codage," held November 24-26, 1986, in Cachan near Paris, France. It gives an account of the state of the art of research in France on Coding, ranging from rather theoretical topics like algebraic geometry and combinatorial coding to applications like modulation, real-space decoding and implementation of coding algorithms on microcomputers. The symposium was the second one of this type. With its broad spectrum, it was a unique opportunity for contacts between university and industry on the topics of information and coding theory.

This volume contains the papers which were presented at the second workshop "Computer Science Logic" held in Duisburg, FRG, October 3-7, 1988. These proceedings cover a wide range of topics both from theoretical and applied areas of computer science. More specifically, the papers deal with problems arising at the border of logic and computer science: e.g. in complexity, data base theory, logic programming, artificial intelligence, and concurrency. The volume should be of interest to all logicians and computer scientists working in the above fields.

This volume presents the proceedings of the 2nd International Workshop on Distributed Algorithms, held July 8-10, 1987, in Amsterdam, The Netherlands. It contains 29 papers on new developments in the area of the design and analysis of distributed algorithms. The topics covered include, e.g. algorithms for distributed consensus and agreement in networks, connection management and topology update schemes, election and termination detection protocols, and other issues in distributed network control.

This volume contains the presentations of the Fifth Symposium on Theoretical Aspects of Computer Science (STACS 88) held at the University of Bordeaux, February 11-13, 1988. In addition to papers presented in the regular program the volume contains abstracts of software systems demonstrations which were included in this conference series in order to show applications of research results in theoretical computer science. The papers are grouped into the following thematic sections: algorithms, complexity, formal languages, rewriting systems and abstract data types, graph grammars, distributed algorithms, geometrical algorithms, trace languages, semantics of parallelism.

This text is an attempt to outline the basic facts concerning KekulEURO structures in benzenoid hydrocarbons: their history, applica tions and especially enumeration. We further pOint out the numerous and often quite remarkable connections between this topic and various parts of combinatorics and discrete mathematics. Our book is primarily aimed toward organic and theoretical chemists interested in the enume ration of Kekule structures of conjugated hydrocarbons as well as to scientists working in the field of mathematical and computational chemistry. The book may be of some relevance also to mathematicians wishing to learn about contemporary applications of combinatorics, graph theory and other branches of discrete mathematics. In 1985, when we decided to prepare these notes for publication, we expected to be able to give a complete account of all known combi natorial formulas for the number of Kekule structures of benzenoid hydrocarbons. This turned out to be a much more difficult task than we initially realized: only in 1986 some 60 new publications appeared dealing with the enumeration of Kekule structures in benzenoids and closely related topics. In any event, we believe that we have collec ted and systematized the essential part of the presently existing results. In addition to this we were delighted to see that the topics to*which we have been devoted in the last few years nowadays form a rapidly expanding branch of mathematical chemistry which attracts the attention of a large number of researchers (both chemists and mathematicians).

The first book devoted exclusively to quantitative graph theory, Quantitative Graph Theory: Mathematical Foundations and Applications presents and demonstrates existing and novel methods for analyzing graphs quantitatively. Incorporating interdisciplinary knowledge from graph theory, information theory, measurement theory, and statistical techniques, this book covers a wide range of quantitative-graph theoretical concepts and methods, including those pertaining to real and random graphs such as: Comparative approaches (graph similarity or distance) Graph measures to characterize graphs quantitatively Applications of graph measures in social network analysis and other disciplines Metrical properties of graphs and measures Mathematical properties of quantitative methods or measures in graph theory Network complexity measures and other topological indices Quantitative approaches to graphs using machine learning (e.g., clustering) Graph measures and statistics Information-theoretic methods to analyze graphs quantitatively (e.g., entropy) Through its broad coverage, Quantitative Graph Theory: Mathematical Foundations and Applications fills a gap in the contemporary literature of discrete and applied mathematics, computer science, systems biology, and related disciplines. It is intended for researchers as well as graduate and advanced undergraduate students in the fields of mathematics, computer science, mathematical chemistry, cheminformatics, physics, bioinformatics, and systems biology.

This volume contains abridged versions of most of the sectional talks and some invited lectures given at the International Conference on Fundamentals of Computation Theory held at Kazan State University, Kazan, USSR, June 22-26, 1987. The conference was the sixth in the series of FCT Conferences organized every odd year, and the first one to take place in the USSR. FCT '87 was organized by the Section of Discrete Mathematics of the Academy of Sciences in the USSR, the Moscow State University (Department of Discrete Mathematics), and the Kazan State University (Department of Theoretical Cybernetics). This volume contains selected contributions to the following fields: Mathematical Models of Computation, Synthesis and Complexity of Control Systems, Probabilistic Computations, Theory of Programming, Computer-Assisted Deduction. The volume reflects the fact that FCT '87 was organized in the USSR: A wide range of problems typical of research in Mathematical Cybernetics in the USSR is comprehensively represented.

For more than 35 years now, George B. Dantzig's Simplex-Method has been the most efficient mathematical tool for solving linear programming problems. It is proba bly that mathematical algorithm for which the most computation time on computers is spent. This fact explains the great interest of experts and of the public to understand the method and its efficiency. But there are linear programming problems which will not be solved by a given variant of the Simplex-Method in an acceptable time. The discrepancy between this (negative) theoretical result and the good practical behaviour of the method has caused a great fascination for many years. While the "worst-case analysis" of some variants of the method shows that this is not a "good" algorithm in the usual sense of complexity theory, it seems to be useful to apply other criteria for a judgement concerning the quality of the algorithm. One of these criteria is the average computation time, which amounts to an anal ysis of the average number of elementary arithmetic computations and of the number of pivot steps. A rigid analysis of the average behaviour may be very helpful for the decision which algorithm and which variant shall be used in practical applications. The subject and purpose of this book is to explain the great efficiency in prac tice by assuming certain distributions on the "real-world" -problems. Other stochastic models are realistic as well and so this analysis should be considered as one of many possibilities."

Praise for the First Edition This excellent text should prove a useful accoutrement for any developing mathematics program ...it s short, it s sweet, it s beautifully written. The Mathematical Intelligencer Erickson has prepared an exemplary work ...strongly recommended for inclusion in undergraduate-level library collections. Choice Featuring a modern approach, Introduction to Combinatorics, Second Edition illustrates the applicability of combinatorial methods and discusses topics that are not typically addressed in literature, such as Alcuin s sequence, Rook paths, and Leech s lattice. The book also presents fundamental results, discusses interconnection and problem-solving techniques, and collects and disseminates open problems that raise questions and observations. Many important combinatorial methods are revisited and repeated several times throughout the book in exercises, examples, theorems, and proofs alike, allowing readers to build confidence and reinforce their understanding of complex material. In addition, the author successfully guides readers step-by-step through three major achievements of combinatorics: Van der Waerden s theorem on arithmetic progressions, Polya s graph enumeration formula, and Leech s 24-dimensional lattice. Along with updated tables and references that reflect recent advances in various areas, such as error-correcting codes and combinatorial designs, the Second Edition also features: * Many new exercises to help readers understand and apply combinatorial techniques and ideas * A deeper, investigative study of combinatorics through exercises requiring the use of computer programs * Over fifty new examples, ranging in level from routine to advanced, that illustrate important combinatorial concepts * Basic principles and theories in combinatorics as well as new and innovative results in the field Introduction to Combinatorics, Second Edition is an ideal textbook for a one- or two-semester sequence in combinatorics, graph theory, and discrete mathematics at the upper-undergraduate level. The book is also an excellent reference for anyone interested in the various applications of elementary combinatorics.