Title | Combinatorial Algorithms on Words [electronic resource] / edited by Alberto Apostolico, Zvi Galil |
---|---|
Imprint | Berlin, Heidelberg : Springer Berlin Heidelberg, 1985 |
Connect to | http://dx.doi.org/10.1007/978-3-642-82456-2 |
Descript | VIII, 363 p. online resource |
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