Sequences: Combinatorics, Compression, Security, and Transmission

✍ Scribed by Amihood Amir, Gad M. Landau (auth.), Renato M. Capocelli (eds.)

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

✦ Synopsis

This volume contains all papers pres- ented at the Advanced International Workshop on Sequences: Combinatorics, Compression, and Transmission which was held Monday, June 6, through Saturday, June 11, 1988, at the Palazzo Serra di Cassano, Naples and at the Hotel Covo dei Saraceni, Positano, Italy. The workshop was sponsored by the Dipartimento di Informatica ed Applicazioni of the University of Salerno, by the Instituto Italiano per gli Studi Filosofici of Naples and the National Research Council of Italy (C.N.R.).

✦ Table of Contents

Front Matter....Pages i-xii
Front Matter....Pages 1-1
Fast Parallel and Serial Multidimensional Approximate Array Matching....Pages 3-24
Context-Dependent String Matching....Pages 25-40
Constant-Space String-Matching....Pages 41-44
Matching Patterns in Strings Subject to Multi-Linear Transformations....Pages 45-58
Efficient Algorithms with Applications to Molecular Biology....Pages 59-74
A Survey of Approximation Algorithms for the Permanent....Pages 75-91
On optimal parallel computations for sequences of brackets....Pages 92-102
Front Matter....Pages 107-107
Universal sequences and graph cover times A short survey....Pages 109-122
Fibonacci Facts and Formulas....Pages 123-137
On the influence of single participant in coin flipping schemes....Pages 138-143
Zero-error capacities and very different sequences....Pages 144-155
Sequences of Lyndon Words....Pages 156-165
A Note on Addition Chains and some Related Conjectures....Pages 166-181
Some Applications of Probability Methods to Number Theory. Successes and Limitations....Pages 182-194
On Pseudo-Random Arrays Constructed from Patterns with distinct Differences....Pages 195-207
Combinatorial Designs Derived from Costas Arrays....Pages 208-227
Algorithms for determining relative star height and star height....Pages 228-243
Eigenwords and Periodic Behaviors....Pages 244-253
Infinite Words and a Problem in Semigroup Theory....Pages 254-257
Some Combinatorial Properties of Factorial Languages....Pages 258-266
Front Matter....Pages 107-107
A Conjecture on Rational Sequences....Pages 267-274
Sequences Defined by Iterated Morphisms....Pages 275-286
Encoding the vertices of a graph with binary edge labels....Pages 287-299
Front Matter....Pages 301-301
Applications of DAWGs to Data Compression....Pages 303-311
Coding and Complexity....Pages 312-325
Compression of Pictures by Finite State Encoders....Pages 326-347
Lossy On-Line Dynamic Data Compression....Pages 348-357
A Comparison of Text Compression Algorithms....Pages 358-365
Compression, Tests for Randomness and Estimating the Statistical Model of an Individual Sequence....Pages 366-373
Front Matter....Pages 375-375
Removing Interaction from Zero-Knowledge Proofs....Pages 377-393
Protecting against Abuses of Cryptosystems in Particular in the Context of Verification of Peace Treaties....Pages 394-405
The Information Dispersal Algorithm and its Applications....Pages 406-419
Three Types of Perfection in Shannon-Theoretic Cryptography....Pages 420-425
Front Matter....Pages 427-427
Codes for Certain Sofic Systems....Pages 429-432
Simple Combinatorial Decoding of the [23,12,7] Golay Code....Pages 433-448
Flag Encodings Related to the Zeckendorf Representation of Integers....Pages 449-466
Immutable Codes....Pages 467-478
Unison in Distributed Networks....Pages 479-487
Sequence Transmission: Coding in the Frequency Domain....Pages 488-505
On the Maximality of the Group Theoretic Single Error Correcting and All Unidirectional Error Detecting (SEC-AUED) Codes....Pages 506-529
Front Matter....Pages 427-427
Coding Sequences with Constraints....Pages 530-540
Robust Error Control Sequences for Efficient Software Implementation....Pages 541-547
Back Matter....Pages 549-549

✦ Subjects

Mathematical Modeling and Industrial Mathematics;Numerical Analysis;Theory of Computation;Coding and Information Theory;Combinatorics;Appl.Mathematics/Computational Methods of Engineering