Searching All Seeds of Strings with Hamming Distance using Finite Automata.
Saved in:
| Title: | Searching All Seeds of Strings with Hamming Distance using Finite Automata. |
|---|---|
| Authors: | Guth, Ondřej1 gutho1@fel.cvut.cz, Melichar, Bořivoj1 melichar@fel.cvut.cz |
| Source: | International MultiConference of Engineers & Computer Scientists 2009. 2009, p622-629. 8p. 5 Diagrams, 1 Chart, 3 Graphs. |
| Subjects: | Sequential machine theory, Spacetime, Approximation theory, Machine theory, Algorithms |
| 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] |
| Copyright of International MultiConference of Engineers & Computer Scientists 2009 is the property of International Association of Engineers (IAENG) and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 41021155 AccessLevel: 6 PubType: Book PubTypeId: book PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Searching All Seeds of Strings with Hamming Distance using Finite Automata. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Guth%2C+Ondřej%22">Guth, Ondřej</searchLink><relatesTo>1</relatesTo><i> gutho1@fel.cvut.cz</i><br /><searchLink fieldCode="AR" term="%22Melichar%2C+Bořivoj%22">Melichar, Bořivoj</searchLink><relatesTo>1</relatesTo><i> melichar@fel.cvut.cz</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22International+MultiConference+of+Engineers+%26+Computer+Scientists+2009%22">International MultiConference of Engineers & Computer Scientists 2009</searchLink>. 2009, p622-629. 8p. 5 Diagrams, 1 Chart, 3 Graphs. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Sequential+machine+theory%22">Sequential machine theory</searchLink><br /><searchLink fieldCode="DE" term="%22Spacetime%22">Spacetime</searchLink><br /><searchLink fieldCode="DE" term="%22Approximation+theory%22">Approximation theory</searchLink><br /><searchLink fieldCode="DE" term="%22Machine+theory%22">Machine theory</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of International MultiConference of Engineers & Computer Scientists 2009 is the property of International Association of Engineers (IAENG) and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=41021155 |
| RecordInfo | BibRecord: BibEntity: Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 8 StartPage: 622 Subjects: – SubjectFull: Sequential machine theory Type: general – SubjectFull: Spacetime Type: general – SubjectFull: Approximation theory Type: general – SubjectFull: Machine theory Type: general – SubjectFull: Algorithms Type: general Titles: – TitleFull: Searching All Seeds of Strings with Hamming Distance using Finite Automata. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Guth, Ondřej – PersonEntity: Name: NameFull: Melichar, Bořivoj IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 01 Text: 2009 Type: published Y: 2009 Titles: – TitleFull: International MultiConference of Engineers & Computer Scientists 2009 Type: main |
| ResultId | 1 |
