Complexity of Matching Sets of Two-Dimensional Patterns by Two-Dimensional On-Line Tessellation Automaton

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="http://www.worldscientific.com/doi/abs/10.1142/S012905411740010X" target="_blank" >http://www.worldscientific.com/doi/abs/10.1142/S012905411740010X</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1142/S012905411740010X" target="_blank" >10.1142/S012905411740010X</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Complexity of Matching Sets of Two-Dimensional Patterns by Two-Dimensional On-Line Tessellation Automaton

Popis výsledku v původním jazyce

We study the two-dimensional pattern matching implemented using the deterministic two-dimensional on-line tessellation automaton. This restricted two-dimensional cellular automaton is able to simulate the Baker-Bird algorithm, which was proposed as the first algorithm for the two-dimensional pattern matching. We explore capabilities of this automaton to carry out the matching task against an arbitrary set of equal-sized patterns. To measure amount of resources needed to accomplish it, we introduce the pattern complexity of a picture language. We show that this complexity ranges from a constant to exponential one. All of these are illustrated by giving examples of two-dimensional on-line tessellation automata matching sets of patterns, describing general techniques of how to construct them and proving lower bounds on the pattern complexity of some picture languages as well as operations over them.

Název v anglickém jazyce

Complexity of Matching Sets of Two-Dimensional Patterns by Two-Dimensional On-Line Tessellation Automaton

Popis výsledku anglicky

We study the two-dimensional pattern matching implemented using the deterministic two-dimensional on-line tessellation automaton. This restricted two-dimensional cellular automaton is able to simulate the Baker-Bird algorithm, which was proposed as the first algorithm for the two-dimensional pattern matching. We explore capabilities of this automaton to carry out the matching task against an arbitrary set of equal-sized patterns. To measure amount of resources needed to accomplish it, we introduce the pattern complexity of a picture language. We show that this complexity ranges from a constant to exponential one. All of these are illustrated by giving examples of two-dimensional on-line tessellation automata matching sets of patterns, describing general techniques of how to construct them and proving lower bounds on the pattern complexity of some picture languages as well as operations over them.

Druh

J_imp - Článek v periodiku v databázi Web of Science

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 periodika

International Journal of Foundations of Computer Science

ISSN

0129-0541

e-ISSN

1793-6373

Svazek periodika

28

Číslo periodika v rámci svazku

5

Stát vydavatele periodika

SG - Singapurská republika

Počet stran výsledku

18

Strana od-do

623-640

Kód UT WoS článku

000418091500012

EID výsledku v databázi Scopus

2-s2.0-85038572387