Sequences II: Methods in Communication, Security, and Computer Science

✍ Scribed by Ian F. Blake, George H. Freeman, Peter R. Stubley (auth.), Renato Capocelli, Alfredo De Santis, Ugo Vaccaro (eds.)

• Publisher: Springer-Verlag New York
• Year: 1993
• Tongue: English
• Leaves: 484
• Edition: 1
• Category: Library

✦ Synopsis

This volume provides an up-to-date view of several topics in theoretical computer science and suggests directions for future research. It constitutes a valuable working tool for mathematicians, electrical engineers and computer scientists and will be of interest to researchers and graduate students in combinatorics, cryptography, information compression and transmission, or mathematics applied to engineering. Among the contributions to this volume, all by world-renowned scientists, are: Ramsey theory applied to showing the existence of arithmetic subsequences with applications to molecular biology; methods for finding the smallest possible Markov Chain that could produce a given sequence of numbers; construction of pseudo-random arrays; the relationship between stochastic complexity and data compression; string matching algorithms; parallel algorithms for string matching in various contexts; string and picture compression; dynamic data compression; coding sequences with constraints; universal sequences for graphs; coding theory; combinatorial issues, including techniques for designing error-correcting codes; and applications of information theory to external set theory. In addition, there are various contributions in related subjects such as distributed computing, approximation algorithms, and cryptography.

✦ Table of Contents

Front Matter....Pages i-xvii
Front Matter....Pages 1-1
On the enumeration of dyadic distributions....Pages 3-11
Detection of Skew in a Sequence of Subsets....Pages 12-23
Asymmetric Error Correcting Codes....Pages 24-35
Binary Perfect Weighted Coverings (PWC)....Pages 36-51
Read/Write Isolated Memory....Pages 52-58
Polynomial-time construction of linear codes with almost equal weights....Pages 59-62
Welch’s Bound and Sequence Sets for Code-Division Multiple-Access Systems....Pages 63-78
Average-case interactive communication....Pages 79-103
Adaptive Lossless Data Compression over a Noisy Channel....Pages 104-117
Front Matter....Pages 119-119
Parallel string matching algorithms....Pages 121-142
Some applications of Rabin’s fingerprinting method....Pages 143-152
Periodic Prefixes in Texts....Pages 153-165
Reconstructing sequences from shotgun data....Pages 166-188
A Systematic Design and Explanation of the Atrubin Multiplier....Pages 189-202
On the Shannon Capacity of Graph Formulae....Pages 203-217
An Efficient Algorithm for the All Pairs Suffix-Prefix Problem....Pages 218-224
Efficient Algorithms for Sequence Analysis....Pages 225-244
Coding Trees as Strings for Approximate Tree Matching....Pages 245-259
Deciding Code Related Properties by Means of Finite Transducers....Pages 260-272
On the Derivation of Spline Bases....Pages 273-291
Front Matter....Pages 119-119
Optimal Parallel Pattern Matching Through Randomization....Pages 292-299
Approximate string-matching and the q -gram distance....Pages 300-312
Universal Discrimination of Individual Sequences via Finite-State Classifiers....Pages 313-325
Front Matter....Pages 327-327
Improving the Efficiency and Reliability of Digital Time-Stamping....Pages 329-334
A Note on Secret Sharing Schemes....Pages 335-344
Privacy of Dense Symmetric Functions....Pages 345-359
Efficient Reduction among Oblivious Transfer Protocols based on New Self-Intersecting Codes....Pages 360-368
Perfect Zero-Knowledge Sharing Schemes over any Finite Abelian Group....Pages 369-378
Some Comments on the Computation of n -th Roots in Z N ....Pages 379-391
The Varieties of Secure Distributed Computation....Pages 392-417
Fair Games Against an All-Powerful Adversary....Pages 418-429
An Asymptotic Coding Theorem for Authentication and Secrecy....Pages 430-436
Front Matter....Pages 437-437
Gray Codes and Strongly Square-Free Strings....Pages 439-446
A New Unavoidable Regularity in Free Monoids....Pages 447-456
The Star Height One Problem for Irreducible Automata....Pages 457-469
Synchronizing Automata....Pages 470-476
Back Matter....Pages 477-477

✦ Subjects

Theory of Computation; Appl.Mathematics/Computational Methods of Engineering; Combinatorics; Coding and Information Theory