Complexity of sets of two-dimensional patterns
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Complexity of sets of two-dimensional patterns
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Complexity of sets of two-dimensional patterns
Popis výsledku anglicky
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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GA15-04960S" target="_blank" >GA15-04960S: SeLeCt - struktury, učení a kognice</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2016
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
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
—
Počet stran výsledku
12
Strana od-do
236-247
Název nakladatele
Springer-Verlag, GmbH
Místo vydání
Heidelberg
Místo konání akce
Seoul
Datum konání akce
19. 7. 2016
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
000389401500020