Presentation | 2010-04-22 Transposition Invariant Fully Compressed Pattern Matching Algorithm Wataru MATSUBARA, Ayumi SHINOHARA, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Transposition invariant pattern matching is the problem of matching given text and pattern to find the occurrence in the case where the pattern may be transformed by applying renaming bijection. This paper studies an problem on compressed string in terms of straight line programs (SLPs). We show efficient algorithms for transposition invariant fully compressed pattern matching and some generalized problem. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | compression / pattern matching / straight line program |
Paper # | COMP2010-6 |
Date of Issue |
Conference Information | |
Committee | COMP |
---|---|
Conference Date | 2010/4/15(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Theoretical Foundations of Computing (COMP) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Transposition Invariant Fully Compressed Pattern Matching Algorithm |
Sub Title (in English) | |
Keyword(1) | compression |
Keyword(2) | pattern matching |
Keyword(3) | straight line program |
1st Author's Name | Wataru MATSUBARA |
1st Author's Affiliation | Tohoku University() |
2nd Author's Name | Ayumi SHINOHARA |
2nd Author's Affiliation | Tohoku University |
Date | 2010-04-22 |
Paper # | COMP2010-6 |
Volume (vol) | vol.110 |
Number (no) | 12 |
Page | pp.pp.- |
#Pages | 7 |
Date of Issue |