Abstract
Rewriting array P systems for generation of rectangular picture arrays have been considered with the rules in membranes and the application of the rules as in a pure 2D context-free grammar (P2DCFG) and its variants. Here, we introduce in P2DCFG, a different mode of rewriting of an array, which we call as independent mode. We then consider rewriting array P systems involving P2DCFG type of rules but with the independent mode of rewriting. We show that the array generative power is increased in the framework of P systems. This framework also allows for the treatment of the so-called “extended” array grammars.
Similar content being viewed by others
References
Bersani, M. M., Frigeri, A., & Cherubini, A. (2011). On some classes of 2D languages and their relations. In J.K. Aggarwal, et al. (Eds.) Combinatorial Image Analysis (vol. 4958, pp. 222–234). Lecture Notes on Computer Science.
Bersani, M. M., Frigeri, A., & Cherubini, A. (2013). Expressiveness and complexity of regular pure two-dimensional context-free languages. International Journal of Computer Mathematics, 90, 1708–1733.
Berstel, J., Boasson, L., & Fagnot, I. (2012). Splicing systems and the Chomsky hierarchy. Theoretical Computer Science, 436, 2–22.
Ceterchi, R., Mutyam, M., Pǎun, Gh., & Subramanian, K.G. (2003). Array—rewriting P systems. Natural Computing, 2, 229–249.
Ceterchi, R., Subramanian, K.G., & Venkat, I. P. (2015) . Systems with Parallel Rewriting for Chain Code Picture Languages. In A. Beckmann, V. Mitrana, M. Soskova (Eds.) Evolving Computability. CiE 2015. Lecture Notes in Computer Science (vol. 9136, pp. 145–155). Champaign: Springer.
Fernau, H., Freund, R., Schmid, M. L., Subramanian, K. G., & Wiederhold, P. (2015). Contextual array grammars and array P systems. Annals of Mathematics and Artificial Intelligence, 75, 5–26.
Freund, R. (1994) . Control mechanisms on #-context-free array grammars. In Gh. Pǎun (Ed.) Mathematical Aspects of Natural and Formal Languages (pp. 97–137). Singapore: World Scientific.
Freund, R. (2000). Array Grammars. Technical Rep. 15/00, Research Group on Mathematical Linguistics (p. 164), Rovira i Virgili University, Tarragona.
Freund, R., Paun, Gh., & Rozenberg, G., et al. (2007). Contextual array grammars. In K. G. Subramanian (Ed.), Formal Models (pp. 112–136). Languages and Applications: World Scientific Publishing.
Freund, R. (2020). How derivation modes and halting conditions may influence the computational power of P systems. Journal of Membrane Computing, 2, 14–25.
Fujioka, K. (2014) . A two-dimensional extension of insertion systems. A.-H. Dediu et al. (Eds.) TPNC 2014, Lecture Notes on Computer Science (vol. 8890, pp. 181–192).
Giammarresi, D., & Restivo, A. (1997) . Two-dimensional languages, In G. Rozenberg and A. Salomaa (Eds.) Handbook of Formal Languages (vol. 3, pp. 215–267). Berlin: Springer.
Head, T. (1987). Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviours. Bulletin of Mathematical Biology, 49, 735–759.
Křivka, Z., Martín-Vide, C., Meduna, A., & Subramanian, K.G. (2014). A variant of pure two-dimensional context-free grammars generating picture languages. In R.P. Barneva, V.E. Brimkov, J. Slapal (Eds.) Combinatorial Image Analysis (vol. 8466, pp. 123–133). Lecture Notes Computer Science. Heidelberg: Springer
Maurer, H. A., Salomaa, A., & Wood, D. (1980). Pure grammars. Information Control, 44, 47–72.
Pan, L., Nagar, A. K., Subramanian, K. G., & Song, B. (2016). Picture array generation using flat splicing operation. Journal of Computational and Theoretical Nanoscience, 13, 3568–3577.
Pǎun, Gh. (2000). Computing with membranes. Journal of Computer and System Sciences, 61, 108–143.
Pǎun, Gh. (2000). Membrane Computing: An Introduction. Berlin: Springer.
Pǎun, Gh., Rozenberg, G., & Salomaa, A. (2010). The Oxford Handbook of Membrane Computing. New York: Oxford University Press.
Rosenfeld, A. (1979). Picture Languages—Formal Models for Picture Recognition. New York: Academic Press.
Rosenfeld, A., & Siromoney, R. (1993). Picture languages—a survey. Languages of Design, 1, 229–245.
Rozenberg, G., Salomaa. A. (1997). (Eds.) Handbook of Formal Languages (vol. 1–3). Berlin: Springer.
Salomaa, A. (1973). Formal Languages. London: Academic Press.
Siromoney, G., Siromoney, R., & Krithivasan, K. (1974). Array grammars and kolam. Computer Graphics Image Processing., 3(1), 63–82.
Siromoney, R. (1991). Contributions of Professor Gift Siromoney in the area of pattern recognition. IETE Journal of Research, 37(5–6), 409–418.
Siromoney, G., Siromoney, R., & Krithivasan, K. (1972). Abstract families of matrices and picture languages. Computer Graphics Image Processing, 1, 234–307.
Siromoney, R., Subramanian, K. G., & Rangarajan, K. (1977). Parallel/Sequential rectangular arrays with tables. International Journal of Computer Mathematics, 6, 143–158.
Subramanian, K. G. (2007). P systems and picture languages. Lecture Notes in Computer Science, 4664, 99–109.
Subramanian, K. G., Ali, R. M., Geethalakshmi, M., & Nagar, A. K. (2009). Pure 2D picture grammars and languages. Discrete Applied Mathematics, 157(16), 3401–3411.
Subramanian, K. G., Nagar, A. K., & Geethalakshmi, M. (2008). Pure 2D picture grammars (P2DPG) and P2DPG with regular control. In Brimkov, et al. (Eds.), Combinatorial Image Analysis. Lecture Notes on Computer Science (vol. 4958, pp. 330–341).
Subramanian, K. G., Geethalakshmi, M., David, N. G., & Nagar, A. K. (2015). Picture array generation using pure 2D context-free grammar rules. Lecture Notes on Computer Science, 9448, 187–201.
Subramanian, K. G., Pan, L., Lee, S. K., & Nagar, A. K. (2010). A P system model with pure context-free rules for picture array generation. Mathematical and Computer Modelling, 52, 1901–1909.
Wang, P. S. P. (1989). Array Grammars, Patterns and Recognizers. Singapore: World Scientific.
Zhang, G., Pérez-Jiménez, M.J., & Păun, Gh. (2017). Real-life Applications with Membrane Computing. In Emergence, Complexity and Computation Series
Acknowledgements
An earlier version of this paper was presented in the International conference on Membrane Computing (ICMC 2021). The comments of the reviewers on the conference version and the journal version were very helpful in preparing this improved revised version.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Funding
No funding was received for conducting this study.
Conflict of interest
The authors declare no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Bera, S., Ceterchi, R., Sriram, S. et al. Array P systems and pure 2D context-free grammars with independent mode of rewriting. J Membr Comput 4, 11–20 (2022). https://doi.org/10.1007/s41965-021-00090-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s41965-021-00090-2