Back to Search
Start Over
Finite Automata Approach to Computing All Seeds of Strings with the Smallest Hamming Distance.
- Source :
- IAENG International Journal of Computer Science; May2009, Vol. 36 Issue 2, p1-10, 10p, 9 Diagrams, 1 Chart, 3 Graphs
- Publication Year :
- 2009
-
Abstract
- Seed is a type of a regularity of strings. A restricted approximate seed w of string T is a factor of T such that w covers a superstring of T under some distance rule. In this paper, the problem of all restricted seeds with the smallest Hamming distance is studied and a polynomial time and space algorithm for solving the problem is presented. It searches for all restricted approximate seeds of a string with given limited approximation using Hamming distance and it computes the smallest distance for each found seed. The solution is based on a finite (suffix) automata approach that provides a straightforward way to design algorithms to many problems in stringology. Therefore, it is shown that the set of problems solvable using finite automata includes the one studied in this paper. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 1819656X
- Volume :
- 36
- Issue :
- 2
- Database :
- Supplemental Index
- Journal :
- IAENG International Journal of Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 42407674