Parsing of two-dimensional images represented by quadtree adjoining grammars

摘要

In this paper, we will investigate parsing algorithms for QTAGs and their extension called multifoot QTAGs (MFQTAGs). QTAG is a kind of tree adjoining grammars which generates the set of quadtrees. The complexity of our parsing algorithms are O(N2) by making use of good properties of quadtrees. In this case, the variable N is the diameter of the input image instead of the number of pixels. In other words, parsing for the languages of QTAGs has the linear time complexity.