Two-Dimensional Pattern Matching Against Basic Picture Languages
The result's identifiers
Result code in 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>
Alternative codes found
RIV/00216208:11320/19:10408688
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Two-Dimensional Pattern Matching Against Basic Picture Languages
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA19-09967S" target="_blank" >GA19-09967S: Compositional Architectures for Pattern Recognition</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Implementation and Application of Automata
ISBN
978-3-030-23678-6
ISSN
0302-9743
e-ISSN
1611-3349
Number of pages
13
Pages from-to
209-221
Publisher name
Springer
Place of publication
Berlin, Heidelberg
Event location
Košice
Event date
Jul 22, 2019
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—