Numbers, Information and Complexity

by Althofer, Ingo; Cai, Ning; Dueck, Gunter; Khachatrian, Levon; Pinsker, Mark S.; Sarkozy, Andras

• ISBN13: 9780792377658
• ISBN10: 0792377656
• Format: Hardcover
• Copyright: 2000-02-01
• Publisher: Kluwer Academic Pub

Summary

Numbers, Information and Complexity is a collection of about 50 articles in honour of Rudolf Ahlswede. His main areas of research are represented in the three sections, 'Numbers and Combinations', 'Information Theory (Channels and Networks, Combinatorial and Algebraic Coding, Cryptology, with the related fields Data Compression, Entropy Theory, Symbolic Dynamics, Probability and Statistics)', and 'Complexity'. Special attention was paid to the interplay between the fields. Surveys on topics of current interest are included as well as new research results. The book features surveys on Combinatorics about topics such as intersection theorems, which are not yet covered in textbooks, several contributions by leading experts in data compression, and relations to Natural Sciences are discussed.

Table of Contents

Preface	xiii
NUMBERS AND COMBINATORICS
On Prefix--free and Suffix--free Sequences of Integers	1	(16)
Rudolf Ahlswede
Levon H. Khachatrian
Andras Sarkozy
Almost Arithmetic Progressions	17	(4)
Egbert Harzheim
A Method to Estimate Partial-Period Correlations	21	(8)
Aimo Tietavainen
Splitting Properties in Partially Ordered Sets and Set Systems	29	(16)
Rudolf Ahlswede
Levon H. Khachatrian
Old and New Results for the Weighted t--Intersection Problem via AK--Methods	45	(30)
Christian Bey
Konrad Engel
Some New Results on Macaulay Posets	75	(20)
Sergei L. Bezrukov
Uwe Leck
Minimizing the Absolute Upper Shadow	95	(6)
Bela Bollobas
Imre Leader
Convex Bounds for the 0,1 Co--ordinate Deletions Function	101	(4)
David E. Daykin
The Extreme Points of the Probabilistic Capacities Cone Problem	105	(4)
David E. Daykin
On Shifts of Cascades	109	(8)
David E. Daykin
Erdos-Ko-Rado Theorems of Higher Order	117	(8)
Peter L. Erdos
Laszlo A. Szekely
On the Prague Dimension of Kneser Graphs	125	(4)
Zoltan Furedi
The cycle method and its limits	129	(14)
Gyula O.H. Katona
Extremal Problems on Δ-Systems	143	(8)
Alexandr V. Kostochka
INFORMATION THEORY
Channels and Networks
The AVC with Noiseless Feedback	151	(26)
Rudolf Ahlswede
Ning Cai
Calculation of the Asymptotically Optimal Capacity of a T-User M-Frequency Noiseless Multiple-Access Channel	177	(4)
Leonid Bassalygo
Mark Pinsker
A Survey of Coding Methods for the Adder Channel	181	(16)
Gurgen H. Khachatrian
Communication Network with Self-Similar Traffic	197	(24)
Boris Tsybakov
Error Probabilities for Identification Coding and Least Length Single Sequence Hopping	221	(18)
Edward C. van der Meulen
Sandor Csibi
Combinatorial and Algebraic Coding
A New Upper Bound On Codes Decodable Into Size-2 Lists	239	(6)
Alexei Ashikmin
Alexander Barg
Simon Litsyn
Constructions of Optimal Linear Codes	245	(20)
Stefan Dodunekov
Juriaan Simonis
New Applications and Results of Superimposed Code Theory Arising from the Potentialities of Molecular Biology	265	(18)
Arkadii G. D'yachkov
Anthony J. Macula
Vyacheslav V. Rykov
Rudified Convolutional Encoders	283	(12)
Rolf Johannesson
On Check Digit Systems Using Anti--symmetric Mappings	295	(16)
Ralph--Hardo Schulz
Switchings and Perfect Codes	311	(14)
Faina I. Solov'eva
On Superimposed Codes	325	(8)
A.J. Han Vinck
Samuel Martirossian
The MacWilliams Identity for Linear Codes over Galois Rings	333	(6)
Zhe-Xian Wan
Cryptology
Structure of a Common Knowledge Created by Correlated Observations and Transmission over Helping Channels	339	(14)
Vladimir B. Balakirsky
How to Broadcast Privacy: Secret Coding for Deterministic Broadcast Channels	353	(16)
Ning Cai
Kwok Yan Lam
Additive--Like Instantaneous Block Encipherers	369	(6)
Zhaozhi Zhang
Information Theory and the Related Fields Data Compression, Entropy Theory, Symbolic Dynamics, Probability and Statistics
Space Efficient Linear Time Computation of the Burrows and Wheeler-Transformation	375	(10)
Stefan Kurtz
Bernhard Balkenhol
Sequences Incompressible by SLZ (LZW), yet Fully Compressible by ULZ	385	(6)
Larry A. Pierce II
Paul C. Shields
Universal Coding of Non-Prefix Context Tree Sources	391	(12)
Yuri M. Shtarkov
How Much Can You Win When Your Adversary is Handicapped?	403	(10)
Ludwig Staiger
On Random-Access Data Compaction	413	(8)
Frans M.J. Willems
Tjalling J. Tjalkens
Paul A.J. Volf
Universal Lossless Coding of Sources with Large and Unbounded Alphabets	421	(22)
En-hui Yang
Yunwei Jia
Metric Entropy Conditions for Kernels	443	(10)
Bernd Carl
On Subshifts and Topological Markov Chains	453	(20)
Wolfgang Krieger
Large Deviations Problem for the Shape of a Random Young Diagram with Restrictions	473	(16)
Vladimir Blinovsky
BSC: Testing of Hypotheses with Information Constraints	489	(12)
Marat V. Burnashev
Shun-inchi Amari
Te Sun Han
The Ahlswede-Daykin Theorem	501	(16)
Peter C. Fischburn
Lawrence Shepp
Some Aspects of Random Shapes	517	(8)
Herbert Ziezold
COMPLEXITY
Decision Support Systems with Multiple Choice Structure	525	(16)
Ingo Althofer
Quantum Computers and Quantum Automata	541	(14)
Rusins Freivalds
Routing in All-Optical Networks	555	(24)
Luisa Gargano
Ugo Vaccaro
Proving the Correctness of Processors with Delayed Branch Using Delayed PC	579	(10)
Silvia M. Mueller
Wolfgang J. Paul
Daniel Kroening
Communication Complexity of Functions on Direct Sums	589	(14)
Ulrich Tamm
Ordering in Sequence Spaces: an Overview	603	(12)
Peter Vanroose
Communication Complexity and BDD Lower Bound Techniques	615	(14)
Ingo Wegener
Reminiscences About Professor Ahlswede And A Last Word	629	(4)
Thomas Mann
List of Invited Lectures held at the Symposium ``Numbers, Information and Complexity'' in Bielefeld, October 8-11, 1998	633	(4)
Bibliography of Publications	637	(14)
Rudolf Ahlswede
Index	651