Skip to main content
SpringerLink
Log in
Book cover

Combinatorial Pattern Matching

Fifth Annual Symposium, CPM '94, Asilomar, CA, USA, June 5 - 8, 1994. Proceedings

  • Conference proceedings
  • © 1994

Overview

Editors:
  1. Maxime Crochemore
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Dan Gusfield
    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 807)

Included in the following conference series:

Conference proceedings info: CPM 1994.

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 54.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 (26 papers)

  1. Front Matter

    Download chapter PDF

  2. A space efficient algorithm for finding the best non-overlapping alignment score

    • Gary Benson
    Pages 1-14

  3. The parameterized complexity of sequence alignment and consensus

    • Hans Bodlaender, Rodney G. Downey, Michael R. Fellows, Harold T. Wareham
    Pages 15-30

  4. Computing all suboptimal alignments in linear space

    • Kun -Mao Chao
    Pages 31-42

  5. Approximation algorithms for multiple sequence alignment

    • Vineet Bafna, Eugene L. Lawler, Pavel A. Pevzner
    Pages 43-53

  6. A context dependent method for comparing sequences

    • Xiaoqiu Huang
    Pages 54-63

  7. Fast identification of approximately matching substrings

    • Archie L. Cobbs
    Pages 64-74

  8. Alignment of trees — An alternative to tree edit

    • Tao Jiang, Lusheng Wang, Kaizhong Zhang
    Pages 75-86

  9. Parametric recomputing in alignment graphs

    • Xiaoqiu Huang, Pavel A. Pevzner, Webb Miller
    Pages 87-101

  10. A lossy data compression based on string matching: Preliminary analysis and suboptimal algorithms

    • Tomasz Luczak, Wojciech Szpankowski
    Pages 102-112

  11. A text compression scheme that allows fast searching directly in the compressed file

    • Udi Manber
    Pages 113-124

  12. An alphabet-independent optimal parallel search for three dimensional pattern

    • Marek Karpinski, Wojciech Rytter
    Pages 125-135

  13. Unit route upper bound for string-matching on hypercube

    • L. Lestré
    Pages 136-145

  14. Computation of squares in a string

    • S. Rao Kosaraju
    Pages 146-150

  15. Minimization of sequential transducers

    • Mehryar Mohri
    Pages 151-163

  16. Shortest common superstrings for strings of random letters

    • Kenneth S. Alexander
    Pages 164-172

  17. Maximal common subsequences and minimal common supersequences

    • Robert W. Irving, Campbell B. Fraser
    Pages 173-183

  18. Dictionary-matching on unbounded alphabets: Uniform length dictionaries

    • Dany Breslauer
    Pages 184-197

  19. Proximity matching using fixed-queries trees

    • Ricardo Baeza-Yates, Walter Cunto, Udi Manber, Sun Wu
    Pages 198-212

  20. Query primitives for tree-structured data

    • Pekka Kilpeläinen, Heikki Mannila
    Pages 213-225
Back to top

Other volumes

  1. Combinatorial Pattern Matching

Keywords

About this book

This volume presents the proceedings of the Fifth Annual Symposium on Combinatorial Pattern Matching, held at Asilomar, California, in June 1994. The 26 selected papers in this volume are organized in chapters on Alignments, Various Matchings, Combinatorial Aspects, and Bio-Informatics. Combinatorial Pattern Matching addresses issues of searching and matching of strings and more complicated patterns, as for example trees. The goal is to derive non-trivial 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, combinatorial pattern matching has developed into a full-fledged area of algorithmics and is expected to grow even further during the next years.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation