Abstract
In this note a new model of grammatical picture generation is introduced. The model is based on the notion of pure context-free grammars of formal string language theory. The resulting model, called Pure 2D context-free grammar (CFG), generates rectangular picture arrays of symbols. The generative power of this model in comparison to certain other related models is examined. Also we associate a regular control language with a Pure 2D CFG and notice that the generative power increases. Certain closure properties are obtained.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 3, pp. 215–267. Springer, Heidelberg (1997)
Giammarresi, D., Restivo, A.: Recognizable Picture Languages. International Journal of Pattern Recognition and artificial Intelligence (Special issue on Parallel Image Processing), Nivat, M., Saoudi, A., Wang, P.S.P. (eds.), 31–46 (1992)
Maurer, H.A., Rozenberg, G., Welzl, E.: Chain-code picture languages. Lecture notes in Computer science, vol. 153, pp. 232–244. Springer, Heidelberg (1983)
Maurer, H.A., Salomaa, A., Wood, D.: Pure Grammars. Information and Control 44, 47–72 (1980)
Rosenfeld, A.: Picture Languages - Formal Models for Picture Recognition. Academic Press, New York (1979)
Rosenfeld, A., Siromoney, R.: Picture languages - a survey. Languages of design 1, 229–245 (1993)
Rozenberg, G., Salomaa, A.: The Mathematical Theory of L systems. Academic Press, New York (1980)
Salomaa, A.: Formal languages. Academic Press, London (1973)
Siromoney, G., Siromoney, R., Krithivasan, K.: Abstract families of matrices and picture languages. Computer Graphics and Image Processing 1, 234–307 (1972)
Siromoney, R., Siromoney, G.: Extended Controlled Tabled L- arrays. Information and Control 35(2), 119–138 (1977)
Siromoney, R., Subramanian, K.G., Rangarajan, K.: Parallel/Sequential rectangular arrays with tables. International Journal of Computer Mathematics, 143–158 (1977)
Stiebe, R.: Picture generation using matrix systems. Journal of Information Processing and Cybernetics 28, 311–327 (1992)
Stiebe, R.: Slender Siromoney Matrix Languages. In: Proceedings of the 1st International Conference on Language and Automata: Theory and Applications, Tarragona, Spain (2007)
Wang, P.S.P.: Array grammars, Patterns and recognizers. World Scientific, Singapore (1989)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Subramanian, K.G., Nagar, A.K., Geethalakshmi, M. (2008). Pure 2D Picture Grammars (P2DPG) and P2DPG with Regular Control. In: Brimkov, V.E., Barneva, R.P., Hauptman, H.A. (eds) Combinatorial Image Analysis. IWCIA 2008. Lecture Notes in Computer Science, vol 4958. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78275-9_29
Download citation
DOI: https://doi.org/10.1007/978-3-540-78275-9_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78274-2
Online ISBN: 978-3-540-78275-9
eBook Packages: Computer ScienceComputer Science (R0)