go-v.orgdoi

Pattern Matching in Matrix Grammars

Radhakrishnan, Viswanathan, Venkatesan T. Chakaravarthy, Kamala Krithivasan · Journal of automata, languages and combinatorics · 1998

  • DOI 10.25596/jalc-1998-059
  • Publisher University of Giessen
  • Type article
  • Issued 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)