Discrete Mathematics and Theoretical Computer Science – serie

Logic and Complexity looks at basic logic as it is used in Computer Science, and provides students with a logical approach to Complexity theory. With plenty of exercises, this book presents classical notions of mathematical logic, such as decidability, completeness and incompleteness, as well as new ideas brought by complexity theory such as NP-completeness, randomness and approximations, providing a better understanding for efficient algorithmic solutions to problems. Divided into three parts, it covers: - Model Theory and Recursive Functions - introducing the basic model theory of propositional, 1st order, inductive definitions and 2nd order logic. Recursive functions, Turing computability and decidability are also examined. - Descriptive Complexity - looking at the relationship between definitions of problems, queries, properties of programs and their computational complexity. - Approximation - explaining how some optimization problems and counting problems can be approximated according to their logical form. Logic is important in Computer Science, particularly for verification problems and database query languages such as SQL. Students and researchers in this field will find this book of great interest.

In The Unknowable I use LISP to compare my work on incompleteness with that of G6del and Turing, and in The Limits of Mathematics I use LISP to discuss my work on incompleteness in more detail. In this book we'll use LISP to explore my theory of randomness, called algorithmic information theory (AIT). And when I say "explore" I mean it! This book is full of exercises for the reader, ranging from the mathematical equivalent oftrivial "fin­ ger warm-ups" for pianists, to substantial programming projects, to questions I can formulate precisely but don't know how to answer, to questions that I don't even know how to formulate precisely! I really want you to follow my example and hike offinto the wilder­ ness and explore AIT on your own! You can stay on the trails that I've blazed and explore the well-known part of AIT, or you can go off on your own and become a fellow researcher, a colleague of mine! One way or another, the goal of this book is to make you into a participant, not a passive observer of AlT. In other words, it's too easy to just listen to a recording of AIT, that's not the way to learn music.

As a teenager, Greg created independently of Kolmogorov and Solomonoff, what we call today algorithmic information theory, a sub­ ject of which he is the main architect. His 1965 paper on gedanken experiments on automata, which he wrote when he was in high school, is still of interest today. He was also heavily involved in IBM, where he has worked for almost thirty years, on the development of RISC technology. Greg's results are widely quoted. My favorite portrait of Greg can be found in John Horgan's-a writer for Scientific American-1996 book The End 01 Science. Greg has gotten many honors. He was a guest of distinguished people like Prigogine, the King and Queen of Belgium, and the Crown Prince of Japan. Just to be brief, allow me to paraphrase Bette Davis in All About Eve. She said, "Fasten your seat belts, it's going to be a bumpy talk!" Ladies and Gentlemen, Greg Chaitin! [Laughter & Applause] CRISTIAN CALUDE introducing GREGORY CHAITIN at the DMTCS'96 meeting at the University of Auckland.

Network Algebra considers the algebraic study of networks and their behaviour. It contains general results on the algebraic theory of networks, recent results on the algebraic theory of models for parallel programs, as well as results on the algebraic theory of classical control structures. The results are presented in a unified framework of the calculus of flownomials, leading to a sound understanding of the algebraic fundamentals of the network theory. The term 'network' is used in a broad sense within this book, as consisting of a collection of interconnecting cells, and two radically different specific interpretations of this notion of networks are studied. One interpretation is additive, when only one cell is active at a given time - this covers the classical models of control specified by finite automata or flowchart schemes. The second interpretation is multiplicative, where each cell is always active, covering models for parallel computation such as Petri netsor dataflow networks. More advanced settings, mixing the two interpretations are included as well. Network Algebra will be of interest to anyone interested in network theory or its applications and provides them with the results needed to put their work on a firm basis. Graduate students will also find the material within this book useful for their studies.

