2006 | OriginalPaper | Chapter
On Two-Dimensional Pattern Matching by Finite Automata
Authors : Jan Žd’árek, Bořivoj Melichar
Published in: Implementation and Application of Automata
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper presents a general concept of two-dimensional pattern matching using conventional (one-dimensional) finite automata. Then two particular models and methods, implementations of the general principle, are presented. The first of these two models presents an automata based version of the Bird and Baker approach with lower space complexity than the original algorithm. The second introduces a new model for two-dimensional approximate pattern matching using the two-dimensional Hamming distance.