Bøger i Discrete Mathematics and Theoretical Computer Science serien

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.

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

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. My favorite portrait of Greg can be found in John Horgan's-a writer for Scientific American-1996 book The End 01 Science. Ladies and Gentlemen, Greg Chaitin!

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.

This volume contains the papers presented at the Third Combinatorics, Computability and Logic (DMTCS'01) conference, These papers cover topics such as abstract data types and specifications algorithms and data structures automata and formal languages computability among others.

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.

Contains papers presented at the 2nd International Conference on Unconventional Models of Computation, which was held at Solvay Institutes, Brussels, Belgium, in December 2000. This work covers all major areas of unconventional computation, including quantum computing, DNA-based computation, membrane computing and evolutionary algorithms.

This essential companion to Chaitin's successful books The Unknowable and The Limits of Mathematics, presents the technical core of his theory of program-size complexity. The LISP code for this book is available at the author's Web site together with a Java applet LISP interpreter.

Christof Teuscher revives, analyzes, and simulates Turing's ideas, applying them to different types of problems, and building and training Turing's machines using evolutionary algorithms.

A collection of survey papers and research papers by experts on sequences and their applications. This text discusses both the theory of sequences and their applications in cryptography, coding theory, communications systems, numerical computation and computer simulation.

This essential companion to Chaitins highly successful The Limits of Mathematics, gives a brilliant historical survey of important work on the foundations of mathematics. The Unknowable is a very readable introduction to Chaitins ideas, and includes software (on the authors website) that will enable users to interact with the authors proofs.