Exact and approximate matching of matrix languages

In this paper we consider the problem of exact and approximate matching of matrix languages. In the exact image testing problem, we have given polynomial time algorithms for the membership problem for matrix grammars. We then consider the problem of approximately matching matrix languages. Given a matrix grammar M, a cost function and an input image I, we give algorithms to approximately match the input image with images generated by the grammar. The algorithms return the cost of matching the input image with an image generated by the matrix grammar. These approximation schemes can be used for pattern recognition. © 2000 Taylor & Francis Group, LLC.