Abstract
Pure two-dimensional context-free grammar (P2DCFG) is a simple but effective non-isometric 2D grammar model to generate picture arrays. This 2D grammar uses only one kind of symbol as in a pure string grammar and rewrites in parallel all the symbols in a column or row by a set of context-free type rules. P2DCFG and a variant called (l / u)P2DCFG, which was recently introduced motivated by the “leftmost” rewriting mode in string context-free grammars, have been investigated for different properties. In this paper we introduce another variant of P2DCFG that corresponds to “rightmost” rewriting in string context-free grammars. The resulting grammar is called (r / d)P2DCFG and rewrites in parallel all the symbols only in the rightmost column or the lowermost row of a picture array by a set of context-free type rules. Unlike the case of string context-free grammars, the picture language families of P2DCFG and the two variants (l / u)P2DCFG and (r / d)P2DCFG are mutually incomparable, although they are not disjoint. We also examine the effect of regulating the rewriting in a (r / d)P2DCFG by suitably adapting two well-known control mechanisms in string grammars, namely, control words and matrix control.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bersani, M.M., Frigeri, A., Cherubini, A.: On some classes of 2D languages and their relations. In: Aggarwal, J.K., Barneva, R.P., Brimkov, V.E., Koroutchev, K.N., Korutcheva, E.R. (eds.) IWCIA 2011. LNCS, vol. 6636, pp. 222–234. Springer, Heidelberg (2011)
Bersani, M.M., Frigeri, A., Cherubini, A.: Expressiveness and complexity of regular pure two-dimensional context-free languages. Int. J. Comput. Math. 90, 1708–1733 (2013)
Dassow, J., Păun, G.: Regulated Rewriting in Formal Language Theory. Springer, Heidelberg (1989)
Freund, R.: Control mechanisms on #-context-free array grammars. In: Păun, Gh. (ed.) Mathematical Aspects of Natural and Formal Languages, pp. 97–137. World Scientific Publishing, Singapore (1994)
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)
Křivka, Z., Martín-Vide, C., Meduna, A., Subramanian, K.G.: A variant of pure two-dimensional context-free grammars generating picture languages. In: Barneva, R.P., Brimkov, V.E., Šlapal, J. (eds.) IWCIA 2014. LNCS, vol. 8466, pp. 123–133. Springer, Heidelberg (2014)
Maurer, H.A., Salomaa, A., Wood, D.: Pure grammars. Inform. Control 44, 47–72 (1980)
Mishra, J.: Classification of linear fractals through L-system. In: Proceedings of the International Conferences Emerging Trends in Engineering and Technology, pp. 1–5 (2008)
Nakamura, A.: Picture languages. In: Davis, L.S. (ed.) Foundations of Image Understanding. International Series in Engineering and Computer Science, pp. 127–155. Kluwer Academic Publishers, Norwell (2001)
Rosenfeld, A.: Picture Languages. Academic Press, Reading (1979)
Rosenfeld, A., Siromoney, R.: Picture languages - a survey. Lang. Des. 1, 229–245 (1993)
Rozenberg, G., Salomaa, A.: The Mathematical Theory of L-Systems. Academic Press, New York (1980)
Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages (3 Volumes). Springer, Berlin (1997)
Salomaa, A.: Formal Languages. Academic Press, Reading (1973)
Siromoney, R., Subramanian, K.G., Rangarajan, K.: Control on kolam arrays. Inform. Control 32, 272–275 (1976)
Subramanian, K.G., Ali, R.M., Geethalakshmi, M., Nagar, A.K.: Pure 2D picture grammars and languages. Discrete Appl. Math. 157(16), 3401–3411 (2009)
Subramanian, K.G., Nagar, A.K., Geethalakshmi, M.: Pure 2D picture grammars (P2DPG) and P2DPG with regular control. In: Brimkov, V.E., Barneva, R.P., Hauptman, H.A. (eds.) IWCIA 2008. LNCS, vol. 4958, pp. 330–341. Springer, Heidelberg (2008)
Subramanian, K.G., Rangarajan, K., Mukund, M. (eds.): Formal Models, Languages and Applications. Series in Machine Perception and Artificial Intelligence, vol. 66. World Scientific, Singapore (2006)
Wang, P.S.-P. (ed.): Array Grammars, Patterns and Recognizers. Series in Computer Science, vol. 18. World Scientific, Singapore (1989)
Acknowledgements
The authors are grateful to the referees for their very useful comments which helped improve the presentation of the paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Subramanian, K.G., Geethalakshmi, M., David, N.G., Nagar, A.K. (2015). Picture Array Generation Using Pure 2D Context-Free Grammar Rules. In: Barneva, R., Bhattacharya, B., Brimkov, V. (eds) Combinatorial Image Analysis. IWCIA 2015. Lecture Notes in Computer Science(), vol 9448. Springer, Cham. https://doi.org/10.1007/978-3-319-26145-4_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-26145-4_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-26144-7
Online ISBN: 978-3-319-26145-4
eBook Packages: Computer ScienceComputer Science (R0)