Template-Based Pattern Matching in Two-Dimensional Arrays

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F17%3A00312204" target="_blank" >RIV/68407700:21230/17:00312204 - isvavai.cz</a>

Výsledek na webu

<a href="https://link.springer.com/chapter/10.1007/978-3-319-59108-7_7" target="_blank" >https://link.springer.com/chapter/10.1007/978-3-319-59108-7_7</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-59108-7_7" target="_blank" >10.1007/978-3-319-59108-7_7</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Template-Based Pattern Matching in Two-Dimensional Arrays

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Template-Based Pattern Matching in Two-Dimensional Arrays

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA15-04960S" target="_blank" >GA15-04960S: SeLeCt - struktury, učení a kognice</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Combinatorial Image Analysis

ISBN

978-3-319-59107-0

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

14

Strana od-do

79-92

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Plovdiv

Datum konání akce

19. 6. 2017

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—