Complexity of Matching Sets of Two-Dimensional Patterns by Two-Dimensional On-Line Tessellation Automaton
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Complexity of Matching Sets of Two-Dimensional Patterns by Two-Dimensional On-Line Tessellation Automaton
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
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/GA15-04960S" target="_blank" >GA15-04960S: SeLeCt - Structures, Learning and Cognition</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2017
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
Name of the periodical
International Journal of Foundations of Computer Science
ISSN
0129-0541
e-ISSN
1793-6373
Volume of the periodical
28
Issue of the periodical within the volume
5
Country of publishing house
SG - SINGAPORE
Number of pages
18
Pages from-to
623-640
UT code for WoS article
000418091500012
EID of the result in the Scopus database
2-s2.0-85038572387