nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

An Overview of 2D Picture Array Generating Models Based on Membrane Computing

verfasst von : K. G. Subramanian, Sastha Sriram, Bosheng Song, Linqiang Pan

Erschienen in: Reversibility and Universality

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A variety of two-dimensional array grammar models generating picture array languages have been introduced and investigated, utilizing and extending the well-established notions and techniques of formal string language theory. On the other hand the versatile computing model with a generic name of P system in the area of membrane computing, has turned out to be a rich framework for different kinds of problems in a variety of fields. Picture array generation in the field of two-dimensional (2D) languages is one such area where P systems with array objects and array rewriting, referred to as array P systems, have been fruitfully employed in increasing the generating power of the 2D grammar models. A variety of array P systems have been proposed in the literature. The objective of this survey is to review and describe the salient features of the major types of array P systems, which have served as the basis for developing other kinds of array P systems. Applications of these array P systems are also briefly described besides indicating possible new directions of investigation.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel On the Reversibility of ECAs with Fully Asynchronous Updating: The Recurrence Point of View

Nächstes Kapitel Input-Position-Restricted Models of Language Acceptors

Bersani, M.M., Frigeri, A., Cherubini, A.: Expressiveness and complexity of regular pure two-dimensional context-free languages. Int. J. Comput. Math. 90(8), 1708–1733 (2013)CrossRefMATH

Besozzi, D., Ferretti, C., Mauri, G., Zandron, C.: Parallel rewriting P systems with deadlock. DNA Computing. Lecture Notes Computer Science, vol. 2568, pp. 302–314. Springer, Berlin (2003)CrossRef

Besozzi, D., Mauri, G., Zandron, C.: Hierarchies of parallel rewriting P systems - a survey. New Gener. Comput. 22(4), 331–347 (2004)CrossRefMATH

Bottoni, P., Labella, A., Martin-Vide, C., Păun, Gh: Rewriting P systems with conditional communication. Formal and Natural Computing. Lecture Notes in Computer Science, pp. 325–353. Springer, Berlin (2002)CrossRef

Ceterchi, R., Mutyam, M., Pǎun, Gh, Subramanian, K.G.: Array-rewriting P systems. Nat. Comput. 2, 229–249 (2003)MathSciNetCrossRefMATH

Ceterchi, R., Subramanian, K.G., Venkat, I.: P systems with parallel rewriting for chain code picture languages. In: Proceeding 11th Conference on Computability in Europe (CiE), pp. 45–155 (2015)

Chen, H., Freund, R., Ionescu, M., Păun, G., Pérez-Jiménez, M.J.: On string languages generated by spiking neural P systems. Fundam. Inf. 75(1–4), 141–162 (2007)MathSciNetMATH

Dersanambika, K.S., Krithivasan, K.: Contextual array P systems. Int. J. Comput. Math. 81(8), 955–969 (2004)MathSciNetCrossRefMATH

Ferretti, C., Mauri, G., Păun, Gh, Zandron, C.: On three variants of rewriting P systems. Theor. Comput. Sci. 301, 201–215 (2003)MathSciNetCrossRefMATH

10.

Fernau, H., Freund, R ., Holzer, M.: The generative power of d-dimensional \(\#\)-context-free array grammars. In: Proceedings Intenational Colloquium Universal Machines and Computations, MCU’98, Vol. II, pp. 43–56 (1998)

11.

Fernau, H., Freund, R., Holzer, M.: Regulated array grammars of finite index. Part I: theoretical investigations. Grammatical Models of Multi-Agent Systems, pp. 157–181. Gordon and Breach, Reading (1999)

12.

Fernau, H., Freund, R., Holzer, M.: Regulated array grammars of finite index. Part II: syntactic pattern recognition. Grammatical Models of Multi-Agent Systems, pp. 284–296. Gordon and Breach, Reading (1999)

13.

Fernau, H., Freund, R., Schmid, M.L., Subramanian, K.G., Wiederhold, P.: Contextual array grammars and array P systems. Ann. Math. Artif. Intell. 75(1–2), 5–26 (2015)MathSciNetCrossRefMATH

14.

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)

15.