This volume contains the refereed proceedings of the International Conference on Sequences and Their Applications which was held at the River View Ho- tel in Singapore during December 14-17, 1998. The program of this conference was arranged by a committee consisting of Claude Carlet (University of Caen) , Agnes Chan (Northeastern University), Cunsheng Ding (National University of Singapore, co-chair), Dieter Gollmann (Microsoft Research), Tor Helleseth (Uni- versity of Bergen, co-chair), Kyoki Imamura (Kyushu Institute of Technology), Andrew Klapper (University of Kentucky), Vijay Kumar (University of Southern California), Siu Lun Ma (National University of Singapore), Harald Niederreiter (A ustrian Academy of Sciences, co-chair), Dilip Sarwate (University of Illinois at Urbana-Champaign), Hans Schotten (Aachen University of Technology), Jeffrey Shallit (University of Waterloo), Neil Sloane (AT&T Shannon Lab), and Aimo Tietiivajnen (University of Turku). The local organization was in the hands of Cunsheng Ding, Kwok Van Lam (chair), Sjauntele Lau, and Sew Kiok Toh, all of the National University of Singapore.The idea for the conference grew out of the recognition that sequences in discrete structures like the ring of integers, residue class rings of the integers, and finite fields have found many important applications in modern information and communication technologies. Among these applications we mention cryp- tographic schemes, ranging systems, spread spectrum communication systems, multi-terminal system identification, code-division mUltiple-access communica- tion systems, global positioning systems, software testing, circuit testing, and computer simulation. There are also connections between sequences in discrete structures and error-correcting codes.

The finite - infinite interplay is central in human thinking, from ancient philosophers and mathematicians (Zeno, Pythagoras), to modern mathe­ matics (Cantor, Hilbert) and computer science (Turing, Godel). Recent developments in mathematics and computer science suggest a) radically new answers to classical questions (e. g. , does infinity exist?, where does infinity come from?, how to reconcile the finiteness of the human brain with the infinity of ideas it produces?), b) new questions of debate (e. g. , what is the role played by randomness?, are computers capable of handling the infinity through unconventional media of computation?, how can one approximate efficiently the finite by the infinite and, conversely, the infinite by finite?). Distinguished authors from around the world, many of them architects of the mathematics and computer science for the new century, contribute to the volume. Papers are as varied as Professor Marcus' activity, to whom this volume is dedicated. They range from real analysis to DNA com­ puting, from linguistics to logic, from combinatorics on words to symbolic dynamics, from automata theory to geography, and so on, plus an incursion into the old history of conceptions about infinity and a list of philosophical "open problems". They are mainly mathematical and theoretical computer science texts, but not all of them are purely mathematical.

Lattice (Boolean) functions are algebraic functions defined over an arbitrary lattice (Boolean algebra), while lattice (Boolean) equations are equations expressed in terms of lattice (Boolean) functions.This self-contained monograph surveys recent developments of Boolean functions and equations, as well as lattice functions and equations in more general classes of lattices; a special attention is paid to consistency conditions and reproductive general solutions.The contents include:- equational compactness in semilattices and Boolean algebras;- the theory of Post functions and equations (which is very close to that of Boolean functions and equations);- a revision of Boolean fundamentals;- closure operators on Boolean functions;- the decomposition of Boolean functions;- quadratic truth equations;- Boolean differential calculus;- Boolean geometry and other topics.There is also a chapter on equations in a very general sense. Applications refer to graph theory, automata theory, synthesis of circuits, fault detection, databases, marketing and others.

