2-DIMENSIONAL PATTERN-MATCHING BY SAMPLING

Authors
CROCHEMORE M GASIENIEC L RYTTER W
Citation
M. Crochemore et al., 2-DIMENSIONAL PATTERN-MATCHING BY SAMPLING, Information processing letters, 46(4), 1993, pp. 159-162
Citations number
11
Categorie Soggetti
Information Science & Library Science","Computer Applications & Cybernetics
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
46
Issue
4
Year of publication
1993
Pages
159 - 162
Database
ISI
SICI code
0020-0190(1993)46:4<159:2PBS>2.0.ZU;2-T
Abstract
We extend the concept of deterministic sampling to the two-dimensional pattern matching problem. We show that almost all patterns have a log arithmic deterministic sample. There are 2D-matching algorithms which work efficiently for almost all patterns. They solve the 2D-matching p roblem in linear sequential time with O(1) space, or, alternatively in O(1) parallel time with linear number of processors. This is the firs t attempt to reduce the space for two-dimensional pattern matching.