Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On homomorphic images of the Szilard languages of matrix insertion–deletion systems with matrices of size 2

  • Regular Paper
  • Published:
Journal of Membrane Computing Aims and scope Submit manuscript

Abstract

A Szilard language is a well-known tool in formal language theory to express the derivation process in a grammar system or grammar. Matrix InsDel (insertion–deletion) system is a well-known variant of InsDel system, where the idea of matrix control is combined with InsDel systems. The size of a matrix InsDel system is represented by a septuple of integers \((k; p, m, m^{'};\) \(q, n, n^{'})\), where k represents maximum number of rules in a matrix, i.e., size of a matrix. The parameters p, m and \(m^{'}\) represent the maximal length of the strings inserted, the maximal length of the left context and the maximal length of the right context of the insertion rules, respectively. The parameters \(q, n, n^{'}\) represent the same for deletion rules. In this paper, we investigate the Szilard languages of matrix InsDel systems with matrices of size 2. We give examples of regular, context-free and context-sensitive languages which cannot be the Szilard language of any matrix InsDel system. We show that any regular language can be represented as a homomorphic image of Szilard language of matrix InsDel system of size (2; 2, 0, 0; 1, 0, 0). Any linear language, meta-linear language and rational (or regular) closure of linear language can be obtained as the homomorphic image of Szilard language of matrix InsDel systems of size (2; 1, 1, 0; 1, 1, 0), and (2; 1, 0, 1; 1, 0, 1). Moreover, any recursively enumerable language can be obtained as the homomorphic image of the Szilard language of matrix InsDel systems of size (2; 1, 1, 0; 1, 1, 1), (2; 1, 0, 1; 1, 1, 1), (2; 1, 1, 1; 1, 1, 0), (2; 1, 1, 1; 1, 0, 1), (2; 1, 1, 0; 2, 0, 0), (2; 1, 0, 1; 2, 0, 0), (2; 2, 0, 0; 1, 1, 0),  and (2; 2, 0, 0; 1, 0, 1).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Adorna, H. N. (2020). Computing with SN P systems with i/o mode. Journal of Membrane Computing, 2(4), 230–245.

    MathSciNet  MATH  Google Scholar 

  2. Alhazov, A., Krassovitskiy, A., Rogozhin, Y., & Verlan, S. (2011). P systems with minimal insertion and deletion. Theoretical Computer Science, 412(1–2), 136–144.

    MathSciNet  MATH  Google Scholar 

  3. Benne, R. (Ed.). (1993). RNA editing: the alteration of protein coding sequences of RNA. Ellis Horwood (Molecular Biology).

    Google Scholar 

  4. Biegler, F., Burrell, M. J., & Daley, M. (2007). Regulated RNA rewriting: Modelling RNA editing with guided insertion. Theoretical Computer Science, 387(2), 103–112.

    MathSciNet  MATH  Google Scholar 

  5. Buiu, C., & Florea, A. G. (2019). Membrane computing models and robot controller design, current results and challenges. Journal of Membrane Computing, 1(4), 262–269. https://doi.org/10.1007/s41965-019-00029-8.

    Article  MathSciNet  MATH  Google Scholar 

  6. Cojocaru, L., & Mäkinen, E. (2014). On some derivation mechanisms and the complexity of their Szilard languages. Theoretical Computer Science, 537, 87–96.

    MathSciNet  MATH  Google Scholar 

  7. Dassow, J., Mitrana, V., & Păun, G. (1993). Szilard languages associated to cooperating distributed grammar systems. Stud. Cercet. Mat., 45, 403–413.

    MathSciNet  MATH  Google Scholar 

  8. Dassow, J., & Păun, Gh. (1989). Regulated rewriting in formal language theory. Springer-Verlag.

    MATH  Google Scholar 

  9. de la Cruz, R. T. A., Cabarle, F. G. C., & Adorna, H. N. (2019). Generating context-free languages using spiking neural P systems with structural plasticity. Journal of Membrane Computing, 1(3), 161–177.

    MathSciNet  MATH  Google Scholar 

  10. de la Cruz, R. T. A., Cabarle, F. G. C., Macababayao, I. C. H., Adorna, H. N., & Zeng, X. (2021). Homogeneous spiking neural P systems with structural plasticity. Journal of Membrane Computing, 3, 10–21. https://doi.org/10.1007/s41965-020-00067-7.

    Article  MathSciNet  MATH  Google Scholar 

  11. Duske, J., Parchmann, R., & Specht, J. (1979). Szilard languages of IO-grammars. Information and Control, 40(3), 319–331.

    MathSciNet  MATH  Google Scholar 

  12. Fernau, H., Kuppusamy, L., Verlan, S. (2017). Universal matrix insertion grammars with small size. In: M. Patitz, M. Stannett (Eds.), UCNC 2017, Unconventional Computation and Natural Computation. LNCS (vol 10240, pp. 182–193).

  13. Fernau, H., Kuppusamy, L., & Raman, I. (2016). Generative power of matrix insertion-deletion systems with context-free insertion or deletion. In M. Amos & A. Condon (Eds.), Unconventional computation and natural computation conference, UCNC (LNCS) (Vol. 9726, pp. 35–48). Springer.

    Google Scholar 

  14. Fernau, H., Kuppusamy, L., & Raman, I. (2017). Graph-controlled insertion-deletion systems generating language classes beyond linearity. In G. Pighizzini & C. Caḿpeanu (Eds.), Descriptional complexity of formal systems: 19th IFIP WG 1.02 international conference, DCFS (LNCS) (Vol. 10316, pp. 128–139). Springer.

    Google Scholar 

  15. Fernau, H., Kuppusamy, L., & Raman, I. (2017). On the generative power of graph-controlled insertion-deletion systems with small sizes. Journal of Automata, Languages and Combinatorics, 22, 61–92.

    MathSciNet  MATH  Google Scholar 

  16. Fernau, H., Kuppusamy, L., & Raman, I. (2018). Investigations on the power of matrix insertion-deletion systems with small sizes. Natural Computing, 17, 249–269.

    MathSciNet  Google Scholar 

  17. Fernau, H., Kuppusamy, L., & Raman, I. (2018). Properties of Language Classes Between Linear and Context-free. Journal of Automata, Languages and Combinatorics, 23(4), 329–360.

    MathSciNet  MATH  Google Scholar 

  18. Fernau, H., Kuppusamy, L., & Raman, I. (2018). On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems. RAIRO-Theoretical Informatics and Applications, 52, 1–21.

    MathSciNet  MATH  Google Scholar 

  19. Freund, R., Kogler, M., Rogozhin, Y., Verlan, S. (2010). Graph-controlled insertion-deletion systems. In: I. McQuillan, G. Pighizzini (Eds.), Proceedings twelfth annual workshop on descriptional complexity of formal systems, DCFS (EPTCS) (vol 31, pp. 88–98).

  20. Galiukschov, B.S. (1981). Semicontextual grammars. Mat. logica i mat. ling., Kalinin University, 38–50 (in Russian).

  21. Ganbaatar, G., Nyamdorj, D., Cichon, G., & Ishdorj, T.-O. (2021). Implementation of RSA cryptographic algorithm using SN P systems based on HP/LP neurons. Journal of Membrane Computing, 3, 22–34. https://doi.org/10.1007/s41965-021-00073-3.

    Article  MathSciNet  MATH  Google Scholar 

  22. Haussler, D. (1982). Insertion and iterated insertion as operations on formal languages. Ph.D. Thesis, Univ. of Colorado at Boulder.

  23. Igarashi, Y. (1977). The tape complexity of some classes of Szilard languages. SIAM Journal of Computing, 6(3), 460–466.

    MathSciNet  MATH  Google Scholar 

  24. Ivanov, S., & Verlan, S. (2015). Random context and semi-conditional insertion-deletion systems. Fundamenta Informatica, 138, 127–144.

    MathSciNet  MATH  Google Scholar 

  25. Ivanov, S., & Verlan, S. (2017). Universality and computational completeness of controlled leftist insertion-deletion systems. Fundamenta Informatica, 155(1–2), 163–185.

    MathSciNet  MATH  Google Scholar 

  26. Jiang, Y., Su, Y., & Luo, F. (2019). An improved universal spiking neural P system with generalized use of rules. Journal of Membrane Computing, 1(4), 270–278. https://doi.org/10.1007/s41965-019-00025-y.

    Article  MathSciNet  MATH  Google Scholar 

  27. Jimenez, Z. B., Cabarle, F. G. C., de la Cruz, R. T. A., Buno, K. C., Adorna, H. N., Hernandez, N. H. S., et al. (2019). Matrix representation and simulation algorithm of spiking neural p systems with structural plasticity. Journal of Membrane Computing, 1(3), 145–160.

    MathSciNet  MATH  Google Scholar 

  28. Kari, L. (1991). On insertion and deletion in formal languages. PhD thesis, University of Turku.

  29. Kari, L., & Thierrin, G. (1996). Contextual insertions/deletions and computability. Information and Computation, 131(1), 47–61.

    MathSciNet  MATH  Google Scholar 

  30. Krassovitskiy, A., Rogozhin, Y., & Verlan, S. (2008). Further results on insertion-deletion systems with one-sided contexts. In C. Martín-Vide, F. Otto, & H. Fernau (Eds.), LATA 2008, LNCS 5196 (pp. 333–344). Springer.

    Google Scholar 

  31. Krassovitskiy, A., Rogozhin, Y., & Verlan, S. (2011). Computational power of insertion-deletion (P) systems with rules of size two. Natural Computing, 10, 835–852.

    MathSciNet  MATH  Google Scholar 

  32. Kuppusamy, L., Rama, R. (2003). On the power of tissue P systems with insertion and deletion rules. In: Pre-proc of workshop on membrane computing, volume 28 of Report RGML (pp. 304–318). Univ. Tarragona.

  33. Kuppusamy, L., & Mahendran, A. (2016). Modelling DNA and RNA secondary structures using matrix insertion-deletion systems. International Journal of Applied Mathematics and Computer Science, 26(1), 245–258.

    MathSciNet  MATH  Google Scholar 

  34. Kuppusamy, L., Mahendran, A., & Krishna, S. N. (2011). Matrix insertion- deletion systems for bio-molecular structures. In R. Natarajan & A. K. Ojo (Eds.), Distributed computing and internet technology, 7th international conference, ICDCIT (LNCS) (Vol. 6536, pp. 301–312). Springer.

    Google Scholar 

  35. Kutrib, M., & Malcher, A. (2007). Finite turns and the regular closure of linear context-free languages. Discrete Applied Mathematics, 155(16), 2152–2164.

    MathSciNet  MATH  Google Scholar 

  36. Lazo, P. P. L., Cabarle, F. G. C., & Adorna, H. N. (2021). A return to stochasticity and probability in spiking neural P systems. Journal of Membrane Computing. https://doi.org/10.1007/s41965-021-00072-4.

    Article  MathSciNet  MATH  Google Scholar 

  37. Mahalingam, K., & Paul, P. (2020). On Szilard languages of \(InsDel\) systems. Journal of Automata, Languages and Combinatorics, 25(4), 321–348.

    MathSciNet  MATH  Google Scholar 

  38. Mahalingam, K., Paul, P., & Mäkinen, E. (2018). On derivation languages of a class of splicing systems. Acta Cybernetica, 23, 1–13.

    MathSciNet  MATH  Google Scholar 

  39. Mahalingam, K., Paul, P., Song, B., Pan, L., & Subramanian, K. G. (2017). Derivation languages of Splicing P systems, BIC-TA 2017. CCIS, 791, 487–501.

    Google Scholar 

  40. Mäkinen, E. (1984). On context-free and Szilard languages. BIT, 24(2), 164–170.

    MathSciNet  MATH  Google Scholar 

  41. Marcus, S. (1969). Contextual grammars. Revue Roumaine de Mathématiques Pures et Appliquées, 14, 1525–1534.

    MathSciNet  MATH  Google Scholar 

  42. Margenstern, M., Păun, Gh., Rogozhin, Y., & Verlan, S. (2005). Context-free insertion-deletion systems. Theoretical Computer Science, 330(2), 339–348.

    MathSciNet  MATH  Google Scholar 

  43. Mihalache, V. (1996). Szilard languages associated to parallel communicating grammar systems. In: Developments in Language Theory II, At the Crossroads of Mathematics, Computer Science and Biology, Magdeburg, Germany, July 1995 (pp. 247–256). World Scientific.

  44. Moriya, E. (1973). The associate language and the derivation properties of formal grammars. Information and Control, 22, 139–162.

    MathSciNet  MATH  Google Scholar 

  45. Ochirbat, O., Ishdorj, T. O., & Cichon, G. (2020). An error-tolerant serial binary full-adder via a spiking neural P system using HP/LP basic neurons. Journal of Membrane Computing, 2(1), 42–48. https://doi.org/10.1007/s41965-020-00033-3.

    Article  MathSciNet  MATH  Google Scholar 

  46. Pan, L., Păun, Gh., & Zhang, G. (2019). Foreword: Starting. Journal of Membrane Computing, 1(1), 1–2.

    Google Scholar 

  47. Pan, L., Song, B., Nagar, A. K., & Subramanian, K. G. (2018). Language generating alphabetic flat splicing P systems. Theoretical Computer Science, 724, 28–34.

    MathSciNet  MATH  Google Scholar 

  48. Paul, P. (2020). On Szilard languages of labelled insertion grammars. Fundamenta Informetica, 172, 53–72.

    MathSciNet  MATH  Google Scholar 

  49. Paul, P., & Ray, K. S. (2020). Derivation languages and descriptional complexity measures of restricted flat splicing systems. Theoretical Computer Science, 16, 19–36.

    MathSciNet  MATH  Google Scholar 

  50. Păun, Gh. (1979). On Szilard’s languages associated to a matrix grammar. Information Processing Letters, 8(2), 104–105.

    MathSciNet  MATH  Google Scholar 

  51. Păun, Gh. (1983). On some families of Szilard languages. Bulletin mathématique de la Société des Sciences Mathématiques de la République Socialiste de Roumanie, 27(75), 259–265.

    MathSciNet  MATH  Google Scholar 

  52. Păun, Gh., Rozenberg, G., Salomaa, A., & Computing, D. N. A. (1998). New computing paradigms. Springer-Verlag.

    MATH  Google Scholar 

  53. Penttonen, M. (1974). On derivation language corresponding to context-free grammars. Acta Informatica, 3, 285–291.

    MathSciNet  MATH  Google Scholar 

  54. Penttonen, M. (1977). Szilard languages are \(log n\) tape recognizable. Elektron. Inf. verarb. Kybern., 13(11), 595–602.

    MathSciNet  MATH  Google Scholar 

  55. Pérez-Hurtado, I., Orellana-Martín, D., Zhang, G., & Pérez-Jiménez, M. J. (2019). P-Lingua in two steps: exibility and efficiency. Journal of Membrane Computing, 1(2), 93–102.

    MathSciNet  Google Scholar 

  56. Petre, I., & Verlan, S. (2012). Matrix insertion-deletion systems. Theoretical Computer Science, 456, 80–88.

    MathSciNet  MATH  Google Scholar 

  57. Raman, I., & Kuppusamy, L. (2019). On describing super-linear languages by matrix insertion-deletion systems. International Journal of Advanced Engineering Science and Applied Mathematics, 11(1), 11–24.

    MathSciNet  Google Scholar 

  58. Ramanujan, A. and Krithivasan, K. (2013). Control words of transition P systems, (BIC-TA 2012). In: Advances in Intelligent Systems and Computing201(2013), Springer.

  59. Ramanujan, A., & Krithivasan, K. (2012). Control languages associated with Spiking Neural P systems. Romanian Journal of Information Science and Technology, 15(4), 301–318.

    Google Scholar 

  60. Ramanujan, A., & Krithivasan, K. (2013). Control Languages Associated with Tissue P Systems. UCNC 2013, LNCS. 7956(2013). Springer.

    Google Scholar 

  61. Rong, H., Yi, K., Zhang, G., Dong, J., Paul, P., & Huang, Z. (2019). Automatic implementation of fuzzy reasoning spiking neural P systems for diagnosing faults in complex power systems. Complexity, 2019, 16 (Article ID 2635714).

    Google Scholar 

  62. Rozenberg, G., & Salomaa, A. (Eds.). (1997). Handbook of formal languages (Vol. 1). Springer.

    MATH  Google Scholar 

  63. Ruzzo, W. (1981). On uniform circuit complexity. Journal of Computer and System Sciences, 22(3), 365–383.

    MathSciNet  MATH  Google Scholar 

  64. Salomaa, A. (1973). Formal languages. Academic Press.

    MATH  Google Scholar 

  65. 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, 54(1), 1–31.

    Google Scholar 

  66. Song, B., Li, K., & Zeng, X. (2021). Monodirectional evolutional symport tissue P systems with promoters and cell division. IEEE Transactions on Parallel and Distributed Systems. https://doi.org/10.1109/TPDS.2021.3065397.

    Article  Google Scholar 

  67. Song, B., Zeng, X., Jiang, M., & Pérez-Jiménez, M. J. (2021). Monodirectional tissue P systems with promoters. IEEE Transactions on Cybernetics, 51(1), 438–450.

    Google Scholar 

  68. Stotskij, E. D. (1967). Some restrictions on derivations in context-sensitive grammars. Nauchno-Tekhnicheskaya Informatsiya Seriya, 2(7), 35–38.

    Google Scholar 

  69. Takahara, A., & Yokomori, T. (2003). On the computational power of insertion/deletion systems. Natural Computing, 2, 321–336.

    MathSciNet  MATH  Google Scholar 

  70. Valencia-Cabrera, L., Pérez-Hurtado, I., & Martínez-del-Amor, M. A. (2020). Simulation challenges in membrane computing. Journal of Membrane Computing, 2(4), 392–402.

    MathSciNet  MATH  Google Scholar 

  71. Verlan, S. (2007). On minimal context-free insertion-deletion systems. Journal of Automata, Languages and Combinatorics, 12(1–2), 317–328.

    MathSciNet  MATH  Google Scholar 

  72. Verlan, S. (2010). Recent developments on insertion-deletion systems. Computer Science Journal of Moldova, 18(2), 210–245.

    MathSciNet  MATH  Google Scholar 

  73. Wang, X., Zhang, G., Gou, X., Paul, P., Neri, F., Rong, H., et al. (2021). Multi-behaviors coordination controller design with enzymatic numerical P systems for robots. Integrated Computer-Aided Engineering, 28(2), 119–150.

    Google Scholar 

  74. Wang, T., Zhang, G., Zhao, J., He, Z., Wang, J., & Pérez-Jiménez, M. J. (2015). Fault diagnosis of electric power systems based on fuzzy reasoning spiking neural P systems. IEEE Transactions on Power Systems, 30(3), 1182–1194.

    Google Scholar 

  75. Zhang, X., Liu, Y., Luo, B., & Pan, L. (2014). Computational power of tissue P systems for generating control languages. Information Sciences, 2014, 285–297.

    MathSciNet  MATH  Google Scholar 

  76. Zhang, G., Pérez-Jiménez, M. J., & Gheorghe, M. (2017). Real-life applications with membrane computing. Springer.

    MATH  Google Scholar 

  77. Zhang, G., Pérez-Jiménez, M. J., Riscos-Núñez, A., Verlan, S., Konur, S., Hinze, T., & Gheorghe, M. (2021). Membrane computing models: implementations. Springer.

    Google Scholar 

  78. Zhang, G., Rong, H., Neri, F., & Pérez-Jiménez, M. J. (2014). An optimization spiking neural P system for approximately solving combinatorial optimization problems. International Journal of Neural Systems, 24(05), 1440006. https://doi.org/10.1142/s0129065714400061.

    Article  Google Scholar 

  79. Zhang, G., Shang, Z., Verlan, S., Martínez-del Amor, M. A., Yuan, C., Valencia-Cabrera, L., & Pérez-Jiménez, M. J. (2020). An overview of hardware implementation of membrane computing models. ACM Computing Surveys. https://doi.org/10.1145/3402456 (Article No.: 90).

    Article  Google Scholar 

  80. Zhu, M., Yang, Q., Dong, J., Zhang, G., Gou, X., Rong, H., et al. (2021). An adaptive optimization spiking neural P system for binary problems. International Journal of Neural Systems, 31(1), 1–17 (Article No. 2050054).

    Google Scholar 

