This must-read textbook presents an essential introduction to Kolmogorov complexity (KC), a central theory and powerful tool in information science that deals with the quantity of information in individual objects. The text covers both the fundamental concepts and the most important practical applications, supported by a wealth of didactic features. This thoroughly revised and enhanced fourth edition includes new and updated material on, amongst other topics, the Miller-Yu theorem, the Gács-Kučera theorem, the Day-Gács theorem, increasing randomness, short lists computable from an input string containing the incomputable Kolmogorov complexity of the input, the Lovász local lemma, sorting, the algorithmic full Slepian-Wolf theorem for individual strings, multiset normalized information distance and normalized web distance, and conditional universal distribution. Topics and features: describes the mathematical theory of KC, including the theories of algorithmic complexity and algorithmic probability; presents a general theory of inductive reasoning and its applications, and reviews the utility of the incompressibility method; covers the practical application of KC in great detail, including the normalized information distance (the similarity metric) and information diameter of multisets in phylogeny, language trees, music, heterogeneous files, and clustering; discusses the many applications of resource-bounded KC, and examines different physical theories from a KC point of view; includes numerous examples that elaborate the theory, and a range of exercises of varying difficulty (with solutions); offers explanatory asides on technical issues, and extensive historical sections; suggests structures for several one-semester courses in the preface. As the definitive textbook on Kolmogorov complexity, this comprehensive and self-contained work is an invaluable resource for advanced undergraduate students, graduate students, and researchers in all fields of science.
This volume presents the proceedings of the Second European Conference on Computational Learning Theory (EuroCOLT '95), held in Barcelona, Spain in March 1995. The book contains full versions of the 28 papers accepted for presentation at the conference as well as three invited papers. All relevant topics in fundamental studies of computational aspects of artificial and natural learning systems and machine learning are covered; in particular artificial and biological neural networks, genetic and evolutionary algorithms, robotics, pattern recognition, inductive logic programming, decision theory, Bayesian/MDL estimation, statistical physics, and cryptography are addressed.
Briefly, we review the basic elements of computability theory and prob ability theory that are required. Finally, in order to place the subject in the appropriate historical and conceptual context we trace the main roots of Kolmogorov complexity. This way the stage is set for Chapters 2 and 3, where we introduce the notion of optimal effective descriptions of objects. The length of such a description (or the number of bits of information in it) is its Kolmogorov complexity. We treat all aspects of the elementary mathematical theory of Kolmogorov complexity. This body of knowledge may be called algo rithmic complexity theory. The theory of Martin-Lof tests for random ness of finite objects and infinite sequences is inextricably intertwined with the theory of Kolmogorov complexity and is completely treated. We also investigate the statistical properties of finite strings with high Kolmogorov complexity. Both of these topics are eminently useful in the applications part of the book. We also investigate the recursion theoretic properties of Kolmogorov complexity (relations with Godel's incompleteness result), and the Kolmogorov complexity version of infor mation theory, which we may call "algorithmic information theory" or "absolute information theory. " The treatment of algorithmic probability theory in Chapter 4 presup poses Sections 1. 6, 1. 11. 2, and Chapter 3 (at least Sections 3. 1 through 3. 4).
Whereas Kolmogorov complexity is the accepted absolute measure of information content of an individual finite object, a similarly absolute notion is needed for the relation between an individual data sample and an individual model summarizing the information in the data ---for example, a finite set (or probability distribution) where the data sample typically came from. The statistical theory based on such relations between individual objects can be called algorithmic statistics, in contrast to classical statistical theory that deals with relations between probabilistic ensembles. 'Algorithmic Statistics' develops the algorithmic theory of statistics, sufficient statistics, and minimal sufficient statistics. This theory is based on two-part codes consisting of the code for the statistic (the model summarizing the regularity, the meaningful information, in the data) and the model-to-data code. In contrast to the situation in probabilistic statistical theory, the algorithmic relation of (minimal) sufficiency is an absolute relation between the individual model and the individual data sample. The book distinguishes implicit and explicit descriptions of the models and gives characterizations of algorithmic (Kolmogorov) minimal sufficient statistic for all data samples for both description modes--in the explicit mode under some constraints. It also strengthens and elaborates upon earlier results on the ``Kolmogorov structure function'' and ``absolutely non-stochastic objects''--those rare objects for which the simplest models that summarize their relevant information (minimal sufficient statistics) are at least as complex as the objects themselves.
This volume contains the proceedings of the fifth International Workshop on Distributed Algorithms (WDAG '91) held in Delphi, Greece, in October 1991. The workshop provided a forum for researchers and others interested in distributed algorithms, communication networks, and decentralized systems. The aim was to present recent research results, explore directions for future research, and identify common fundamental techniques that serve as building blocks in many distributed algorithms. The volume contains 23 papers selected by the Program Committee from about fifty extended abstracts on the basis of perceived originality and quality and on thematic appropriateness and topical balance. The workshop was organizedby the Computer Technology Institute of Patras University, Greece.
Thank you for visiting our website. Would you like to provide feedback on how we could improve your experience?
This site does not use any third party cookies with one exception — it uses cookies from Google to deliver its services and to analyze traffic.Learn More.