We propose a framework for pattern matching in twodimensional arrays of symbols where the patterns are described by an extended version of the regular matrix grammar and the size of desired matches is prescribed. We then demonstrate how to reformulate the 2D pattern matching as the one-dimensional pattern matching (string pattern matching), and study the efficiency of the string pattern matching algorithm based on pattern complexity with respect to two finite automaton models: (1) the classical finite automaton and (2) the finite automaton equipped with two scanning heads placed in a fixed distance. We also identify several subclasses of the considered templates for which the framework yields a more efficient matching than the naive algorithm.
|Title of host publication||Combinatorial Image Analysis - 18th International Workshop, IWCIA 2017, Proceedings|
|Editors||Reneta P. Barneva, Valentin E. Brimkov, Valentin E. Brimkov|
|Number of pages||14|
|Publication status||Published - 2017|
|Event||18th International Workshop on Combinatorial Image Analysis, IWCIA 2017 - Plovdiv, Bulgaria|
Duration: 2017 Jun 19 → 2017 Jun 21
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Other||18th International Workshop on Combinatorial Image Analysis, IWCIA 2017|
|Period||17/6/19 → 17/6/21|
Bibliographical noteFunding Information:
Han was supported by the Basic Science Research Program through NRF funded by MEST (2015R1D1A1A01060097) and the IITP grant funded by the Korea government (MSIP) (R0124-16-0002), and Průša was supported by the Czech Science Foundation under grant no. 15-04960S.
© Springer International Publishing AG 2017.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)