The Second International Conference on Unconventional Models of Compu- UMC'2K, organized by the Centre for Discrete Mathematics and The- tation, oretical Computer Science, the International Solvay Institutes for Physics and Chemistry and the Vrije Universiteit Brussel Theoretical Physics Division was held at Solvay Institutes from 13 to 16 December, 2000. The computers as we know them today, based on silicon chips, are get- ting better and better, cheaper and cheaper, and are doing more and more for us. Nonetheless, they still give rise to frustrations because they are unable to cope with many tasks of practical interest: Too many problems are effectively intractable. A simple example: cyber movie networks face the near impossible task of building a brand in a computing and communication almost vacuum. Fortunately, for billions of years nature itself has been "computing" with molecules and cells. These natural processes form the main motivation for the construction of radically new models of computation, the core interest of our conference. The ten invited speakers at the conference were: 1. Accardi (Rome, Italy), S. Bozapalidis (Thessaloniki, Greece), K.Gustafson (Boulder, USA), T. Head (Binghamton, USA), T. Hida (Nagoya, Japan), v. Ivanov (Dubna, Russia), G. Piiun (Bucharest, Romania), G. Rozenberg (Lei den, the Netherlands). H. Siegelmann (Haifa, Israel), and E. Winfree (Caltech, USA). The Programme Committee consisting ofM. Amos (Liverpool, UK), I. An- toniou (Co-chair, Brussels, Belgium), S. Bozapalidis (Thessaloniki, Greece), G.

In The Unknowable I use LISP to compare my work on incompleteness with that of G6del and Turing, and in The Limits of Mathematics I use LISP to discuss my work on incompleteness in more detail. In this book we'll use LISP to explore my theory of randomness, called algorithmic information theory (AIT). And when I say "explore" I mean it! This book is full of exercises for the reader, ranging from the mathematical equivalent oftrivial "fin­ ger warm-ups" for pianists, to substantial programming projects, to questions I can formulate precisely but don't know how to answer, to questions that I don't even know how to formulate precisely! I really want you to follow my example and hike offinto the wilder­ ness and explore AIT on your own! You can stay on the trails that I've blazed and explore the well-known part of AIT, or you can go off on your own and become a fellow researcher, a colleague of mine! One way or another, the goal of this book is to make you into a participant, not a passive observer of AlT. In other words, it's too easy to just listen to a recording of AIT, that's not the way to learn music.

Alan Mathison Turing (1912-1954) was the first to carry out substantial re­ search in the field now known as Artificial Intelligence (AI). He was thinking about machine intelligence at least as early as 1941 and during the war cir­ culated a typewritten paper on machine intelligence among his colleagues at the Government Code and Cypher School (GC & CS), Bletchley Park. Now lost, this was undoubtedly the earliest paper in the field of AI. It probably concerned machine learning and heuristic problem-solving; both were topics that Turing discussed extensively during the war years at GC & CS, as was mechanical chess [121]. In 1945, the war in Europe over, Turing was recruited by the National Physical Laboratory (NPL)! in London, his brief to design and develop an electronic stored-program digital computer-a concrete form of the universal Turing machine of 1936 [185]. Turing's technical report "Proposed Electronic 2 Calculator" , dating from the end of 1945 and containing his design for the Automatic Computing Engine (ACE), was the first relatively complete spec­ ification of an electronic stored-program digital computer [193,197]. (The document "First Draft of a Report on the EDVAC", produced by John von Neumann and the Moore School group at the University of Pennsylvania in May 1945, contained little engineering detail, in particular concerning elec­ tronic hardware [202].

