Long Common Subsequences and the Proximity of two Random Strings.

Abstract

Let (x(1), x(2),. . ., x(n)) and (x(1), x(2),. . ., x(n)) be two strings from an alphabet a, and let L(n) deonte their longest common subsequence. The probabilistic behavior of L(n) is studied under various probability models for the x and x'strings.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 06, 1980
Accession Number
ADA092610

Entities

People

  • J. Michael Steele

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computer Science
  • Couplings
  • Data Processing
  • Ergodic Processes
  • Inequalities
  • Markov Chains
  • Markov Processes
  • New York
  • Probability
  • Random Variables
  • Sequences
  • Stationary Processes
  • Statistics
  • Stochastic Processes
  • Theorems
  • United States

Fields of Study

  • Mathematics

Readers

  • Computer Programming and Software Development.
  • Mathematical Modeling and Probability Theory.