Freund, R.: Array grammars. Technical Rep. 15/00, Research Group on Mathematical Linguistics, Rovira i Virgili University, Tarragona, 164 pages (2000)

16.

Freund, R., Păun, Gh, Rozenberg, G.: Contextual array grammars. In: Subramanian, K.G., et al. (eds.) Formal Models, Languages and Applications. Series in Machine Perception and Artificial Intelligence, vol. 66, pp. 112–136. World Scientific, Signapore (2007)CrossRef

17.

Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Rozenberg, G., Salomaa, G. (eds.) Handbook of Formal Languages, pp. 215–267. Springer, Berlin (1997)CrossRef

18.

Isawasan, P., Muniyandi, R.C., Venkat, I., Subramanian, K.G.: Array-rewriting P systems with basic puzzle grammar rules and permitting features. International Conference on Membrane Computing. Lecture Notes in Computer Science, vol. 10105, pp. 272–285. Springer, Berlin (2017)CrossRef

19.

Isawasan, P., Venkat, I., Muniyandi, R.C., Subramanian, K.G.: A membrane computing model for generation of picture arrays. Advances in Visual Informatics. Lecture Notes in Computer Science, pp. 155–165. Springer, Berlin (2015)CrossRef

20.

Jiang, K., Chen, W., Zhang, Y., Pan, L.: On string languages generated by sequential spiking neural P systems based on the number of spikes. Nat. Comput. 15(1), 87–96 (2016)MathSciNetCrossRef

21.

Krishna, S.N., Rama, R.: On the power of P systems based on sequential/parallel rewriting. Int. J. Comput. Math. 77(1–2), 1–14 (2000)

22.

Krishna, S.N., Rama, R.: A note on parallel rewriting in P systems. Bull. EATCS 73, 147–151 (2001)MathSciNetMATH

23.

Krithivasan, K., Păun, Gh, Ramanujan, A.: On controlled P systems. Fundam. Inf. 131(3–4), 451–464 (2014)MathSciNetMATH

24.

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

25.

Morita, K.: Two-dimensional languages. In: Martin-Vide, C., Mitrana, V., Păun, Gh (eds.) Formal Languages and Applications. Series in Fuzziness and Soft Computing, vol. 148, pp. 426–437. Springer, Berlin (2004)CrossRef

26.

Păun, Gh: Marcus contextual grammars. Studies in Linguistics and Philosophy, vol. 67. Springer, Dordrecht (1997)CrossRefMATH

27.

Pǎun, Gh: Computing with membranes. J. Comput. Syst. Sci. 61, 108–143 (2000)MathSciNetCrossRefMATH

28.

Păun, Gh: Membrane Computing: An Introduction. Springer, Berlin (2000)MATH

29.

Pan, L., Pǎun, Gh: On parallel array P systems. Automata, Universality, Computation. Emergence, Complexity and Computation, vol. 12, pp. 171–181. Springer, Berlin (2015)

30.

Păun, Gh, Rozenberg, G., Salomaa, A.: The Oxford Handbook of Membrane Computing. Oxford University Press, New York (2010)CrossRefMATH

31.

Pan, L., Song, B., Subramanian, K.G.: Rewriting P systems with flat-splicing rules. Proceeding International Conference on Membrane Computing, vol. 10105, pp. 340–345. Springer, Berlin (2016)

32.

Ramanujan, A., Krithivasan, K.: Control languages associated with spiking neural P systems. Rom. J. Inf. Sci. Technol. 15(4), 301–318 (2012)

33.

Rosenfeld, A.: Picture Languages. Academic Press, Reading (1979)MATH

34.

Rosenfeld, A., Siromoney, R.: Picture languages - a survey. Lang. Des. 1(3), 229–245 (1993)

35.

Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, vol. 3. Springer, Berlin (1997)MATH

36.

Salomaa, A.: Formal Languages. Academic Press, Reading (1973)MATH

37.

Siromoney, G., Siromoney, R., Krithivasan, K.: Abstract families of matrices and picture languages. Comput. Gr. Image Process. 1, 284–307 (1972)MathSciNetCrossRefMATH

38.

Siromoney, G., Siromoney, R., Krithivasan, K.: Array grammars and Kolam. Comput. Gr. Image Process. 3(1), 63–82 (1974)CrossRefMATH

