Finite Automata and Two-dimensional Pattern Matching

Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Finite Automata and Two-dimensional Pattern Matching
Original language description
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.
Czech name
Není k dispozici
Czech description
Není k dispozici

Publication year
2004
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of the 7th International Multiconference Information Society IS'2004
ISBN
961-6303-65-1
ISSN
—
e-ISSN
—
Number of pages
4
Pages from-to
185-188
Publisher name
Institut Jozef Stefan
Place of publication
Ljubljana
Event location
Ljubljana
Event date
Oct 9, 2004
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)