Mosaic grammars. (English) Zbl 0318.68058

Summary: This paper describes some results obtained from investigating a class of two-dimensional grammars, called mosaic grammars. The concepts of “pattern” and “mosaic” are introduced, and these structures are then used for defining various classes of “mosaic grammars”. Both sequential and parallel mosaic grammars are considered. Some of the demonstrated relationships among classes of mosaic grammars are indicated.


68T10 Pattern recognition, speech recognition
68N01 General topics in the theory of software
68Q45 Formal languages and automata
Full Text: DOI


[1] Banerji, R. B., A language for pattern recognition, Pattern Recognition, 1, 63 (1968)
[2] Breeding, K. J., Grammar for a picture description language, (Report No. 177 (May 1965), University of Illinois)
[3] Buneman, O. P., A grammar for the topological analysis of plane figures, Pattern Recognition, 1, 383 (1968) · Zbl 0219.68055
[4] Chang, Shi-kuo, Analysis and synthesis of two-dimensional patterns using picture-processing grammars, Doctoral Dissertation (1969), Berkeley, Calif.
[5] Chang, Shi-kuo, A method for the structural analysis of two-dimensional mathematical expressions, IBM Research, RC 2655 (1969)
[6] Chang, Shi-kuo, Picture processing grammar and its applications, (Symp. Theory Computing (1970)) · Zbl 0217.22802
[7] Clowes, M. B., A generative picture grammar, (Seminar Paper No. 6 (1967), Computing Research Section, Commonwealth Scientific and Industrial Research Organization: Computing Research Section, Commonwealth Scientific and Industrial Research Organization Australia)
[8] Dacey, M. F., The syntax of a triangle and some other figures, Pattern Recognition, 2, 11 (1970)
[9] Dacey, M. F., A picture language for periodic strip patterns, Geographical Anal., 3 (1971)
[10] Evans, T. G., A grammar-controlled pattern analyzer, (Proc. IFIP Congress (1968)) · Zbl 0191.17703
[11] Feder, J., The linguistic approach to pattern analysis: a literature survey, (Tech. Report 400-133 (1966), New York University)
[12] Feder, J., Languages, automata and classes of chain-encoded patterns, (Tech. Report 400-165 (1967), New York University) · Zbl 0175.27804
[13] Feder, J., Languages of encoded line patterns, Inf. Control, 13, 230 (1968) · Zbl 0175.27804
[14] Feder, J., Linguistic specification and analysis of classes of line patterns, (Tech. Report 403-2 (1969), New York University)
[15] Feder, J., Plex languages, Inf. Sci., 3, 225 (1971) · Zbl 0222.68029
[16] Freeman, H., On the encoding of arbitrary geometric configurations, IRE Trans. Electron. Comp., EC-10, 260 (1961)
[17] Grenander, U., Linguistic tendencies in pattern analysis (April 1968), Div. of Applied Math., Brown University
[18] Grenander, U., Foundations of pattern analysis, Q. Appl. Math., 27, 1 (1969) · Zbl 0187.17102
[19] Grenander, U., A unified approach to pattern analysis, (Advances in Computers, Vol. 10 (1970), Academic Press: Academic Press New York), 175-216
[20] Kirsch, R. A., Computer interpretation of English text and picture patterns, IEEE Trans. Comp., 363-376 (1964)
[21] Kulick, J., A generative grammar for pictures of chemical graphs, (Master’s Thesis (1970), University of Pennsylvania)
[22] Miller, W. F.; Shaw, A. C., A picture calculus, (SLAC-Pub-358 (Oct. 1967), Stanford University)
[23] Miller, W. F.; Shaw, A. C., Search procedures in the picture calculus, (GSG No. 51 (Oct. 1967), Stanford University)
[24] Miller, W. F.; Shaw, A. C., Linguistic methods in picture processing—a survey, (Proc. AFIPS FJCC (1968)), 279-290
[25] Narasimhan, R., A linguistic approach to pattern recognition, (Report No. 121 (July 1962), University of Illinois)
[26] Narasimhan, R., Labeling schemata and syntactic descriptions of pictures, Inf. Control, 7, 151 (1964)
[27] Narasimhan, R., Syntax-directed interpretation of classes of pictures, CACM, 9, 3, 166 (1966)
[28] Ota, P. A., Mosaic Grammars, (Moore School Report No. 73-10 (May 1973), University of Pennsylvania) · Zbl 0318.68058
[29] Pavlidis, T., Analysis of set patterns, Pattern Recognition, 1, 164 (1968)
[30] Pavlidis, T., Structural pattern recognition: primitives and juxaposition relations, (Tech. Report No. 89 (1971), Computer Science Lab., Princeton University) · Zbl 0258.68050
[31] Pavlidis, T., Linear and context-free graph grammars, JACM, 19, 11 (1972) · Zbl 0229.68027
[32] Pavlidis, T., Representation of figures by labelled graphs, Pattern Recognition, 4, 5 (1972)
[33] Pfaltz, J.; Rosenfeld, A., Web grammars, (Tech. Report 69-84 (1969), University of Maryland)
[34] Pfaltz, J., Web grammars and picture description, (Tech. Report 70-138 (1970), University of Maryland)
[35] Rosenfeld, A., Isotonic grammars, parallel grammars and picture grammars, (Machine Intelligence, Vol. 6 (1971), Edinburgh Univ. Press), 281-294 · Zbl 0261.68035
[36] Shaw, A. C., Pattern recognition bibliography, (GSG Memo No. 4 (1966), Stanford University)
[37] Shaw, A. C., On the interactive generation and interpretation of artificial pictures, (SLAC-PUB-664 (1969), Cornell University)
[38] Shaw, A. C., Parsing of graph-representable pictures, JACM, 17, 453 (1970) · Zbl 0215.56403
[39] Shaw, A. C., Picture graphs, grammars and parsing, (Tech. Report No. 71-89 (1971), Cornell University) · Zbl 0257.68101
[40] Zahn, C. T., A formal description for two-dimensional patterns, (SLAC-Pub-538 (1969), Stanford University)
[41] Knowlton, K., A computer technique for producing animated movies, (Proc. AFIPS SJCC, 25 (1964)), 67
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.