39.

Siromoney, R., Subramanian, K.G., Rangarajan, K.: Parallel/sequential rectangular arrays with tables. Int. J. Comput. Math. 6(2), 143–158 (1977)MathSciNetCrossRefMATH

40.

Subramanian, K.G.: P Systems and picture languages. Machines, Computations, and Universality. Lecture Notes in Computer Science, pp. 99–109. Springer, Berlin (2007)CrossRef

41.

Subramanian, K.G., Ali, R.M., Geethalakshmi, M., Nagar, A.K.: Pure 2D picture grammars and languages. Discret. Appl. Math. 157(16), 3401–3411 (2009)MathSciNetCrossRefMATH

42.

Subramanian, K.G., Isawasan, P., Venkat, I., Pan, L.: Parallel array-rewriting P systems. Rom. J. Inf. Sci. Technol. 17(1), 103–116 (2014)

43.

Subramanian, K.G., Isawasan, P., Venkat, I., Pan, L., Nagar, A.K.: Array P systems with permitting features. J. Comput. Sci. 5(2), 243–250 (2014)MathSciNetCrossRef

44.

Subramanian, K.G., Pan, L., Lee, S.K., Nagar, A.K.: A P system model with pure context-free rules for picture array generation. Math. Comput. Model. 52, 1901–1909 (2010)MathSciNetCrossRefMATH

45.

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 (2007)

46.

Subramanian, K.G., Saravanan, R., Robinson, T.: P system for array generation and application to kolam patterns. Forma 22, 47–54 (2007)MathSciNet

47.

Subramanian, K.G., Saravanan, R., Geethalakshmi, M., Helen Chandra, P., Margenstern, M.: P systems with array objects and array rewriting rules. Prog. Nat. Sci. 17(4), 479–485 (2007)MathSciNetCrossRefMATH

48.

Sureshkumar, W., Rama, R.: Chomsky hierarchy control on isotonic array P systems. Int. J. Pattern Recogit. Artif. Intell. 30(2), 1–20 (2016)MathSciNet

49.

Sureshkumar, W., Rama, R., Krishna, S.N.: 8-directional array P systems: power and hierarchy. In: Gheorghe, M., et al. (eds.) Multidisciplinary Creativity, pp. 150–169. Spandugino Publishing House, Bucharest (2015)

50.

Yamamoto, Y., Morita, K., Sugata, K.: Context-sensitivity of two-dimensional regular array grammars. Array Grammars, Patterns and Recognizers. WSP Series in Computer Science, vol. 18, pp. 17–41. World Scientific, Singapore (1989)CrossRef

51.

Wang, P.S.P. (ed.): Array Grammars Patterns and Recognizers. World Scientific, Singapore (1989)

52.

Wang, P.S.P.: A Formal Parallel Model for Three-Dimensional Object Pattern Representation. In: Chen, C.H., et al. (eds.) Handbook of Pattern Recognition and Computer Vision, pp. 211–231. World Scientific, Singapore (2010)

53.

Wu, T., Zhang, Z., Pan, L.: On languages generated by cell-like spiking neural P systems. IEEE Trans. NanoBiosci. 15(5), 455–467 (2016)CrossRef

54.

Zeng, X., Xu, L., Liu, X., Pan, L.: On languages generated by spiking neural P systems with weights. Inf. Sci. 278, 423–433 (2014)MathSciNetCrossRefMATH

55.

Zhang, G., Pan, L.: A survey of membrane computing as a new branch of natural computing. Chin. J. Comput. 33(2), 208–214 (2010)CrossRef

56.

Zhang, X., Zeng, X., Pan, L.: On string languages generated by spiking neural P systems with exhaustive use of rules. Nat. Comput. 7(4), 535–549 (2008)MathSciNetCrossRefMATH

Titel: An Overview of 2D Picture Array Generating Models Based on Membrane Computing
verfasst von: K. G. Subramanian
Sastha Sriram
Bosheng Song
Linqiang Pan
Verlag: Springer International Publishing
Buch: Reversibility and Universality
Print ISBN: 978-3-319-73215-2

Electronic ISBN: 978-3-319-73216-9

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-73216-9_16

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"