We present four algorithms to perform template matching of an N×N image with an M×M template. The first algorithm is sequential, and the others are based on a SIMD mesh connected computer with N×N processors. In the first three algorithms, both the image and the template are represented by quadtrees, whereas in the last one, the template is represented by a quadtree, and the image is represented by a matrix. The time complexities of the four algorithms are respectively upper-bounded by α1N2M2, α2N+β2M2, α3N+β3M2, and β4M2, where α1, α2, β2, α3, β3, and β4 are constants.

We study some properties of array grammars, called puzzle grammars, introduced in Ref. 7. We give a new method, using puzzle grammar, for generating the set of rectangles. We prove that the emptiness problem for puzzle grammar is undecidable. We show that the non-overlapping problem for puzzle grammar is decidable.

Studies the parallel recognition of 2D-images generated by parallel context-free image grammars. The authors show that the recognition of an n*n image can be done in O(log/sup 2/(n)) time with n/sup 6/ processors. For unambiguous context-free and linear image grammars, they prove that only O(n/sup 3/) is needed. For deterministic parallel image grammars, the recognition can be done in O(log/sup 2/(n)) time by using n/sup 2/ processors.>

We investigate the complexity of the recognition of images generated by a class of context-free image grammars. We show that the sequential time complexity of the recognition of an n × n image as generated by a context-free grammar is O(nM(n)), where M(n) is the time to multiply two boolean n × n matrices. The space complexity of this recognition is O(n3). Using a parallel random access machine (i.e. PRAM), the recognition can be done in O( log 2(n)) time with n7 processors or in O(n log 2(n)) time with n6 processors. We also introduce high dimensional context-free grammars and prove that their recognition problem is polylogarithmic.

We investigate the parallel complexity of recognition problems for context-free and regular array (image) sets. We show that the sequential time complexity of the recognition of an n × n image is O(n5). The space required for these recognition problems is O(n5). We prove that there are log 2n time parallel algorithms with BM (n4) and n2 BM (n) processors for the recognition of context-free and regular array sets, respectively, where BM (n) is the number of processors sufficient to multiply two boolean n × n matrices in logarithmic time. We develop also a methodology for processing images using composition systems.

Two methods of generating isosceles right triangles by basic puzzle grammars are presented. The methods use two different sets of tiles to tile the triangular region. This is of interest in view of the fact that the set of isosceles right triangles is a nontrivial example of a two-dimensional language which cannot be generated by any regular array grammar.

We introduce a new model for generating finite, digitized, connected pictures called puzzle grammars and study its generative power by comparison with array grammars. We note how this model generalizes the classical Chomskian grammars and study the effect of direction-independent rewriting rules. We prove that regular control does not increase the power of basic puzzle grammars. We show that for basic and context-free puzzle grammars, the membership problem is NP-complete and the emptiness problem is undecidable.

We define a syntactic model for generating sets of images, where an image can be viewed as an array over finite alphabet. This model is called image grammar. Image grammar can be considered as a generalization of classical Chomsky grammar. Then we study some combinatorial and language theoretical properties such as reduction, pumping lemmas, complexity measure, we give a strict infinite hierarchy. We also characterize these families in terms of deterministic substitutions and Chomsky languages.

In this paper, we introduce a new device called GL-systems (i.e. Grammar-Lindenmayer systems) for generating finite images. GL-systems are sequential/parallel systems in which the horizontal rules form a Chomskian grammar and the vertical rules form a DTOL system. We obtain hierarchical results of various types of GL-systems. We study some properties like, closure properties, combinatorial results, pumping lemma and decidability results. An algebraic characterization for GL-systems (with variation) is presented.

The authors give a very simple uniform explanation of the persistence of exponential decidability. They follow M. Vardi and P. Wolper's theory (1986) that given a formula gamma of a temporal or dynamic logic, it is important to construct an equivalent automation M/sub gamma /. They characterize the weak monadic theory of the tree; it turns out that weak alternating automata greatly simplify design procedures.>