Skip to main content
SpringerLink
Log in

Combinatorial Pattern Matching

4th Annual Symposium, CPM 93, Padova, Italy, June 2-4, 1993. Proceedings

  • Conference proceedings
  • © 1993

Overview

Editors:
  1. Alberto Apostolico
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Maxime Crochemore
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Zvi Galil
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Udi Manber
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 684)

Included in the following conference series:

Conference proceedings info: CPM 1993.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
Softcover Book USD 69.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (19 papers)

  1. Front Matter

    Download chapter PDF

  2. A linear time pattern matching algorithm between a string and a tree

    • Tatsuya Akutsu
    Pages 1-10

  3. Tight comparison bounds for the string prefix-matching problem

    • Dany Breslauer, Livio Colussi, Laura Toniolo
    Pages 11-19

  4. 3-D docking of protein molecules

    • Daniel Fischer, Raquel Norel, Ruth Nussinov, Haim J. Wolfson
    Pages 20-34

  5. Minimal separators of two words

    • E. Garel
    Pages 35-53

  6. Covering a string

    • Costas S. Iliopoulos, Dennis W. G. Moore, Kunsoo Park
    Pages 54-62

  7. On the worst-case behaviour of some approximation algorithms for the shortest common supersequence of k strings

    • Robert W. Irving, Campbell B. Fraser
    Pages 63-73

  8. An algorithm for locating non-overlapping regions of maximum alignment score

    • Sampath K. Kannan, Eugene. W. Myers
    Pages 74-86

  9. Exact and approximation algorithms for the inversion distance between two chromosomes

    • John Kececioglu, David Sankoff
    Pages 87-105

  10. The maximum weight trace problem in multiple sequence alignment

    • John Kececioglu
    Pages 106-119

  11. An algorithm for approximate tandem repeats

    • Gad M. Landau, Jeanette P. Schmidt
    Pages 120-133

  12. Two dimensional pattern matching in a digitized image

    • Gad M. Landau, Uzi Vishkin
    Pages 134-151

  13. Analysis of a string edit problem in a probabilistic framework

    • Guy Louchard, Wojciech Szpankowski
    Pages 152-163

  14. Detecting false matches in string matching algorithms

    • S. Muthukrishnan
    Pages 164-178

  15. On suboptimal alignments of biological sequences

    • Dalit Naor, Douglas Brutlag
    Pages 179-196

  16. A fast filtration algorithm for the substring matching problem

    • Pavel A. Pevzner, Michael S. Waterman
    Pages 197-214

  17. A unifying look at d-dimensional periodicities and space coverings

    • Mireille Régnier, Ladan Rostami
    Pages 215-227

  18. Approximate string-matching over suffix trees

    • Esko Ukkonen
    Pages 228-242

  19. Multiple sequence comparison and n-dimensional image reconstruction

    • Martin Vingron, Pavel A. Pevzner
    Pages 243-253

  20. A new editing based distance between unordered labeled trees

    • Kaizhong Zhang
    Pages 254-265
Back to top

Other volumes

  1. Combinatorial Pattern Matching

Keywords

About this book

The papers contained in this volume were presented at the Fourth Annual Symposium on Combinatorial Pattern Matching, held in Padova, Italy, in June 1993. Combinatorial pattern matching addresses issues of searching and matching of strings and more complicated patterns such as trees, regular expressions, extended expressions, etc. The goal is to derive nontrivial combinatorial properties for such structures and then to exploit these properties in order to achieve superior performance for the corresponding computational problems. In recent years, a steady flow of high-quality scientific studies of this subject has changed a sparse set of isolated results into a full-fledged area of algorithmics. The area is expected to grow even further due to the increasing demand for speedand efficiency that comes especially from molecular biology and the Genome project, but also from other diverse areas such as information retrieval, pattern recognition, compilers, data compression, and program analysis.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation