Pattern Matching in Matrix Grammars
Radhakrishnan, Viswanathan, Venkatesan T. Chakaravarthy, Kamala Krithivasan · Journal of automata, languages and combinatorics · 1998
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
Journal of automata, languages and combinatorics · University of Giessen · article · 1998
Abstract
In this paper, we present algorithms for four problems on matrix grammars, in the sense of Siromoney, Siromoney and Krithivasan [6]. 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.
Open the resolved locator · 10.25596/jalc-1998-059
Metadata licence: OpenAlex metadata (CC0)