Seminar WS1995/96 Combinatorial Pattern Matching

1 Optimal Parsing of Strings

A. Hartman, M. Rodeh, Optimal Parsing of Strings, In: Combinatorical Algorithms on Words, A. Apostolico, Z. Galil (Ed.), Springer, 1985, 155–167

2 Searching Subsequences

Ricardo A. Baeza-Yates, Searching Subsequences, Theoretical Computer Science, Vol. 78, 1991, 363–376

3 Approximating Shortest Superstrings

Shang-Hua Teng, Frances Yao, Approximating Shortest Superstrings, Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (FOCS), 1993, 158–165

4 Time-Space Optimal String Matching

M. Crochemore, String Matching on Ordered Alphabets, Theoretical Computer Science, Vol. 92, 1992, 33–47

5 Suffix Arrays

Udi Manber, Gene Myers, Suffix Arrays: A New Method for On-Line String Searches, SIAM Journal on Computing, Vol. 22, Oct. 1993, 935–948

6 Suffix Binary Search Trees

Rob Irving, Suffix Binary Search Trees, Technical Report TR-1995-7, Department of Computing Science, University of Glasgow, April 1995

7 Computing Covers of a String

Dennis Moore, W.F. Smyth, An Optimal Algorithm to Compute All the Covers of a String, Information Processing Letters, Vol. 50, 1994, 239–246

Dennis Moore, W.F. Smyth, A Correction to “An Optimal Algorithm to Compute All the Covers of a String”, Information Processing Letters, Vol. 54, 1995, 101–103

8 Dynamic Dictionary Matching

Ramana M. Idury, Alejandro A. Schäffer, Dynamic Dictionary Matching with Failure Functions, Theoretical Computer Science, Vol. 131, 1994, 295–310

9 Finding Repetitions in a String

Michael G. Main, Richard J. Lorentz, An O(n log n) Algorithm for Finding All Repetitions in a String, Journal of Algorithms, Vol. 5, 1984, 422-432

S. Rao Kosaraju, Computation of Squares in a String, 5th Annual Symp. on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 807, 1994, 146-150

10 Fast Multiple Keyword Searching

Jong Yong Kim, John Shawe-Taylor, Fast Multiple Keyword Searching, 3rd Annual Symp. on Combinatorial Pattern Matching, Lectures Notes in Computer Science, Vol. 644, 1992, 41–51

11 Speeding up Dynamic Programming

Zvi Galil, Raffaele Giancarlo, Speeding up Dynamic Programming with Applications to Molecular Biology, Theoretical Computer Science, Vol 64, 1989, 107–118

12 String Matching with Don’t-Care Patterns

Ron Y. Pinter, Efficient String Matching with Don’t-Care Patterns, In: A. Apostolico and Z. Galil (eds.), Combinatorial Algorithms on Words, NATO Advanced Science Institute Series F: Computer and System Sciences, Vol. 12, 1985, 11–29

13 Multiple Sequence Alignment 1

John Kececioglu, The Maximum Weight Trace Problem in Multiple Sequence Alignment, 4th Annual Symp. on Combinatorial Pattern Matching, Lecture Notes in Computer Science, Vol. 684, 1993, 106–119

14 Multiple Sequence Alignment 2

J. Meidanis, J. Setubal, Multiple Alignment of Biological Sequences with Gap Flexibility, LA-TIN’95: Theoretical Informatics, Lecture Notes in Computer Science, 1995, Vol. 911, 411–426

15 Approximate String Matching with Suffix Automata

Esko Ukkonen, Derick Wood, Approximate String Matching with Suffix Automata, Algorithmica, Vol. 10, 1993, 353–364

16 Efficient Text Searching of Regular Expressions

Ricardo A. Baeza-Yates, Efficient Text Searching of Regular Expressions, ICALP’89, Lecture Notes in Computer Science, Vol. 372 1989, 46–62

Wie hält man einen Informatik-Seminarvortrag?

Tips zur Vorbereitung eines Vortrags können über das World Wide Web unter der Adresse

http://eos.informatik.uni-bonn.de:8080/~rick/cpm.html abgerufen werden!