Combinatorial Algorithms on Words
Combinatorial Algorithms on Words refers to the collection of manipulations of strings of symbols (words) - not necessarily from a finite alphabet - that exploit the combinatorial properties of the logical/physical input arrangement to achieve efficient computational performances. The model of compu...
| Other Authors: | , |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
1985, 1985
|
| Edition: | 1st ed. 1985 |
| Series: | NATO ASI Subseries F:, Computer and Systems Sciences
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- Open Problems in Stringology
- 1 — String Matching
- Efficient String Matching with Don’t-care Patterns
- Optimal Factor Transducers
- Relating the Average-case Cost of the Brute force and the Knuth-Morris-Pratt String Matching Algorithm
- Algorithms for Factorizing and Testing Subsemigroups
- 2 — Subword Trees
- The Myriad Virtues of Subword Trees
- Efficient and Elegant Subword Tree Construction
- 3 — Data Compression
- Textual Substitution Techniques for Data Compression
- Variations on a Theme by Ziv and Lempel
- Compression of Two-dimensional Images
- Optimal Parsing of Strings
- Novel Compression of Sparse Bit Strings
- 4 — Counting
- The Use and Usefulness of Numeration Systems
- Enumeration of Strings
- Two Counting Problems Solved via String Encodings
- Some Uses of the Mellin integral Transform in the Analysis of Algorithms
- 5 — Periods and Other Regularities
- Periodicities in Strings
- Linear Time Recognition of Square free Strings
- Discovering Repetitions in Strings
- Some Decision Results on Nonrepetitive Words
- 6 — Miscellaneous
- On the Complexity of some Word Problems Which Arise in Testing the Security of Protocols
- Code Properties and Derivatives of DOL Systems
- Words over a Partially Commutative Alphabet
- The Complexity of Two-way Pushdown Automata and Recursive Programs
- On Context Free Grammars and Random Number Generation