On languages generated by isotonic array P systems with/without priority rules
Tóm tắt
Membrane computing and array grammars are two well-known areas in formal language theory. In this paper, we investigate the languages generated by the isotonic array P systems with or without priority rules. This model incorporates the properties of P systems and isotonic array grammars. Moreover, in this model, the arrays present in the membranes evolve according to the isotonic array rewriting rules. This model is capable of generating interesting pictures like hollow rectangles and crosses having four equal arms which are in general difficult to generate. In this paper, we compare the family of languages generated by the isotonic array P systems with/without priority rules with the family of languages generated by different variants of array grammars as well as P systems such as 2D Siromoney matrix grammar, local tiling languages, tiling recognizable languages, array rewriting P system and parallel array rewriting P system.
Từ khóa
Tài liệu tham khảo
Păun, G. (2000). Computing with membranes. Journal of Computer and System Sciences, 61(1), 108–143.
Păun, G. (2002). Membrane computing: An introduction. Springer.
Song, B., Li, K., Orellana-Martín, D., Pérez-Jiménez, M. J., & Pérez-Hurtado, I. (2021). A survey of nature-inspired computing: Membrane computing. ACM Computing Surveys (CSUR), 54(1), 1–31.
Zhang, G., Pérez-Jiménez, M. J., & Gheorghe, M. (2017). Real-life applications with membrane computing (Vol. 25). Springer.
Fan, S., Paul, P., Wu, T., Rong, H., & Zhang, G. (2020). On applications of spiking neural P systems. Applied Sciences, 10(20), 7011.
Rozenberg, G., & Salomaa, A. (2012). Handbook of formal languages Beyond words (Vol. 3). Springer.
Stromoney, G., Siromoney, R., & Krithivasan, K. (1972). Abstract families of matrices and picture languages. Computer Graphics and Image Processing, 1(3), 284–307.
Nivat, M., Saoudi, A., Subramanian, K., Siromoney, R., & Dare, V. R. (1991). Puzzle grammars and context-free array grammars. International Journal of Pattern Recognition and Artificial Intelligence, 5(05), 663–676.
Subramanian, K., Siromoney, R., Dare, V. R., & Saoudi, A. (1995). Basic puzzle languages. International journal of pattern recognition and artificial intelligence, 9(05), 763–775.
Subramanian, K., Siromoney, R., Dare, V. R., & Saoudi, A. (1992). Basic puzzle grammars and isosceles right triangles. International Journal of Pattern Recognition and Artificial Intelligence, 6(05), 799–816.
Cook, C. R., & Wang, P.S.-P. (1978). A Chomsky hierarchy of isotonic array grammars and languages. Computer Graphics and Image Processing, 8(1), 144–152.
Freund, R. (2000). Array grammar systems. Journal of Automata, Languages and Combinatorics, 5(1), 13–30.
Nirmal, N., & Rama, R. (1988). Picture generation and developmental matrix systems. Computer Vision, Graphics, and Image Processing, 43(1), 67–80.
Krithivasan, K., & Das, A. (1985). Terminal weighted grammars and picture description. Computer Vision, Graphics, and Image Processing, 30(1), 13–31.
Cherubini, A., Reghizzi, S. C., Pradella, M., & San Pietro, P. (2006). Picture languages: Tiling systems versus tile rewriting grammars. Theoretical Computer Science, 356(1–2), 90–103.
Cherubini, A., Crespi Reghizzi, S., & Pradella, M. (2008). Regional languages and tiling: A unifying approach to picture grammars. In: Mathematical foundations of computer science 2008: 33rd international symposium, MFCS 2008, Toru’ N, Poland, August 25–29, 2008. Proceedings 33 (pp. 253–264). Springer.
Subramanian, K., Revathi, L., & Siromoney, R. (1989). Siromoney array grammars and applications. International Journal of Pattern Recognition and Artificial Intelligence, 3(03n04), 333–351.
Siromoney, G., Siromoney, R., & Krithivasan, K. (1974). Array grammars and kolam. Computer Graphics and Image Processing, 3(1), 63–82.
Govindaraj, R., & Mahendran, A. (2018). Generating various kolam patterns using new kolam picture grammar. International Journal of Internet Technology and Secured Transactions, 8(2), 209–220.
Siromoney, G., & Siromoney, R. (1986). Rosenfeld’s cycle grammars and kolam. In: International workshop on graph grammars and their application to computer science (pp. 564–579). Springer
Venkatesan, A. P., Thomas, D. G., Robinson, T., & Nagar, A. K. (2010). Trajectory array P system. In: 2010 IEEE fifth international conference on bio-inspired computing: Theories and applications (BIC-TA) (pp. 1543–1549). IEEE
Dersanambika, K., & Krithivasan, K. (2004). Contextual array P systems. International Journal of Computer Mathematics, 81(8), 955–969.
Lakshmi, M. G., Vinodhini, G. A. F., Jayasankar, S., & Thomas, D. G. (2023). Parallel contextual array insertion-deletion P systems and array rewriting P systems with pure 2D context-free rules. Journal of Membrane Computing, 5, 144–60.
Fernau, H., Freund, R., Schmid, M. L., Subramanian, K., & Wiederhold, P. (2015). Contextual array grammars and array P systems. Annals of Mathematics and Artificial Intelligence, 75, 5–26.
Sureshkumar, W., & Rama, R. (2016). Chomsky hierarchy control on isotonic array P systems. International Journal of Pattern Recognition and Artificial Intelligence, 30(02), 1650004.
Sureshkumar, W., Mahalingam, K., & Rama, R. (2017). Robot motion planning inside a grid using membrane computing. International Journal of Imaging and Robotics, 17(1), 14–26.
Ceterchi, R., Mutyam, M., Păun, G., & Subramanian, K. (2003). Array-rewriting P systems. Natural Computing, 2, 229–249.
Subramanian, K., Isawasan, P., Venkat, I., & Pan, L. (2014). Parallel array-rewriting P systems. Romanian Journal of Information Science and Technology, 17(1), 103–116.
Kirsch, R. A. (1964). Computer interpretation of English text and picture patterns. IEEE Transactions on Electronic Computers, 4, 363–376.
Yodogawa, E., & Honda, N. (1968). On two-dimensional grammars. Res. Rept. of the Institute of Electronics and Communication Engineers of Japan (IECEJ).
Rosenfeld, A. (1970). Isotonic grammars, parallel grammars, and picture grammars. University of Maryland.
Latteux, M., & Simplot, D. (1997). Recognizable picture languages and domino tiling. Theoretical Computer Science, 178(1–2), 275–283.