Complexity of sets of two-dimensional patterns
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F16%3A00301936" target="_blank" >RIV/68407700:21230/16:00301936 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-319-40946-7_20" target="_blank" >http://dx.doi.org/10.1007/978-3-319-40946-7_20</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-40946-7_20" target="_blank" >10.1007/978-3-319-40946-7_20</a>
Alternative languages
Result language
angličtina
Original language name
Complexity of sets of two-dimensional patterns
Original language description
We study the two-dimensional pattern matching implemented using the two-dimensional on-line tessellation automaton, which is a restricted type of the cellular automaton able to simulate the Baker-Bird algorithm, proposed as the first algorithm for the two-dimensional pattern matching. We further explore capabilities of this automaton to carry out the matching task against an arbitrary set of equally 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 spreads in a wide range. It is demonstrated by giving examples, deriving general techniques and proving some lower bounds.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
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
2016
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
CIAA 2016: Proceedings of the 21st International Conference on Implementation and Application of Automata
ISBN
978-3-319-40945-0
ISSN
0302-9743
e-ISSN
—
Number of pages
12
Pages from-to
236-247
Publisher name
Springer-Verlag, GmbH
Place of publication
Heidelberg
Event location
Seoul
Event date
Jul 19, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000389401500020