Použití dvojrozměrných nastavovacích automatů pro vyhledávání v dvojrozměrném textu

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F04%3A03106850" target="_blank" >RIV/68407700:21230/04:03106850 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

A Two-dimensional Online Tessellation Automata Approach to Two-dimensional Pattern Matching

Popis výsledku v původním jazyce

A new general approach to exact and approximate twodimesional pattern matching is presented. This method, based on two-dimensional online tessellation automata, is a generalization of a well known one-dimensional pattern matching approach based on finiteautomata. It creates a nondeterministic two-dimensional online tessellation automaton and transforms it, by newly presented method, to a deterministic one. Then this automaton processes the input two-dimensional text and whenever it reaches a final state it reports an occurrence of the pattern. Since the text processing depends only on the size of the text, the searching phase of presented algorithms requires only UB(n2) time for the text of size (n,n). The only disadvantage of this method is the possibility of the exponential (in the size of the pattern) time of the preprocessing phase.

Název v anglickém jazyce

A Two-dimensional Online Tessellation Automata Approach to Two-dimensional Pattern Matching

Popis výsledku anglicky

A new general approach to exact and approximate twodimesional pattern matching is presented. This method, based on two-dimensional online tessellation automata, is a generalization of a well known one-dimensional pattern matching approach based on finiteautomata. It creates a nondeterministic two-dimensional online tessellation automaton and transforms it, by newly presented method, to a deterministic one. Then this automaton processes the input two-dimensional text and whenever it reaches a final state it reports an occurrence of the pattern. Since the text processing depends only on the size of the text, the searching phase of presented algorithms requires only UB(n2) time for the text of size (n,n). The only disadvantage of this method is the possibility of the exponential (in the size of the pattern) time of the preprocessing phase.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2004

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 statě ve sborníku

Proceedings of the Eindhoven FASTAR Days 2004

ISBN

0926-4515

ISSN

—

e-ISSN

—

Počet stran výsledku

15

Strana od-do

1-15

Název nakladatele

TU Eindhoven

Místo vydání

Eindhoven

Místo konání akce

Eindhoven

Datum konání akce

3. 9. 2004

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—