The third Discrete Mathematics and Theoretical Computer Science conference (DMTCS'OI) of the Centre for Discrete Mathematics and Theoretical Computer Science of the University of Auckland has been organised at the Faculty of Math- ematics and Computer Science, "Ovidius" University, Constan~a, Romania, with the co-operation of the Maritime Academy "Mircea eel Batran", Constan~a. It was held held in the beautiful Romanian city of Constan~a on the Black Sea. The conference was dedicated to Professor Frank Harary on the occasion of his 80th Birthday. The four invited speakers of the conference were: F. Harary (New Mexico State University, USA), H. Ishihara (Jaist, Japan), P. Odifreddi (Thrin Univer- sity, Italy), 1. Tomescu (Bucharest University, Romania). The Programme Committee consisting of C.S. Calude (Chair, Auckland), C. Ding (Hong Kong), M.J. Dinneen (Secretary, Auckland), M.R. Fellows (Victo- ria, Canada), M. Hallett (Zurich), M. Ito (Kyoto), S. Istrail (Rockville, USA), K-W. Lih (Taipei), S. Marcus (Bucharest), Y. Matiyasevich (St. Petersburg), Gh. Paun (Bucharest), S. Rudeanu (Bucharest), J. Rutten (Amsterdam), K.

Pseudorandom sequences have widespread applications, for instance, in spread spectrum, code division multiple access, optical and ultrawide band communication systems, as well as in ranging systems global positioning systems, circuit testing and stream ciphers. Such sequences also have strong ties to error-correcting codes.This volume contains survey and research papers on sequences and their applications. It brings together leading experts from discrete mathematics, computer science and communications engineering, and helps to bridge advances in these different areas. Papers in this volume discuss the theory of sequences and their applications in cryptography, coding theory, communications systems, numerical computation and computer simulation.

Logic and Complexity looks at basic logic as it is used in Computer Science, and provides students with a logical approach to Complexity theory. With plenty of exercises, this book presents classical notions of mathematical logic, such as decidability, completeness and incompleteness, as well as new ideas brought by complexity theory such as NP-completeness, randomness and approximations, providing a better understanding for efficient algorithmic solutions to problems. Divided into three parts, it covers: - Model Theory and Recursive Functions - introducing the basic model theory of propositional, 1st order, inductive definitions and 2nd order logic. Recursive functions, Turing computability and decidability are also examined. - Descriptive Complexity - looking at the relationship between definitions of problems, queries, properties of programs and their computational complexity. - Approximation - explaining how some optimization problems and counting problems can be approximated according to their logical form. Logic is important in Computer Science, particularly for verification problems and database query languages such as SQL. Students and researchers in this field will find this book of great interest.

As a teenager, Greg created independently of Kolmogorov and Solomonoff, what we call today algorithmic information theory, a sub­ ject of which he is the main architect. His 1965 paper on gedanken experiments on automata, which he wrote when he was in high school, is still of interest today. He was also heavily involved in IBM, where he has worked for almost thirty years, on the development of RISC technology. Greg's results are widely quoted. My favorite portrait of Greg can be found in John Horgan's-a writer for Scientific American-1996 book The End 01 Science. Greg has gotten many honors. He was a guest of distinguished people like Prigogine, the King and Queen of Belgium, and the Crown Prince of Japan. Just to be brief, allow me to paraphrase Bette Davis in All About Eve. She said, "Fasten your seat belts, it's going to be a bumpy talk!" Ladies and Gentlemen, Greg Chaitin! [Laughter & Applause] CRISTIAN CALUDE introducing GREGORY CHAITIN at the DMTCS'96 meeting at the University of Auckland.

Information usually comes in pieces, from different sources. It refers to different, but related questions. Therefore information needs to be aggregated and focused onto the relevant questions. Considering combination and focusing of information as the relevant operations leads to a generic algebraic structure for information. This book introduces and studies information from this algebraic point of view. Algebras of information provide the necessary abstract framework for generic inference procedures. They allow the application of these procedures to a large variety of different formalisms for representing information. At the same time they permit a generic study of conditional independence, a property considered as fundamental for knowledge presentation. Information algebras provide a natural framework to define and study uncertain information. Uncertain information is represented by random variables that naturally form information algebras. This theory also relates to probabilistic assumption-based reasoning in information systems and is the basis for the belief functions in the Dempster-Shafer theory of evidence.

Quantum Logic deals with the foundations of quantum mechanics and, related to it, the behaviour of finite, discrete deterministic systems. The quantum logical approach is particulalry suitable for the investigation and exclusion of certain hidden parameter models of quantum mechanics. Conversely, it can be used to embed quantum universes into classical ones. It is also highly relevant for the characterization of finite automation. This book has been written with a broad readership in mind. Great care has been given to the motivation of the concepts and to the explicit and detailed discussions of examples.