Download references

Acknowledgements

This work was supported by the National Natural Science Foundation of China (61972324); the Sichuan Science and Technology Program (2021YFS0313, 2021YFG0133, 2021YFN0104, 2020YJ0433); the Beijing Advanced Innovation Center for Intelligent Robots and Systems (2019IRS14); the Artificial Intelligence Key Laboratory of Sichuan Province (2019RYJ06).

Author information

Authors and Affiliations

  1. School of Control Engineering, Chengdu University of Information Technology, Chengdu, 610225, China

    Prithwineel Paul, Gexiang Zhang, Dequan Guo & Ming Zhu

Authors
  1. Prithwineel Paul
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gexiang Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dequan Guo
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ming Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gexiang Zhang.

Ethics declarations

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.

Appendix

Appendix

Theorem 23

\(hSZMat_2INS_1^{0,1}DEL_1^{1, 1} = RE.\)

Proof

From Theorems 6 and 22. \(\square\)

Theorem 24

\(hSZMat_2INS_1^{1,1}DEL_1^{1,0} = RE.\)

Proof

\(A = \{\theta S_1 \# \$ \}\).

(II) For \(r_i: X \rightarrow bY\):

if \(b \in N^{''}\)

if \(b \in T_1\)

\(r_{i1}: [(\lambda , \lambda / r_{i_1}, X), (\#, \lambda / r_i^{1}, \$)]\)

\(r_{i1}^{b}: [(\theta , \lambda / r_{i_1}, X), (\#, \lambda / r_i^{1}, \$)]\)

\(r_{i2}: [(r_{i_1}, X / \lambda , \lambda ), (\#, \lambda / r_i^{2}, r_i^{1})]\)

\(r_{i2}^{b}: [(r_{i_1}, X / \lambda , \lambda ), (\#, \lambda / r_i^{2}, r_i^{1})]\)

\(r_{i3}: [(\lambda , \lambda / b, r_{i_1}), (\#, \lambda / r_i^{3}, r_i^{2})]\)

\(r_{i3}^{b}: [(\theta , \lambda / Y, r_{i_1}), (\#, \lambda / r_i^{3}, r_i^{2})]\)

\(r_{i4}: [(b, \lambda / Y, r_{i_1}), (r_i^{3}, r_i^{2} / \lambda , \lambda )]\)

\(r_{i4}^{b}: [(Y, r_{i_1} / \lambda , \lambda ), (r_i^{3}, r_i^{2} / \lambda , \lambda )]\)

\(r_{i5}: [ (r_i^{3}, r_i^{1} / \lambda , \lambda )]\)

\(r_{i5}^{b}: [(r_i^{3}, r_i^{1} / \lambda , \lambda ), (\#, r_i^{3} / \lambda , \lambda )]\)

\(r_{i6}: [(Y, r_{i_1} / \lambda , \lambda ), (\lambda , r_i^{3} / \lambda , \$)]\)

 

\(\square\)

Theorem 25

\(hSZMat_2INS_1^{1,1}DEL_1^{0,1} = RE.\)

Proof

From Theorems 6 and 24. \(\square\)

Theorem 26

\(hSZMat_2INS_1^{1,0}DEL_2^{0,0} = RE.\)

Proof

\(A = \{\theta H S_1 E\}\).

(II) For \(r_i: X \rightarrow bY\):

if \(b \in N^{''}\)

if \(b \in T_1\)

\(r_{i1}: [(\lambda , X / \lambda , \lambda ), (E, \lambda / r_i^{1}, \lambda )]\)

\(r_{i1}^{b}: [(\lambda , X / \lambda , \lambda ), (E, \lambda / r_i^{1}, \lambda )]\)

\(r_{i2}: [(H, \lambda / Y_1^{r_i}, \lambda ), (E, \lambda / \#_{r_i}, \lambda )]\)

\(r_{i2}^{b}: [(H, \lambda / Y_1^{r_i}, \lambda ), (E, \lambda / \#_{r_i}, \lambda )]\)

\(r_{i3}: [(E, \lambda / \#_{r_i}^{'}, \lambda ), (E, \lambda / r_i^{2}, \lambda )]\)

\(r_{i3}^{b}: [(E, \lambda / \#_{r_i}^{'}, \lambda ), (E, \lambda / r_i^{2}, \lambda )]\)

\(r_{i4}: [(E, \lambda / r_i^{3}, \lambda ), (\lambda , \#_{r_i}^{'} \#_{r_i} / \lambda , \lambda )]\)

\(r_{i4}^{b}: [(E, \lambda / r_i^{3}, \lambda ), (\lambda , \#_{r_i} \#_{r_i}^{'} / \lambda , \lambda )]\)

\(r_{i5}: [(H, \lambda / b, \lambda ), (\lambda , r_i^{2} / \lambda , \lambda )]\)

\(r_{i5}^{b}: [(\theta , \lambda / r_i^{'}, \lambda ), (\lambda , r_i^{2} / \lambda , \lambda )]\)

\(r_{i6}: [(\lambda , H / \lambda , \lambda ), (Y_1^{r_i}, \lambda / Y_2^{r_i}, \lambda )]\)

\(r_{i6}^{b}: [(\lambda , r_i^{'} H / \lambda , \lambda ), (Y_1^{r_i}, \lambda / Y_2^{r_i}, \lambda )]\)

\(r_{i7}: [(Y_2^{r_i}, \lambda / H, \lambda ), (\lambda , r_i^{3} r_i^{1} / \lambda , \lambda )]\)

\(r_{i7}^{b}: [(Y_2^{r_i}, \lambda / H, \lambda ), (\lambda , r_i^{3} r_i^{1} / \lambda , \lambda )]\)

\(r_{i8}: [(H, \lambda / Y, \lambda ), (\lambda , Y_1^{r_i}Y_2^{r_i} / \lambda , \lambda )]\)

\(r_{i8}^{b}: [(H, \lambda / Y, \lambda ), (\lambda , Y_1^{r_i}Y_2^{r_i} / \lambda , \lambda )]\)

\(\square\)

Theorem 27

\(hSZMat_2INS_1^{0,1}DEL_2^{0,0}= RE.\)

Proof

From Theorems 6 and 26. \(\square\)

Theorem 28

\(hSZMat_2INS_2^{0,0}DEL_1^{1,0}= RE.\)

Proof

(II) For \(r_i: X \rightarrow bY\):

if \(b \in N^{''}\)

if \(b \in T_1\)

\(r_{i1}: [(\lambda , \lambda / bY, \lambda ), (Y, X / \lambda , \lambda )]\)

\(r_{i1}^{b}: [(\lambda , \lambda / r_{i_1}Y, \lambda ), (Y, X / \lambda , \lambda )]\)

 

\(r_{i2}^{b}: [(\$, r_{i_1} / \lambda , \lambda )]\)

\(\square\)

Theorem 29

\(hSZMat_2INS_2^{0,0}DEL_1^{0,1} = RE.\)

Proof

From Theorems 6 and 28. \(\square\)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Paul, P., Zhang, G., Guo, D. et al. On homomorphic images of the Szilard languages of matrix insertion–deletion systems with matrices of size 2. J Membr Comput 4, 68–86 (2022). https://doi.org/10.1007/s41965-021-00086-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s41965-021-00086-y

Keywords

Search

Navigation