Two-dimensional pattern matching against local and regular-like picture languages

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F21%3A00354392" target="_blank" >RIV/68407700:21230/21:00354392 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216208:11320/21:10440772

Výsledek na webu

<a href="https://doi.org/10.1016/j.tcs.2020.12.026" target="_blank" >https://doi.org/10.1016/j.tcs.2020.12.026</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2020.12.026" target="_blank" >10.1016/j.tcs.2020.12.026</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Two-dimensional pattern matching against local and regular-like 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 investigate how to find rectangular subarrays that belong to the picture language. Two-dimensional pattern matching problems can be formulated by interpreting subarrays as matches and picture languages as patterns. We formulate four particular problems – finding maximum, minimum, any or all match(es) – and describe algorithms solving the problems for basic classes of picture languages, which include local picture languages and picture languages accepted by various types of deterministic two-dimensional finite automata such as four-way, three-way and two-way automata, on-line tessellation automata, and returning finite automata. We also prove that the pattern matching problems cannot be solved for the class of local picture languages in time linear in the input area unless the well known problem of triangle finding in a graph is solvable in quadratic time. This shows a fundamental difference between the complexity of one-dimensional and two-dimensional pattern matching.

Název v anglickém jazyce

Two-dimensional pattern matching against local and regular-like picture languages

Popis výsledku anglicky

Given a two-dimensional array of symbols and a picture language over a finite alphabet, we investigate how to find rectangular subarrays that belong to the picture language. Two-dimensional pattern matching problems can be formulated by interpreting subarrays as matches and picture languages as patterns. We formulate four particular problems – finding maximum, minimum, any or all match(es) – and describe algorithms solving the problems for basic classes of picture languages, which include local picture languages and picture languages accepted by various types of deterministic two-dimensional finite automata such as four-way, three-way and two-way automata, on-line tessellation automata, and returning finite automata. We also prove that the pattern matching problems cannot be solved for the class of local picture languages in time linear in the input area unless the well known problem of triangle finding in a graph is solvable in quadratic time. This shows a fundamental difference between the complexity of one-dimensional and two-dimensional pattern matching.

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/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í

2021

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

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

1879-2294

Svazek periodika

870

Číslo periodika v rámci svazku

May

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

16

Strana od-do

137-152

Kód UT WoS článku

000649704000008

EID výsledku v databázi Scopus

2-s2.0-85098153050