|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc030104,
author = {Viswanathan Radhakrishnan and Venkatesan T and Chakaravarthy
and Kamala Krithivasan},
title = {Pattern Matching in Matrix Grammars},
journal = jalc,
year = 1998,
volume = 3,
number = 1,
pages = {59--72},
keywords = {formal languages, pattern matching, matrix grammars,
CYK algorithm},
abstract = {In this paper, we present algorithms for four problems on
matrix grammars, in the sense of Siromoney, Siromoney and
Krithivasan. The problems are membership testing, vertical
strip testing, horizontal strip testing and subimage
testing. Inputs to all the four algorithms are a matrix
grammar $M$ and a matrix $I$. The membership testing
involves finding whether $I$ is generated by $M$ or not.
The vertical strip testing is to test whether $I$ is a
vertical strip of some matrix generated by $M$. Similarly,
horizontal strip testing is to find whether $I$ is a
horizontal strip of some matrix generated by $M$. Finally,
subimage testing algorithm outputs whether $I$ is a subimage
of some image generated by $M$ or not. The first two
algorithms are based on an algorithm by Cocke, Younger and
Kasami (CYK algorithm). The last two make use of the so
called super equivalent classes. These algorithms may find
applications in pattern matching.}
}