Není k dispozici

Kód výsledku v IS VaVaI

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

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Finite Automata and Two-dimensional Pattern Matching

Popis výsledku v původním jazyce

This paper presents a general concept of 2D pattern matching using conventional finite automata. Then two concrete models and methods, implementations of the general principle, are presented. First of these two models presents automata based version of well known Bird and Baker approach to the exact 2D pattern matching. Its implementation works in optimal (linear) time. The second one introduces a new model for the 2D approximate pattern matching with mismatches (we call it also matching using the 2D Hamming distance, to keep an analogy with the area of 1D pattern matching). Its implementation works independently on the number of errors in $mathcal{O}(m lceilfrac{m}{w}rceil n^2)$ time. Presented algorithms use the idea of linearisation and thus canbe easily extended to solve pattern matching problems of more than two dimensions.

Název v anglickém jazyce

Finite Automata and Two-dimensional Pattern Matching

Popis výsledku anglicky

This paper presents a general concept of 2D pattern matching using conventional finite automata. Then two concrete models and methods, implementations of the general principle, are presented. First of these two models presents automata based version of well known Bird and Baker approach to the exact 2D pattern matching. Its implementation works in optimal (linear) time. The second one introduces a new model for the 2D approximate pattern matching with mismatches (we call it also matching using the 2D Hamming distance, to keep an analogy with the area of 1D pattern matching). Its implementation works independently on the number of errors in $mathcal{O}(m lceilfrac{m}{w}rceil n^2)$ time. Presented algorithms use the idea of linearisation and thus canbe easily extended to solve pattern matching problems of more than two dimensions.

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 7th International Multiconference Information Society IS'2004

ISBN

961-6303-65-1

ISSN

—

e-ISSN

—

Počet stran výsledku

4

Strana od-do

185-188

Název nakladatele

Institut Jozef Stefan

Místo vydání

Ljubljana

Místo konání akce

Ljubljana

Datum konání akce

9. 10. 2004

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

WRD - Celosvětová akce

Kód UT WoS článku

—