Template-based pattern matching in two-dimensional arrays

Yo Sub Han; Daniel Průša

doi:10.1007/978-3-319-59108-7_7

Template-based pattern matching in two-dimensional arrays

Yo Sub Han, Daniel Průša

College of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Combinatorial Image Analysis - 18th International Workshop, IWCIA 2017, Proceedings
Editors	Reneta P. Barneva, Valentin E. Brimkov, Valentin E. Brimkov
Publisher	Springer Verlag
Pages	79-92
Number of pages	14
ISBN (Print)	9783319591070
DOIs	https://doi.org/10.1007/978-3-319-59108-7_7
Publication status	Published - 2017
Event	18th International Workshop on Combinatorial Image Analysis, IWCIA 2017 - Plovdiv, Bulgaria Duration: 2017 Jun 19 → 2017 Jun 21

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10256 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	18th International Workshop on Combinatorial Image Analysis, IWCIA 2017
Country/Territory	Bulgaria
City	Plovdiv
Period	17/6/19 → 17/6/21

Bibliographical note

Publisher Copyright:
© Springer International Publishing AG 2017.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-59108-7_7

Cite this

Han, Y. S., & Průša, D. (2017). Template-based pattern matching in two-dimensional arrays. In R. P. Barneva, V. E. Brimkov, & V. E. Brimkov (Eds.), Combinatorial Image Analysis - 18th International Workshop, IWCIA 2017, Proceedings (pp. 79-92). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10256 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-59108-7_7

Han, Yo Sub ; Průša, Daniel. / Template-based pattern matching in two-dimensional arrays. Combinatorial Image Analysis - 18th International Workshop, IWCIA 2017, Proceedings. editor / Reneta P. Barneva ; Valentin E. Brimkov ; Valentin E. Brimkov. Springer Verlag, 2017. pp. 79-92 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{474f68a10a0342f2ba3ae0e08467f225,

title = "Template-based pattern matching in two-dimensional arrays",

abstract = "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.",

keywords = "Finite automata, Matrix grammars, Multi-head automata, Pattern complexity, Two-dimensional pattern matching",

author = "Han, {Yo Sub} and Daniel Prů{\v s}a",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 18th International Workshop on Combinatorial Image Analysis, IWCIA 2017 ; Conference date: 19-06-2017 Through 21-06-2017",

year = "2017",

doi = "10.1007/978-3-319-59108-7_7",

language = "English",

isbn = "9783319591070",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "79--92",

editor = "Barneva, {Reneta P.} and Brimkov, {Valentin E.} and Brimkov, {Valentin E.}",

booktitle = "Combinatorial Image Analysis - 18th International Workshop, IWCIA 2017, Proceedings",

address = "Germany",

}

Han, YS & Průša, D 2017, Template-based pattern matching in two-dimensional arrays. in RP Barneva, VE Brimkov & VE Brimkov (eds), Combinatorial Image Analysis - 18th International Workshop, IWCIA 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10256 LNCS, Springer Verlag, pp. 79-92, 18th International Workshop on Combinatorial Image Analysis, IWCIA 2017, Plovdiv, Bulgaria, 17/6/19. https://doi.org/10.1007/978-3-319-59108-7_7

Template-based pattern matching in two-dimensional arrays. / Han, Yo Sub; Průša, Daniel.
Combinatorial Image Analysis - 18th International Workshop, IWCIA 2017, Proceedings. ed. / Reneta P. Barneva; Valentin E. Brimkov; Valentin E. Brimkov. Springer Verlag, 2017. p. 79-92 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10256 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Template-based pattern matching in two-dimensional arrays

AU - Han, Yo Sub

AU - Průša, Daniel

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Finite automata

KW - Matrix grammars

KW - Multi-head automata

KW - Pattern complexity

KW - Two-dimensional pattern matching

UR - http://www.scopus.com/inward/record.url?scp=85020463059&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85020463059&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-59108-7_7

DO - 10.1007/978-3-319-59108-7_7

M3 - Conference contribution

AN - SCOPUS:85020463059

SN - 9783319591070

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 79

EP - 92

BT - Combinatorial Image Analysis - 18th International Workshop, IWCIA 2017, Proceedings

A2 - Barneva, Reneta P.

A2 - Brimkov, Valentin E.

PB - Springer Verlag

T2 - 18th International Workshop on Combinatorial Image Analysis, IWCIA 2017

Y2 - 19 June 2017 through 21 June 2017

ER -

Han YS, Průša D. Template-based pattern matching in two-dimensional arrays. In Barneva RP, Brimkov VE, Brimkov VE, editors, Combinatorial Image Analysis - 18th International Workshop, IWCIA 2017, Proceedings. Springer Verlag. 2017. p. 79-92. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-59108-7_7

Template-based pattern matching in two-dimensional arrays

Abstract

Publication series

Other

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this