Two-Dimensional Pattern Matching Against Basic Picture Languages

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F19%3A00335625" target="_blank" >RIV/68407700:21230/19:00335625 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/19:10408688

Výsledek na webu

<a href="https://link.springer.com/chapter/10.1007/978-3-030-23679-3_17" target="_blank" >https://link.springer.com/chapter/10.1007/978-3-030-23679-3_17</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-23679-3_17" target="_blank" >10.1007/978-3-030-23679-3_17</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Two-Dimensional Pattern Matching Against Basic Picture Languages

Popis výsledku v původním jazyce

Given a two-dimensional array of symbols and a picture language over a finite alphabet, we study the problem of finding rectangular subarrays of the array that belong to the picture language. We formulate four particular problems – finding maximum, minimum, any or all match(es) – and describe algorithms solving them for basic classes of picture languages, including local picture languages and picture languages accepted by deterministic on-line tessellation automata or deterministic four-way finite automata. We also prove that the matching problems cannot be solved for the class of local picture languages in linear time unless the problem of triangle finding is solvable in quadratic time. This shows there is a fundamental difference in the pattern matching complexity regarding the one-dimensional and two-dimensional setting.

Název v anglickém jazyce

Two-Dimensional Pattern Matching Against Basic Picture Languages

Popis výsledku anglicky

Given a two-dimensional array of symbols and a picture language over a finite alphabet, we study the problem of finding rectangular subarrays of the array that belong to the picture language. We formulate four particular problems – finding maximum, minimum, any or all match(es) – and describe algorithms solving them for basic classes of picture languages, including local picture languages and picture languages accepted by deterministic on-line tessellation automata or deterministic four-way finite automata. We also prove that the matching problems cannot be solved for the class of local picture languages in linear time unless the problem of triangle finding is solvable in quadratic time. This shows there is a fundamental difference in the pattern matching complexity regarding the one-dimensional and two-dimensional setting.

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/GA19-09967S" target="_blank" >GA19-09967S: Hierarchické architektury pro rozpoznávání</a><br>

Návaznosti

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

Rok uplatnění

2019

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

Implementation and Application of Automata

ISBN

978-3-030-23678-6

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

13

Strana od-do

209-221

Název nakladatele

Springer

Místo vydání

Berlin, Heidelberg

Místo konání akce

Košice

Datum konání akce

22. 7. 2019

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

WRD - Celosvětová akce

Kód UT WoS článku

—