Complexity Perspectives on Minimal Cooperation in Cell-like Membrane Systems

BULLETIN of the International Membrane Computing Society IMCS Number 2 December 2016 Bulletin Webpage: http://membranecomputing.net/IMCSBulletin Webmaster: Andrei Florea, [email protected] Foreword This is the second issue of our Bulletin, completing the first year of the existence of the International Membrane Computing Society. We hear often the “wise statement” that it is easy to start, not to easy to go on... There are big chances that our project, IMCS and its Bulletin, is one further evidence which disproves this statement. We also know that “even the journey of one thousand miles begins with one step” (Lao Tzu). In what concerns the Bulletin, this is already the second step... This second issue of the Bulletin is significantly larger, but it has a similar structure as the first issue, the June 2016 one. A tool for connecting the MC community, a channel through which a broad range of information become available to the many groups working in this research area, from Europe to China, from Canada to New Zealand. In my opinion, one of the items included deserves a special mentioning: the list of PhD theses completely or only partially dealing with topics in MC. There are more that 85 titles, and this is really a large number. Encouraging is also the evolution in time of the number of theses, which proves the robustness of MC, due especially to the increased number of applications, in a wider range of areas. It is important to stress that the contents of the IMCS Bulletin is conceived as a working material, the Bulletin is a “blackboard” where each member of the MC community (and any future member, too) can write a message to the other members of the community, with this “blackboard” also visible to the entire community and also outside the community: each issue gradually grows and remains available at http://membranecomputing.net/IMCSBulletin), also being printed. (If somebody wants to have a printed copy, s/he has to contact the IMCS secretary – see information about the structure of IMCS, including email addresses, in the subsequent pages.) The “instructions to contributors” are minimal. Any material which any MC researcher considers of interest for the community, helping in achieving the goals of IMCS, is very much welcome and can be submitted at any time to the bulletin editor (myself for a while) or to any member of the Bulletin Committee. In what 4 Foreword concerns the style and format, the previous issues of the Bulletin are available as a model. (If an author needs more precise instructions, please contact me. Standard Latex files are sufficient, LNCS style is the best.) The copyright of all materials remains with their authors. * The realization of this issue of the Bulletin of IMCS owns very much (i) to all contributors, (ii) to the webmaster, Andrei Florea, [email protected], and to the MC research group in Politechnica University in Bucharest, led by prof. C˘at˘alin Buiu, where the bulletin is hosted, and (iii) to prof. Gexiang Zhang, the President of IMCS, to his group, and to the Xihua University in Chengdu, China, where the bulletin is printed. Gheorghe P˘aun December 10, 2016 Contents Letter from the President ................................................ 9 IMCS Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 – Structure of IMCS .................................................. 11 – Constitution of IMCS ............................................... 17 News from MC Research Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 – The Research Group on Modeling, Simulation and Verification of Biological Systems at the University of Pisa . . . . . . . . . . . . . . . . . . . . . . 23 – Research Group on Bio-Inspired Computing at Huazhong University of Science and Technology in China . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 – Hong Peng, Jun Wang: RGMCA: Research Group on Membrane Computing and Applications at Xihua University, Chengdu . . . . . . . . . . 31 – Jos´e M. Sempere: The Spanish Thematic Network on Biomolecular and Biocellular Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 – Formal Methods Laboratory (FML) in Ia¸si . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Bibliographies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 – Marian Gheorghe: Kernel P Systems Bibliography . . . . . . . . . . . . . . . . . . . 47 – PhD Theses in Membrane Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 – Membrane Computing, 16th International Conference, CMC 2015, Valencia, Spain, August 17-21, 2015, Revised Selected Papers, LNCS 9504, Springer-Verlag, Berlin, 2015 . . . . . . . . . . . . . . . . . . . 55 – Ludek Cienciala: Membrane Agents – Book Summary . . . . . . . . . . . . . . . 61 6 Contents – Andrew Adamatzky, ed.: Advances in Unconventional Computing. Vol. I: Theory, Vol. 2: Prototypes, Models and Algorithms. Springer, 2016 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 Tutorials, Surveys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 – Luis Valencia-Cabrera, David Orellana-Mart´ın, Agust´ın Riscos-N´u˜nez, Mario J. P´erez-Jim´enez: Complexity Perspectives on Minimal Cooperation in Cell-like Membrane Systems . . . . . . . . . . . . . . . . . . . . . . . . . 69 – Artiom Alhazov, Rudolf Freund, Sergiu Ivanov: Polymorphic P Systems: A Survey ............................................... 79 – Daniel D´ıaz-Pernil, Miguel A. Guti´errez-Naranjo, Hong Peng: Some Notes on Membrane Computing and Image Processing . .. . . . . 103 – Lucie Ciencialov´a, Erzs´ebet Csuhaj-Varj´u, Ludˇek Cienciala, Petr Sos´ık: P Colonies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 Technical Notes, Open Problems, Inquiries, Answers . . . . . . . . 157 – Vincenzo Manca: Multiset Generalization of Balanced Chemical Reactions ................................................ 157 – Matteo Cavaliere, Alvaro Sanchez: Evolutionary Resilience of Membrane Computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 – Gheorghe P˘aun, Jos´e M. Sempere: Families of Languages Associated with SN P Systems: Preliminary Ideas, Open Problems .................................................... 161 – Marian Gheorghe: Membrane Systems Analysis . . . . . . . . . . . . . . . . . . . . 165 – Alan Mehlenbacher: P System for Two-Level Economic Exchange with Investment ................................................... 167 – Linqiang Pan, Gheorghe P˘aun, Gexiang Zhang: SN P Systems with Communication on Request . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 Abstracts of PhD Theses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 – Christian Bodenstein: Theoretical Analysis of Cyclic Processes in Biology in the Context of Ca2+ Oscillations, Circadian Rhythms and Synthetic Oscillators ................................. 195 – Zhiqiang Zhang: Research on the Computational Power of Numerical P Systems ........................................... 200 – Lea Weber: Implementation of an Artificial Evolution for Optimal Placement of Processing Units on a Freely Configurable Two-dimensional Grid Map ........................... 204 Contents 7 – Sergiu Ivanov: On the Power and Universality of Biologically-Inspired Models of Computation ..................... 207 – Ciprian Dragomir: Formal Verification of P Systems ............... 210 – Tao Wang: Spiking Neural P Systems and Their Applications in Fault Diagnosis of Electric Power Systems ...................... 212 Calls for Participation to MC Conferences/Meetings . . . . . . . . 217 – Call for Participation Fifteenth Brainstorming Week on Membrane Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 – CMC 18, 24-28 July 2017, Bradford, UK. First Call for Papers .. . . . 219 – Call for Papers WMC at UCNC 2017, Fayetteville, USA . . . . . . . . . . . 223 Reports on MC Conferences/Meetings . . . . . . . . . . . . . . . . . . . . . . 225 – Alberto Leporati, Claudio Zandron: Report on CMC17 The Seventeenth Conference on Membrane Computing . . . . . . . . . . . . . 225 – Linqiang Pan, Gexiang Zhang, Ravie Chandren Muniyandi, Bosheng Song: A Summary of The 5th Asian Conference on Membrane Computing (ACMC 2016) . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 – Marian Gheorghe, Savas Konur: Workshop on Membrane Computing at the International Conference on Unconventional Computation and Natural Computation, Manchester, UK, July 11-15 2016................................................ 235 – Svetlana Cojocaru, Alexandru Colesnicov, Ludmila Malahov: Workshop on Unconventional Computing Systems in commemoration of Yurii Rogozhin Chi¸sin˘au, Moldova, November 11, 2016 . . . . . . . . . . 237 Miscellanea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 Gheorghe P˘aun: Some Wonders of a Bio-Computer-Scientist . . . . . . . 241 Letter from The President Dear IMCS members, Merry Christmas and Happy New Year to you all! The first issue of our Bulletin has achieved a great success since it was published on the website in June. Tens of hard copies have also been distributed to each research group in the P system community during the 17th International Conference on Membrane Computing (CMC 2016), which was held in Milano, Italy, and The 5th Asian Conference on Membrane Computing (ACMC 2016), which was held at the Universiti Kebangsaan Malaysia (The National University of Malaysia), Bangi, Selangor, Malaysia. The two conferences were rather successful, organized this year under the auspices and with the support of International Membrane Computing Society (IMCS). First of all, I would like to share the great news that our Honorary President, prof. Gheorghe P˘aun, received the Order of the Star of Romania (Romania’s highest civil Order) on December 1, 2016, which was awarded by the President of Romania in recognition of his life achievements in science. Let us congratulate him on his ground breaking scientific contributions. He also received the title of Honorary Professor of Xihua University, Chengdu, China, in November. One of our aims is to strengthen the collaborations within the P system community. We are trying our best to accomplish this. Here I just list three examples. ACMC 2016 received an increased number of submissions, 39, this year. Prof. Gheorghe P˘aun visited China in October and November. During his visit, he delivered a series of lectures on Automata and Formal Languages, consisting of six parts: Chomsky hierarchy, Regulated rewriting, Grammar systems, Lindenmayer (L) systems, Marcus contextual grammars and Splicing (Head, H) systems. More than twenty teachers and students attended the lectures. Another example is that Sergey Verlan and myself started to jointly supervise a PhD student from this 16 Structure of IMCS 6. The nominations for the year Y should reach the Awards Chair before 20 of January of the year Y+1. The Awards Committee members decide the winners by the middle of February, and the prizes are awarded at the first edition of BWMC, CMC or ACMC where the winners participate in. 7. The members of the Awards Committee and the rules of functioning can be changed every year, after March 1, at the proposal of the Chair person or of any member of the IMCS Board, subject to a vote in the IMCS Board. The IMCS prizes are mainly meant to reward the excellency in MC research, equally focusing on theory and applications, and to encourage young researchers. The prizes are not subject to competitions, they do not identify the best PhD thesis or paper or application, they just point that a certain work/result is of a high value. This does not imply that other works/results are not so. We cannot rank scientific results like in sport, in a mathematical sense. We only want to call attention to certain works – thus also calling attention to MC and to IMCS. The prestige of a prize will be given by the prestige of the winners, also on their evolution in time, during their careers. To reach these goals, we have to be conservative, exigent, transparent in our nominations and, especially, in selection. Nominations for the prizes for 2016 are waited for until January 20, 2017, and can be sent at any time, electronically, to any member of the Awards Committee (preferably with a CC to all members). Constitution of the International Membrane Computing Society – IMCS Article 1: Name (1.1.) The name of the Society shall be International Membrane Computing Society, abbreviated IMCS. (1.2.) The logo of IMCS is the one in the figure below. It should appear in all relevant places, such as IMCS web page, posters, calls, on the cover of the Bulletin of IMCS, etc. Article 2: Objects (2.1.) The society shall be a nonprofit academic organization, having as its goal to promote the development of membrane computing (MC), internationally, at all levels (theory, applications, software, implementations, connection with related areas, etc.). 18 Constitution of IMCS (2.2.) A special attention will be paid to the communication/cooperation inside MC community, to connections with other professional scientific organizations with similar aims, and to promoting MC to young researchers. (2.3.) IMCS will publish proceedings, journals or other materials, printed or electronically, as it sees fit. (2.4.) IMCS will organize yearly MC meetings, such as the Conference on Membrane Computing (CMC), the Asian Conference on Membrane Computing (ACMC), the Brainstorming Week on Membrane Computing (BWMC), as well as further workshops/meetings, as it sees fit. Article 3: Membership (3.1.) There are four categories of members: Honorary Members, Regular Members, Student Members, and Institution Members. (3.2.)The Honorary Members are elected by the IMCS Board (email voting, majority rule). Regular membership is open to all persons interested, on completing a membership form. (3.3.) Student Members can be undergraduate, master, and PhD students, and they are eligible for various facilities IMCS is planning for students. (3.4.) Institutions which want to join IMCS and support it can become Institution Members. Any support/sponsorship from an institution will be acknowledged in an appropriate way in IMCS publications. (3.5.) Any member, of any kind, is supposed to know and accept the Constitution of IMCS. Article 4: Structure (4.1.) The structure of IMCS and its governance are as specified in the next figure. The figure also specifies the ten Honorary Members with whom the Society starts (February 2016). (4.2.) Gheorghe P˘aun, the founder of MC, is appointed Honorary President of IMCS. (4.3.) The work of IMCS is organized and conducted by the Board of IMCS, consisting of the Executive Board and the Advisory Board. The Advisory Board should have between 10 and 20 members, hence in total the IMCS Board should contain between 20 and 30 members, (4.4.) The Executive Board consists of four individual positions: President, Vice President, Treasurer, and Secretary, and six Committees: Bulletin, Website, PR, Publication, Conferences, and Awards Committee. Each of these six Committees has a chair person. The Advisory Board also has a chair person. (4.5.) The four individual positions from the Executive Board, the six chair persons of the Committees, the members of the Advisory Board, and the chair of the Advisory Board are elected by the IMCS Board (email voting, majority rule). Each chair of a Committee appoints a number of Committee members as he/she sees fit. Constitution of IMCS 19 (4.6.) All the elected positions are elected for one year. After one year, a change of an elected person can be proposed by the President or the Vice President of the IMCS Board, by the person itself (resignation), or by two thirds of members of the IMCS Board, and it is voted in the IMCS Board (email voting, majority rule). If there is no change proposal, then the person who occupies any position in the IMCS Board continues in the same position, for one further year. ✬ ✫ ✩ ✪ ✬ ✫ ✩ ✪ ✬ ✫ ✩ ✪ ✗ ✖✔ ✕ ✗ ✖✔ ✕ ✗ ✖✔ ✕ ✗ ✖✔ ✕ ✗ ✖✔ ✕ ✗ ✖✔ ✕ ✓ ✒✏ ✑ ✗ ✖✔ ✕ ✓ ✒✏ ✑ ✗ ✖✔ ✕ IMCS Board Executive Board Advisory Board President Vice President Treasurer Secretary Bulletin Committee Website Committee PR Committee Publication Committee Conferences Committee Awards Committee 10-20 members 20-30 members ✬ ✫ ✩ ✪ Honorary President: Gheorghe P˘aun Honorary Members: Solomon Marcus Arto Salomaa Grzegorz Rozenberg Kamala Krithivasan Oscar H. Ibarra Takashi Yokomori Tom Head J¨urgen Dassow Lila Kari Cristian S. Calude ★ ✧✥ ✦ ✬ ✫ ✩ ✪ ✬ ✫ ✩ ✪ ✬ ✫ ✩ ✪ ✬ ✫ ✩ ✪ Institution Members Individual Regular Members Student Members Article 5: Duties and competencies (5.1.) The IMCS Board President represents the Society in relation with any external entity, organizes/coordinates the activity of the IMCS Board, initiates voting in the IMCS Board, chairs any panel/meeting of the Society. (5.2.) The Vice President helps the President in all his/her activity, represents the President when he/she is not available (e.g., in chairing panels/meetings). Every year, the President and the Vice President present a common report 20 Constitution of IMCS about IMCS activity, first circulating it by email in the IMCS Board and, after possible corrections, posting it in the IMCS web page. (5.3.) The Treasurer takes care of the income and expenses of IMCS, and each year presents a report in this respect to IMCS Board. This report is analyzed and voted in the IMCS Board (email voting, majority rule). (5.4.) The Secretary is responsible to keep a track record of the IMCS: memberships, reports, voting results, etc. (5.5.) The Bulletin Committee takes care of editing the Bulletin of IMCS, first accumulating information/materials in an electronic format and then printed, if needed/requested, with a periodicity to be decided by the IMCS Board. (5.6.) The Website Committee takes care of the IMCS web page, whose structure should be decided by the IMCS Board. (5.7.) The PR Committee is responsible with developing relationships with other similar organizations and promoting IMCS on various scientific forums, advertising its activity on specialised networks and at international events. (5.8.) The Publication Committee supervises the publication of proceedings, special issues of journals, collective volumes edited under the auspices of IMCS. Two particular goals of this Committee are to initiate a specialized journal, International Membrane Computing Journal, and a specialized series of monographs. (5.9.) The Conference Committee works as a steering committee for the two MC yearly conferences, CMC and ACMC, looking for venues, suggesting (in cooperation with the organizing committees) program committees and invited speakers, possible sponsors and publications. (5.10.) The Awards Committee collects nominations and decides the winners of three yearly IMCS Prizes: (1) The PhD Thesis of the Year, (2) The Theoretical Result of the Year, (3) The Application of the Year. The Awards Committee has its Rules of functioning, which are voted by the IMCS Board (email voting, majority rule). Article 6: Voting (6.1.) Each member of the IMCS Board (between 20 and 30 members) has one vote. (6.2.) A voting, on any subject, can be initiated by the President, the Vice President, or by two thirds of the IMCS Board members. (6.3.) The message proposing a vote should specify the issue to be decided in such a way that the alternatives YES and NO are clear. The message should be sent to all members of the IMCS Board, the voting messages of the members should also be sent to all members (full transparency). The voting should last 30 days. If a member is not replying in the first 15 days, the initiator of the vote should contact him/her once again. If a member is not replying even to the second message, then his/her vote is considered abstaining. (6.4.) ”Majority rule” means that at least half of the IMCS Board have voted (YES, NO, or abstaining) and the decision is made according to the number of Constitution of IMCS 21 YES and NO votes which is higher. In case of a draw, the vote of the President is decisive – unless if the President does not decide to repeat the vote, maybe changing the object of the vote. (6.5.) All ambiguities and uncovered cases should be clarified by discussions in the IMCS Board and, if decided so, proposed as amendments to the Constitution. Article 7: Panels (7.1.) On the occasions of IMCS annual meetings, like BWMC, CMC, and ACMC, panels should be organized, chaired by the President, the Vice President or, in their absence, by another member of the IMCS Board designated by the President, to discuss current issues of the Society. Article 8: Finance (8.1.) Income: possible membership fees, as decided by IMCS Board, donations, sponsorhips, conference registration fees, participation to research projects. (8.2.) Expenses: IMCS prizes, students support, Bulletin of IMCS hardcopy, maintaining web pages, sponsoring MC conferences – all these and anything else, under the control of the IMCS Board. Article 9: Amendments (9.1.) Amendments to IMCS Constitution can be proposed by any member of the IMCS Board, at any time. Any amendment should be discussed and voted in the IMCS Board (email voting, majority rule) and then, if accepted, published in the IMCS web page, thus being available to all members of IMCS. Article 10: Dissolution (10.1.) The dissolution of IMCS should be done in two steps: first, a vote in the IMCS Board is organized (email voting, two thirds majority), and, if the dissolution proposal passes, a general vote is organized, where all regular members participate (email voting, two thirds majority; in order the vote to be valid, at least half of the members should vote). (10.2.) If the Society decides to get dissolved, all remaining assets shall be donated to a similar organization, at the choice of the IMCS Board. Article 11. Provisory statement The present Constitution will get provisionally valid by being voted (by email, majority rule), in March 2016, in the IMCS Board, as this Board was constituted by consensus during BWMC 2016 and soon after that. Then, it will be published in the IMCS web page and, as soon as possible, in 2016, it will be voted by all individual members of IMCS (email voting, majority rule). The vote will last one month and to voting will participate all individual members of IMCS, students or regular, registered until the last day of the previous month. News from MC Research Groups The Research Group on Modeling, Simulation and Verification of Biological Systems at the University of Pisa 1 Contacts Dipartimento di Informatica Universit`a di Pisa Largo B. Pontecorvo, 3 56127 Pisa, Italy Group webpage: http://www.di.unipi.it/msvbio/ 2 Reserch activities The activity of the research group on modeling, simulation and verification of biological systems started in 2004, with the aim of developing formal notations and analysis techniques for biochemical systems. The class of notations we developed includes term rewriting systems, process calculi and automata-based formalisms. As analysis techniques we studied and applied stochastic simulation, model checking and abstract interpretation. Subsequently, we considered other classes of biological systems and phenomena, such as cellular pathways (in the context of systems biology), cancer development, and also systems of interest for population biology, ecology and evolution. Moreover, we conducted research on bio-inspired models of computation (in particular Membrane Systems and Reaction Systems). In particular, we worked on compositional semantics and formal analysis techniques for such bio-inspired models, and on variants of membrane systems for the modeling of populations and ecosystems. In parallel, we aimed at defining static analyses able to predict all possible evolutions of biological systems modeled in biologically inspired calculi. Such analyses 24 Research Group on Modeling Biological Systems, Pisa University address relevant properties such as temporal and causal properties and probabilistic termination in stochastic calculi. Reserch topics In order of affinity with Membrane Computing: •Theory of membrane systems [8, 9, 10, 18] •Formal semantics of membrane systems [11, 12] •Spatial P systems [7, 6] •Membrane systems for population and ecosystems modelling [2, 1, 3] •Reaction Systems [4, 5, 19] •Modelling formalisms for biochemical systems [13] •Computational models of cancer [22] •Cellular pathway components identification [20, 21] •Analyses of temporal and causal properties for biologically inspired calculi [16, 15, 14] •Analysis of probabilistic termination in stochastic calculi [17]. Conferences The group regularly contributes to the organization of the International Symposium “From Data to Models and Back (DataMod)”, formerly known as MoK- MaSD. DataMod aims at bringing together researchers interested in the combined application of computational modeling methods with data-driven techniques from the areas of knowledge management, data mining and machine learning. Modeling methodologies of interest include automata, agents, Petri nets, process algebras and rewriting systems. Application domains include social systems, ecology, biology, medicine, smart cities, governance, education, software engineering, and any other field that deals with complex systems and large amounts of data. DataMod (as it was for MoKMaSD) welcomes contributions in which notations and methodologies from membrane computing are exploited for the modeling and analysis of systems in any application domain. Contributions in which such methodologies are applied in synergy with with data-driven techniques would be of particular interest. The web page of the symposium is: http://pages.di.unipi.it/datamod/ 3 Components •Roberto Barbuti (full professor) http://pages.di.unipi.it/barbuti/ •Francesca Levi (associate professor) http://pages.di.unipi.it/levi/ Research Group on Modeling Biological Systems, Pisa University 25 •Roberta Gori (assistant professor) http://pages.di.unipi.it/gori/ •Paolo Milazzo (assistant professor) http://pages.di.unipi.it/milazzo/ •Giovanni Pardini (postdoc) http://pages.di.unipi.it/pardini/ •Pasquale Bove (phd student) •Giovanna Broccia (phd student) Selected publications 1. R. Barbuti, A. Bompadre, P. Bove, P. Milazzo, and G. Pardini. Attributed probabilistic p systems and their application to the modelling of social interactions in primates. In International Conference on Software Engineering and Formal Methods, pages 176–191. Springer, 2015. 2. R. Barbuti, P. Bove, P. Milazzo, and G. Pardini. Minimal probabilistic p systems for modelling ecological systems. Theoretical Computer Science, 608:36–56, 2015. 3. R. Barbuti, A. Cerone, A. Maggiolo-Schettini, P. Milazzo, and S. Setiawan. Modelling population dynamics using grid systems. In International Conference on Software Engineering and Formal Methods, pages 172–189. Springer, 2012. 4. R. Barbuti, R. Gori, F. Levi, and P. Milazzo. Investigating dynamic causalities in reaction systems. Theoretical Computer Science, 623:114–145, 2016. 5. R. Barbuti, R. Gori, F. Levi, and P. Milazzo. Specialized predictor for reaction systems with context properties. Fundamenta Informaticae, 147:1–19, 2016. 6. R. Barbuti, A. Maggiolo-Schettini, P. Milazzo, and G. Pardini. Simulation of spatial p system models. Theoretical Computer Science, 529:11–45, 2014. 7. R. Barbuti, A. Maggiolo-Schettini, P. Milazzo, G. Pardini, and L. Tesei. Spatial p systems. Natural Computing, 10(1):3–16, 2011. 8. R. Barbuti, A. Maggiolo-Schettini, P. Milazzo, G. Pardini, and S. Tini. Systolic automata and p systems. In Computing with New Resources, pages 17–31. Springer, 2014. 9. R. Barbuti, A. Maggiolo-Schettini, P. Milazzo, and L. Tesei. Timed p automata. Fundamenta Informaticae, 94(1):1–19, 2009. 10. R. Barbuti, A. Maggiolo-Schettini, P. Milazzo, and S. Tini. Ap systems flat form preserving step-by-step behaviour. Fundamenta Informaticae, 87(1):1, 2008. 11. R. Barbuti, A. Maggiolo-Schettini, P. Milazzo, and S. Tini. Compositional semantics and behavioral equivalences for p systems. Theoretical Computer Science, 395(1):77– 100, 2008. 12. R. Barbuti, A. Maggiolo-Schettini, P. Milazzo, and S. Tini. An overview on operational semantics in membrane computing. International Journal of Foundations of Computer Science, 22(01):119–131, 2011. 13. R. Barbuti, A. Maggiolo-Schettini, P. Milazzo, and A. Troina. The calculus of looping sequences for modeling biological membranes. In International Workshop on Membrane Computing, pages 54–76. Springer, 2007. 14. C. Bodei, L. Brodo, R. Gori, D. Hermith, and F. Levi. A global occurrence counting analysis for brane calculi. In Logic-Based Program Synthesis and Transformation - 25th International Symposium, LOPSTR 2015, Siena, Italy, July 13-15, 2015. Revised Selected Papers, pages 179–200, 2015. 32 H. Peng, J. Wang Her research work includes fuzzy spiking neural P systems and fault diagnosis of power systems. Dr. Xiaoxiao Song ([email protected]) graduated and received his PhD from Chongqing University. He is interested in optimization algorithm research, membrane computing and its application in industry control system. Dr. Zhang Sun ([email protected]) graduated and received his Ms Degree from Xihua University. Currently, he continues the research in order to complete his PhD. His specialty is hardware design and realization of membrane computing models through FPGA. Dr. Bing Gou ([email protected]) graduated received his PhD in 2016 from the Southwest Jiaotong University. In this year, he joined our team and tries to focus on membrane computing model and its application to fault diagnosis of electrical motors control. Ke Cheng is an M.S. degree student ([email protected], Chengdu) Ming Jun is an M.S. degree student ([email protected], Chengdu) Wenping Yu is an M.S. degree student ([email protected], Chengdu) Guangchun Chen is an M.S. degree student ([email protected], Chengdu) Juan Hu is an M.S. degree student ([email protected], Chengdu) 2 Research Interests and Results (1) Fuzzy spiking neural P systems and their applications in fault diagnosis: Fuzzy spiking neural P systems (FSN P systems, in short) are extensions of SN P systems which incorporate fuzzy logic techniques into the framework of SN P systems. The motivation was to make SN P systems a computing framework to model or express fuzzy production rules and to perform fuzzy reasoning. Two kinds of neurons are considered in FSN P systems: proposition neurons and rule neurons. Proposition neurons are used to express fuzzy propositions, while rule neurons are used to describe fuzzy production rules in a knowledge base. Moreover, fuzzy logic is integrated into both proposition and rule neurons. In recent years, fuzzy logics have been introduced to develop five kinds of FSN P systems: fuzzy spiking neural P systems with linguistic terms (lFSN P systems) [1], fuzzy reasoning spiking neural P systems (FRSN P systems) [2], weighted fuzzy spiking neural P systems (WFSN P systems) [3], adaptive fuzzy spiking neural P systems (AFSN P systems) [4] and fuzzy reasoning spiking neural P systems with trapezoidal fuzzy numbers (tFRSN P systems) [5]. FRSN P systems were firstly used to deal with fault diagnosis problem, where an instance of fault diagnosis of transformers was modeled and analyzed by FRSN P systems [2]. After that the fault diagnosis of power systems has been investigated, in [6, 7, 8], respectively. (2) Membrane computing-inspired data clustering: Membrane clustering algorithms are a class of clustering algorithms which are inspired form the Research Group of MC and Applications, Xihua University 33 mechanism of membrane computing models. The main idea is that a data clustering problem can be regarded as an optimization problem. So, the clustering problem can be solved by the use of P systems. H. Peng, J. Wang and their collaborators have discussed a membrane computinginspired clustering algorithm [9], in which a differential evolution mechanism is introduced as evolution rules to evolve a set of cluster centers. Then P systems were used to discuss different clustering problems, such as data clustering [10, 11, 12, 13, 14], fuzzy clustering [15, 16] and automatic clustering problems [17, 18]. In addition, P systems were used to induce a decision tree algorithm [19]. (3) Application of membrane computing in image processing/signal processing: In recent years our team used membrane computing model to solve a variety of image processing/signal processing problems. Five papers on the topic of application of membrane computing model in image and signal processing have been also published by H. Peng, J. Wang and their collaborators (region-based image segmentation [20, 21], clustering-based image segmentation [22], image thresholding [23, 24, 25, 26], image fusion [27], watermarking [28], and digital filter design [29, 30]). (4) Application of membrane computing in micro-grid: Improved particle swarm optimization, genetic algorithms and artificial fish swarm algorithms based on membrane computing are applied on the operation of distributed power, especially in economic operation of micro-grid and control strategy of micro-grid environmental protection optimization [31, 32, 33, 34, 35]. Ref. [36, 37, 38, 39, 40] applied different improved P systems in different control systems. 3 Publications and Teaching Our team members have published 40 papers (see references) and received five Chinese patents. There are now more than 8 graduate students working for their Master degree. References 1. J. Wang, L. Zhou, H. Peng, G. Zhang: An extended spiking neural P system for fuzzy knowledge representation. Int. J. Innov. Comput. Inform. Control., 7(7), 3709-3724 (2011) 2. H. Peng, J. Wang, M.J. P´erez-Jim´enez, H. Wang, J. Shao, T. Wang: Fuzzy reasoning spiking neural P system for fault diagnosis. Information Sciences, 235, 106-116 (2013) 3. J. Wang, P. Shi, H. Peng, M.J. P´erez-Jim´enez, T. Wang: Weighted fuzzy spiking neural P systems. IEEE Transaction on Fuzzy Systems, 21(2), 209-220 (2013) 4. J. Wang, H. Peng: Adaptive fuzzy spiking neural P systems for fuzzy inference and learning. Int. J. Comput. Math., 90(4), 857-868 (2013) 34 H. Peng, J. Wang 5. T. Wang, J. Wang, H. Peng, H. Wang: Knowledge representation and reasoning based on FRSN P system. In: Proc. WCICA, IEEE, 849-854 (2011) 6. M. Tu, J. Wang, H. Peng, P. Shi: Application of adaptive fuzzy spiking neural P systems in fault diagnosis of power systems. Chinese Journal of Electronics, 23(1), 87-92 (2014) 7. J. Wang, H. Peng, M. Tu, M.J. P´erez-Jim´enez, P. Shi: A fault diagnosis method of power systems based on an improved adaptive fuzzy spiking neural P systems and PSO algorithms. Chinese Journal of Electronics, 25(2), 320-327 (2016) 8. T. Wang, G. Zhang, J. Zhao, Z., He, J. Wang, M.J. P´erez-Jim´enez: Diagnosis of electric power systems based on fuzzy reasoning spiking neural P systems. IEEE Transaction on Power Systems, 30(3), 1182-1194 (2015) 9. H. Peng, J. Zhang, Y. Jiang, X. Huang, J. Wang: DE-MC: A membrane clustering algorithm based on differential evolution mechanism. Romanian Journal of Information Science and Technilogy, 17(1), 76-88 (2014) 10. L. Qin, F. Cheng, Z. Chen, X. Huang, H. Peng, J. Liu: A hybrid clustering algorithm based on P systems and Immune mechanisms, ICIC Express Letters, 9(2), 485-491 (2015) 11. H. Peng, X. Luo, Z. Gao, J. Wang, Z. Pei: A novel clustering algorithm inspired by membrane computing, The Scientific World Journal, Vol. 2015, Article ID 929471, 1-9 (2015) 12. J. Jin, H. Liu, F. Wang, H. Peng, J. Wang: Parallel Implementation of P Systems for Data Clustering on GPU. Bio-Inspired Computing - Theories and Applications, Volume 562 of the series Communications in Computer and Information Science, vol.562, 200-211 (2015) 13. X. Huang, H. Peng, Y. Jiang, J. Zhang, J. Wang: PSO-MC: a novel PSO-based membrane clustering algorithm, ICIC Express Letters, 8(2), 497-503 (2014) 14. Y. Jiang, H. Peng, X. Huang, J. Zhang, P. Shi: A novel clustering algorithm based on P systems, International Journal of Innovative Computing, Information and Control, 10(2), 753-765 (2014) 15. H. Peng, J. Wang, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: An unsupervised learning algorithm for membrane computing. Information Sciences, 304, 80-91 (2015) 16. H. Peng, Y. Jiang, J. Wang, M.J. P´erez-Jim´enez: Membrane clustering algorithm with hybrid evolutionary mechanisms. Journal of Software, 26(5), 1001-1012 (2015) 17. H. Peng, J. Wang, P. Shi, A. Riscos-N´u˜nez, M.J. P´erez-Jim´enez: An automatic clustering algorithm inspired by membrane computing, Pattern Recognition Letters, 68, 34-40 (2015) 18. H. Peng, J. Wang, P. Shi, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: An extended membrane system with active membrane to solve automatic fuzzy clustering problems. International Journal of Neural Systems, 26(3), 1-17 (2016) 19. J. Wang, J. Hu, H. Peng, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: Decision tree models induced by membrane systems. Romanian Journal of Information Science and Technology, 18(3), 228-239 (2015) 20. Y. Yang, H. Peng, Y. Jiang, X. Huang, J. Zhang: A region-based image segmentation method under P systems, Journal of Information and Computational Science, 10(10), 2943-2950 (2013) 21. H. Peng, Y. Yang, Y. Jiang, X. Huang, J. Wang: A region-based color image segmentation method under P systems. Romanian Journal of Information Science and Technology, 17(1), 63-75 (2014) Research Group of MC and Applications, Xihua University 35 22. J. Zhang, H. Peng, X. Huang, X. Gao: An image pixel clustering algorithm based on P systems, ICIC Express Letters, Part B: Applications, 6(7), 1813-1819 (2015) 23. Z. Zhang, H. Peng: Object segmentation with membrane computing, Journal of Information and Computational Science, 9(17), 5417-5424 (2012) 24. H. Wang, H. Peng, J. Shao: A thresholding method based on P systems for image segmentation, ICIC Express Letters, 6(1), 221-227 (2012) 25. H. Peng, J. Wang, M.J. P´erez-Jim´enez, P. Shi: A novel image thresholding method based on membrane computing and fuzzy entropy, Journal of Intelligent and Fuzzy Systems, 24(2), 229-237 (2013) 26. H. Peng, J. Wang, M.J. P´erez-Jim´enez: Optimal multilevel thresholding with membrane computing. Digital Signal Processing, 37, 53-64 (2015) 27. Z. Zhang, X. Yi, H. Peng: A novel framework of tissue membrane systems for image fusion. Bio-Medical Materials and Engineering, 24(6), 3259-3266 (2014) 28. H. Peng, J. Wang, M.J. P´erez-Jim´enez: The framework of P systems applied to solve optimal watermarking problem. Signal Processing, 101, 256-265 (2014) 29. J. Wang, P. Shi, H. Peng: Membrane computing model for IIR filter design. Information Sciences, 329, 164-176 (2016) 30. H. Peng, J. Wang: A hybrid approach based on tissue P systems and artificial bee colony for IIR system identification, Neural Computing and Applications, 2016. DOI: 10.1007/s00521-016-2201-3. 31. T. Liu, J. Wang, Z. Sun: An improved particle swarm optimization and its application for micro-grid economic operation optimization, Communications in Computer and Information Science, 472, 276-280 (2014) 32. Z. Sun, T. Liu, J. Wang, J. Liu, H. Li: An improved particle swarm optimization based on adaptive mutation and P systems for micro-grid economic operation, Proceedings of the 2015 Chinese Intelligent Automation Conference, Lecture Notes in Electrical Engineering, 336, 505-512 (2015) 33. J. Luo, J. Wang, P. Shi, H. Luo, Z. Sun, T. Liu: Micro-grid economic operation using genetic algorithm based on P systems, ICIC Express Letters, 9(2), 609-617 (2015) 34. M. Tu, J. Wang, X. Song: An artificial fish swarm algorithm based on P systems, ICIC Express Letters, Part B: Aplications, 4(3), 747-753 (2013) 35. M. Tu, J. Wang, F. Yang, J. Lu: Application of artificial fish swarm algorithm based on P systems in Economic load dispatch of power systems, ICIC Express Letters, 8(2), 409-414 (2014) 36. T. Wang, J. Wang, H. Peng: Optimization of PID controller parameters based on PSOPS algorithm, ICIC Express Letters, 6(1), 273-280 (2011) 37. J. Wang, T. Wang, P. Shi: Membrane optimization algorithm based on mutated PSO and its application in nonlinear control systems, International Journal of Innovative Computing, Information and Control, 9(7), 2963-2977 (2013) 38. K. Chen, J. Wang, Z. Sun: Programmable logic stage programming using spiking neural P systems, Journal of Computational and Theoretical Nanoscience, 12(7), 1292-1299 (2015) 39. K. Chen, J. Wang, Z. Sun, L. Juan, T. Liu: The application of spiking neural P systems for PLC programming, Communications in Computer and Information Science, 472, 11-15 (2014) 40. Y. Yang, J. Ming, J. Wang, H. Peng, Z. Sun, and Wenping Yu: The implementation of membrane clustering algorithm based on FPGA, ACMC2016, 2016. The Spanish Thematic Network on Biomolecular and Biocellular Computing Jos´e M. Sempere Departamento de Sistemas Inform´aticos y Computaci´on Universidad Polit´ecnica de Valencia, Spain [email protected] Summary. We describe the structure and main activities of the Spanish Thematic Network on Biomolecular and Biocellular Computing (Redbiocom). 1 The network and its research teams The Spanish Thematic Network on Biomolecular and Biocellular Computing, Redbiocom (http://www.redbiocom.es) was established in the year 2008, and, since then, it has been supported by different Spanish governments through different research supporting programs. It was first coordinated by Prof. Dr. Mario P´erez- Jim´enez (Univ. of Sevilla), and, currently, it is coordinated by Dr. Jos´e M. Sempere (Univ. Polit´ecnica de Valencia). Initially, the network was composed by the following Spanish research groups: •The Research Group of the Universidad Aut´onoma de Madrid (UAM) •The Research Group on Computational Biology and Bioinformatics of the Universitat de les Illes Balears (UIB) •The Research Group of the Universitat de Lleida (ULL) •The Natural Computing Research Group of the Universidad de Sevilla (US) •The Research Group on Natural Computing of the Universidad Polit´ecnica de Madrid (UPM-I) •The Research Group of the Artificial Intelligence Laboratory of the Universidad Polit´ecnica de Madrid (UPM-II) •The Research Group on Computational Models and Formal Languages of the Universidad Polit´ecnica de Valencia (UPV) Nowadays, the network has been slightly changed by removing the UAM team and by splitting the UPM-I group into two different groups. In the following, we overview the main activities of the current research groups. 38 J.M. Sempere The Research Group on Computational Biology and Bioinformatics at the Universitat de les Illes Balears (UIB) Group Coordinator: Francesc Rossell´o (email: [email protected]) The research group works in computational biology and bioinformatics. The main topics in which the group is currently working can be enumerated as follows: 1. Structural Bioinformatics 2. Philogenetic Trees and Networks 3. Biomolecular Networks Modeling 4. Biomolecular Processes Modeling In the last two topics the research group has used and explored membrane computing and computational chemistry as computational tools. The Research Group organized the Brainstorming Workshop on Uncertainty in Membrane Computing in 2004 in Palma de Mallorca. The Research Group at the Universitat de Lleida (ULL) Group Coordinator: M. Angels Colomer (email: [email protected]) The main research topics of the group are the following: 1. Ecosystems modeling through Population Dynamic P-systems. 2. Discrete Markov chains research through computational DNA and P systems. 3. Stochastic Modeling of rural problems. The Research Group on Natural Computing at the Universidad de Sevilla (US) Group Coordinator: Agust´ın Riscos-N´u˜nez (email: [email protected]) The Research Group on Natural Computing at the Universidad de Sevilla (RGNC) explores the interconnections between Computer Science, Engineering, Mathematics and Biology. The main research lines of the group are the following: 1. The development of specification languages for complex dynamic systems, specially in multicompartment systems for biological systems (from bacterial colonies to ecosystems). 2. The development of algorithms by formal semantics to simulate and integrate different space-time scales that appear in biological systems. 3. The implementation with high-performance computing of the previous algorithms in a framework of software development. 4. The design of models for systems and synthetic biology in the framework of cellular computing. The Spanish Thematic Network on Biomolecular and Biocellular Computing 39 5. The research on the theoretical aspects of non-conventional computing, specially with respect to its computational power and efficiency. The main achievements is the formulation of new characterizations of the conjecture P=NP. 6. Applications to various engineering areas, including engineering optimization, power system fault diagnosis, or the study of other complex systems involving data modeling and process interactions. The RGNC is one of the most referred groups in Membrane Computing. They have organized the Brainstorming Week on Membrane Computing since the year 2004. Two of the members of the group serve in the Program Committee and the Steering Committee of the International Conference on Membrane Computing (CMC). Additionally, Prof. Dr. Mario P´erez-Jim´enez (formerly, the RGNC coordinator) is the Awards Committee Chair of the IMCS, and Agust´ın Riscos-N´u˜nez is member of the IMCS Bulletin Committee. In 2014, the RGNC obtained the NVIDIA CUDA Research Center mention for the Universidad de Sevilla, and it was renewed in 2015. The Research Group on Natural Computing at the Universidad Polit´ecnica de Madrid (UPM-I) Group Coordinator: Juan Castellanos (email: [email protected]) The research group on Natural Computing at UPM, focuses its research activities in the following areas: 1. Genetic Algorithms and Evolutionary Computing. 2. Artificial Neural Networks. 3. Molecular Computing (DNA based computing). 4. Cellular Computing and Membrane Computing. The research group belongs to the European Molecular Computing Consortium (EMCC) and they organize the Natural Information Technologies conference (NIT) that is usually celebrated every year in Madrid. Some members of the group are members of the editorial committee of the International Journal Information, Theories and Applications (IJITA). The Research Group on Mathematical Models and Biocomputing Algorithms at the Universidad Polit´ecnica de Madrid (UPM-II) Group Coordinator: Fernando Arroyo (email: [email protected]) This research group was created in 2014, and its members were formerly members of the UPM-I group. The main research topics of the group are the same as the ones of the UPM-I group, together with a strong interest in Formal Languages and Networks of Bio-inspired Processors. 40 J.M. Sempere Research Group of the Artificial Intelligence Laboratory at the Universidad Polit´ecnica de Madrid (UPM-III) Group Coordinator: Alfonso Rodr´ıguez-Pat´on (email: [email protected]) The main research activities of this group are focused in biomolecular computing (DNA based computing) and bacterial computing. Additionally, the group works in membrane computing (P systems), specially in Spiking Neural P systems, and in Systems Biology. The Research Group on Computation Models and Formal Languages at the Universidad Polit´ecnica de Valencia (UPV) Group Coordinador: Jos´e M. Sempere (email: [email protected]) The research group at UPV works in theoretical aspects of Biomolecular and Membrane Computing (P systems), classical Automata Theory and Formal Languages, Grammatical Inference, and other non-conventional models of computation (such as Networks of Bio-inspired Processors). Some of the theoretical results have been applied to solve practical problems in biosequence processing, such as functional and structural protein prediction, and simulation of biological processes such as the recently developed ARES system to simulate the antibiotic resistance evolution that has been fully designed under the P systems paradigm. The members of the research group have organized some international events such as the ECAI 2004 Workshop on Symbolic Networks, the 10th International Colloquium on Grammatical Inference (ICGI 2010) and, more recently, the 16th Conference on Membrane Computing (CMC16) in 2015. One of its member, Jos´e M. Sempere is a member of the Steering Committee of the International Conference on Membrane Computing (CMC) and member of the IMCS Bulletin Committee. 2 Network activities The main activities of the network are oriented to promote the research activities of its research groups. In addition, it is a valuable instrument to establish collaborations between the groups to propose coordinated research projects in the national research programs and/or international projects with other foreign research groups. One of the main events that the network has organized is the International School on Biomolecular and Biocellular Computing (http://www.redbiocom. es/ISBBC.html). The first edition of ISBBC was held in Osuna (Sevilla) in 2011, while the second edition was organized in Madrid in 2013 co-located with the NIT 2013 Conference. Currently, the arrangements for the third edition have started and it will be held in June 2017, in Valencia. The school is a three days event for graduated and doctoral students where they can attend talks given by the most prominent researchers of the network together with international invited speakers. The Spanish Thematic Network on Biomolecular and Biocellular Computing 41 The talks are organized in the areas of Membrane Computing, Systems and Synthetic Biology, Networks of Bio-inspired Processors and Bioinformatics. All the students can apply for grants that cover all the expenses related to attending the school. Another goal of the network is to serve as a gateway for external collaborations between foreign research groups and the network groups. In this sense, any collaborative project that can involve more than one of the research groups of the network can be addressed to the network. Any question, proposal or additional information regarding the network can be addressed to Jos´e M. Sempere ([email protected]). 48 M. Gheorghe 7. M. Gheorghe, F. Ipate, S. Konur, Kernel P Systems and Relationships with other Classes of P Systems, in Multidisciplinary creativity – Homage to Gheorghe P˘aun on His 65th Birthday (M. Gheorghe et al., eds.), Spandugino Publishing House, 64 – 76, 2015. 8. M. Gheorghe, F. Ipate, R. Lefticaru, M.J. P´erez-Jim´enez, A. T¸urcanu, L. Valencia- Cabrera, M. Garc´ıa-Quismondo, L. Mierl˘a, 3-COL Problem Modelling Using Simple kernel P Systems, International Journal of Computer Mathematics, 90(4), 816 – 830, 2013. 9. M. Gheorghe, S. Konur, F. Ipate, Kernel P Systems and Stochastic P Systems for Modelling and Formal Verification of Genetic Logic Gates, in Advances in Unconventional Computing (A. Adamatzky, ed.), Emergence, Complexity and Computation Series, Volume 1: Theory, Springer, 661 – 676, 2015. 10. M. Gheorghe, S. Konur, F. Ipate, L. Mierl˘a, M. E. Bakir, M. Stannett, An Integrated Model Checking Toolset for Kernel P Systems, Proc. 16th Conference on Membrane Computing (G. Rozenberg et al., eds.), Lecture Notes in Computer Science, 9504, 153 – 170, 2015. 11. M. Gheorghe, Gh. P˘aun, M. J. P´erez-Jim´enez, G. Rozenberg, Research Frontiers of Membrane Computing: Open Problems and Research Topics, International Journal of Foundations of Computer Science, 24, 547 – 624, 2013. 12. F. Ipate, R. Lefticaru, L. Mierl˘a, L. Valencia-Cabrera, H. Han, G. Zhang, C. Dragomir, M. Gheorghe, Kernel P Systems: Applications and Implementations, Proc. 8th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA, 12 – 14 July, Huang Shan (Z. Yin et al., eds.), 1081 – 1089, 2013. 13. S. Konur, M. Gheorghe, C. Dragomir, L. Mierl˘a, F. Ipate, N. Krasnogor, Conventional Verification for Unconventional Computing: a Genetic XOR Gate Example, Fundamenta Informaticae, 134(1-2), 97 – 110, 2014. 14. S. Konur, M. Gheorghe, C. Dragomir, L. Mierl˘a, F. Ipate, N. Krasnogor, Qualitative and Quantitative Analysis of Systems and Synthetic Biology Constructs using P Systems, ACS Synthetic Biology, 4(1), 83 – 92, 2015. 15. S. N. Krishna, M. Gheorghe, C. Dragomir, Some Classes of Generalised Communicating P Systems and Simple Kernel P Systems, Proc. 9th International Conference on Computability in Europe, 1 – 5 July, Milan (P. Bonizzoni et al., eds.), 284 – 293, 2013. 16. R. Lefticaru, L. F. Mac´ıas-Ramos, I. M. Niculescu, L. Mierl˘a, Towards Agent- Based Simulation of Kernel P Systems using FLAME and FLAME GPU, Proc. Workshop on Membrane Computing, Manchester, 11 – 15 July, 2016 (M. Gheorghe, S. Konur, eds.), Technical Report of the University of Bradford, 58 – 61, 2016. 17. R. Lefticaru, L. F. Mac´ıas-Ramos, I. M. Niculescu, L. Mierl˘a, Agent-Based Simulation of Kernel P Systems with Division Rules using FLAME, Proc. 17th International Conference on Membrane Computing, Milan, 25 – 29 July, 2016 (A. Leporati, C. Zandron, eds.), 195 – 216, 2016. 18. I. M. Niculescu, M. Gheorghe, F. Ipate, A. S¸ef˘anescu, From Kernel P Systems to X-Machines and FLAME, Journal of Automata, Languages and Combinatorics, 19(1–4), 239 – 250, 2014. PhD Theses in Membrane Computing The following theses were totally or only partially dedicated to membrane computing. The list is mainly compiled from the bibliography given at http://ppage.psystems.eu, with some updates provided by Spain, Italy and, especially, China groups. There also are several theses in preparation at this moment. For sure, the list is not complete. We hope to make it as complete as possible in a future version. 1. O. Agrigoroaiei: Causality and Coordination in Interaction-Based Systems, Romanian Academy, Ia¸si branch, Romania, 2012. 2. A. Alhazov: Communication in Membrane Systems with Symbol Objects, Tarragona University, Tarragona, Spain, 2006. 3. A. Alhazov: Habilitation thesis: Small Abstract Computers, Academy of Sciences of Moldova, Chi¸sin˘au, Republic of Moldova, 2013. 4. B. Aman: Spatial Dynamic Structures and Mobility in Computation, Romanian Academy, Ia¸si branch, Romania, 2009. 5. F. Arroyo-Montoro: Structures and Biolanguage to Simulate Membrane Computing, Madrid University, Madrid, Spain, 2004. 6. A. Arteta: New Techniques for Implementing Membrane Systems, Technical University of Madrid, Madrid, Spain, 2010. 7. F. Bernardini: Membrane Systems for Molecular Computing and Biological Modelling, University of Sheffield, Sheffield, UK, 2005. 8. D. Besozzi: Computational and Modelling Power of P Systems, University of Milan-Bicocca, Milano, Italy, 2003. 9. L. Bianco: Membrane Models of Biological Systems, Verona University, Verona, Italy, 2007. 10. C. Bonchi¸s: Arithmetics and Information Theory in Membrane Computing, West University, Timi¸soara, Romania, 2009. 11. R. Brijder: Models of Natural Computation: Gene Assembly and Membrane Systems, Leiden University, Leiden, The Netherlands, 2008. 50 PhD Theses in Membrane Computing 12. R. Castellini: Algorithms and Software for Biological MP Modeling by Statistical and Optimization Techniques, Verona University, Verona, Italy, 2010. 13. M. Cavaliere: Evolution, Communication and Observation: From Biology to Membrane Computing and Back, Universidad de Sevilla, Seville, Spain, 2006. 14. P. Cazzaniga: Stochastic Algorithms for Biochemical Processes, Verona University, Verona, Italy, 2009. 15. H. Chen: Research on Applications on Membrane Computing, Chongqing University, Chongqing, China, 2011. 16. Y. Chen: Formal Modeling and Simulation of Train Flow Based on High Confidence Wireless Communication, Lanzhou Jiaotong Univ., China, 2014. 17. J. Cheng: Autonomous Differential Evolution Algorithm: Design and Application, Southwest Jiaotong Univ., China, 2015. 18. L. Ciencialov´a: P Kolonie (in Czech), Opava University, Opava, Czech Republic, 2008. 19. C. Dragomir: 20. D. Diaz-Pernil: Sistemas Celulares de Tejidos: Formalizaci´on y Eficiencia Computacional, Universidad de Sevilla, Seville, Spain, 2008. 21. I. Dinc˘a: Modelling and Specification of Parallel and Distributed Systems, University of Pite¸sti, Pite¸sti, Romania, 2011. 22. G. Franco: Biomolecular Computing – Combinatorial Algorithms and Laboratory Experiments, Universit`a degli Studi di Verona, Italy, 2006. 23. P. Frisco: Theory of Molecular Computing. Splicing and Membrane Systems, Leiden University, Leiden, The Netherlands, 2004. 24. M. Garcia-Quismondo-Fernandez: Modelling and Simulation of Real-Life Phenomena in Membrane Computing, Universidad de Sevilla, Seville, Spain, 2014. 25. C. Graciani-Diaz: Especificacin y Verificaci´on de Programas Moleculares en PVS, Universidad de Sevilla, Seville, Spain, 2003. 26. J. He: Research on Membrane-Inspired Algorithms and Applications, Huazhong University of Science and Technology, Wuhan, China, 2014. 27. S. Hemalatha, A Study on Rewriting P Systems, Splicing Grammar Systems and Picture Array Languages, Anna University, Chennai, India, 2007. 28. L. Hu: Research on Fault Knowledge Evolution Technologies of Human- Machine Synergy Diagnosis for CNC Machine Tools, Chongqing Univ., China, 2015. 29. L. Huang: Research on Membrane Computing Optimization Methods, Zhejiang University, Hangzhou, China, 2007. 30. A.M. Ionescu: Membrane Computing: Traces, Neural Inspired Models, Controls, Tarragona University, Spain, 2008. 31. T. Isdorj-Onolt: Membrane Computing, Neural Inspirations, Gene Assembly in Ciliates, Universidad de Sevilla, Seville, Spain, 2007. 32. C. Izba¸sa: Information Theory and Computation over Multisets, West University, Timi¸soara, Romania, 2010. 33. J.R. Jack: Discrete Nondeterministic Modeling of Biochemical Networks, Louisiana Technical University, Ruston, USA, 2009. PhD Theses in Membrane Computing 51 34. Y. Jiang: Research on the Computational Power of P Systems with Network Structure, Huazhong University of Science and Technology, Wuhan, China, 2011. 35. K. Jiang: Research on Sequential Spiking Neural P Systems Based on Spike Number, Huazhong University of Science and Technology, Wuhan, China, 2014. 36. Y.-B. Kim: Distributed Algorithms in Membrane Systems, The University of Auckland, Auckland, New Zealand, 2012. 37. Y. Kong: Research on the Computational Power of Spiking Neural P Systems with Differential Biological Backgrounds, Huazhong University of Science and Technology, Wuhan, China, 2015. 38. S.N. Krishna: Languages of P Systems: Computability and Complexity, University of Madras, Chennai, India, 2001. 39. L. Lakshmanan: On the Crossroads of P Systems and Contextual Grammars: Variants, Computability, Complexity and Efficiency, Indian Institute of Technology, Madras, India, 2003. 40. R. Lefticaru: Testing Methods Based on Formal Specifications, University of Pite¸sti, Romania, 2011. 41. C. Liu: Research on Optimization Methods of Cell-Like Membrane Computing and Their Applications, Dalian University of Technology, Dalian, China, 2014. 42. R. Lombardo: Unconventional Computations and Genome Representations, Verona University, Italy, 2016. 43. C. Lu: Research on Computational Properties of Membrane Systems with Proteins, Huazhong University of Science and Technology, Wuhan, China, 2012. 44. L.F. Mac´ıas-Ramos: Developing efficient simulators for cell machines, Universidad de Sevilla, Seville, Spain, 2016 45. M. Madhu: Studies of P Systems as a Model of Cellular Computing, Indian Institute of Technology, Madras, India, 2003. 46. L. Marchetti: MP representations of Biological Structures and Dynamics, Universit`a di Verona, Verona, Italy, 2012. 47. M.A. Martinez-del-Amor: Accelerating Membrane Systems Simulators Using High Performance Computing with GPU, Universidad de Sevilla, Seville, Spain, 2013. 48. V.P. Metta: Modelling and Simulation of Spiking Neural P systems Using Petri Nets, Thapar University, Patiala, Indian, 2012. 49. P. Milazzo: Qualitative and Quantitative Formal Modeling of Biological Systems, Pisa University, Pisa, Italy, 2006. 50. Y. Niu: Research on Models and Algorithms of Membrane Computing for Solving Computational Intractable Problems, Huazhong University of Science and Technology, Wuhan, China, 2012. 51. M. Oswald: P Automata, Vienna University of Technology, Wien, Austria, 2004. 52. R. Pagliarini: Modelling and Reverse-Engineering of Biological Phenomena by Means of Metabolic P Systems, Verona University, Verona, Italy, 2011. 52 PhD Theses in Membrane Computing 53. A. P˘aun: Unconventional Models of Computation: DNA and Membrane Computing, Western University, London, Canada, 2003. 54. A.B. Pavel: Development of Robot Controllers Using Membrane Computing, Politechnica University, Bucharest, Romania, 2015. 55. X. Peng: Research on Computational Power and Applications of Spiking Neural P Systems, Central South University, Changsha, China, 2013. 56. I. P´erez-Hurtado de Mendoza: Desarrollo y Aplicaciones de un Entorno de Programaci´on para Computaci´on Celular: P-Lingua, Universidad de Sevilla, Seville, Spain, 2010. 57. D. Pescini: Modelling, Analysis and Stochastic Simulations of Biological Systems, University of Milano-Bicocca, Milano, Italy, 2007. 58. B. Popa: Membrane Systems with Limited Parallelism, Louisiana Technical University, Ruston, USA, 2006. 59. A.E. Porreca: The Time-Space Trade-Off in Membrane Computing, Milano Bicocca University, Italy, 2012. 60. A. Ramanujan: Control Languages in P Systems, Indian Institute of Technology Madras, Chennai, Indian, 2014. 61. A. Riscos-N´u˜nez: Programaci´on Celular: Resoluci´on Eficiente de Problemas Num´ericos NP-completos, Universidad de Sevilla, Seville, Spain, 2004. 62. F. Romero-Campero: P Systems: A Computational Modelling Framework for Systems Biology, Universidad de Sevilla, Seville, Spain, 2008. 63. ´ A. Romero-Jim´nez: Complejidad y Universalidad en Modelos de Computaci ´ On Celular, Universidad de Sevilla, Seville, Spain, 2002. 64. F. Sancho-Caparrini: Verificaci´on de Programas en Modelos de Computaci´on no Convencionales, Universidad de Sevilla, Seville, Spain, 2002. 65. D. Sburlan: Promoting and Inhibiting Contexts in Membrane Computing, Universidad de Sevilla, Seville, Spain, 2006. 66. T. Song: Research on Computational Properties and Applications of Spiking Neural P Systems, Huazhong University of Science and Technology, Wuhan, China, 2013. 67. B. Song: Research on Computational Property of Timed Membrane Systems, Huazhong University of Science and Technology, Wuhan, China, 2015. 68. I. Stamatopoulou: A Formal Framework for the Modelling of Multi-Agent Systems with Dynamic Structure, University of Thessaloniki, Thessalonica, Greece, 2008. 69. Y. Sun: Process Modeling and Operation Optimization Methods for Coal Water Slurry Gasification Unit, East China University of Science and Technology, 2012. 70. C. S¸tefan: Parallel and Distributed Communication Systems: A Formal Approach, University of Pite¸sti, Romania, 2012. 71. A. T¸urcanu: Modelling, Testing and Verification of Biology Inspired Systems, University of Pite¸sti, Pite¸sti, Romania, 2013. PhD Theses in Membrane Computing 53 72. L. Valencia-Cabrera: An Environment for Virtual Experimentation with Computational Models Based on P Systems, Universidad de Sevilla, Seville, Spain, 2015. 73. C.-I. Vasile: Distributed Control for Multi-Robot Systems, Politechnica University, Bucharest, Romania, 2015. 74. C. Vasilica Ferent: Methodologies for Specification and Validation of Software Systems, ???, 2011. 75. J. Wang: Spiking Neural P Systems, Leiden University, Leiden, The Netherlands, 2011. 76. J. Wang: Computational Power of Spiking Neural Membrane Systems Inspired by Neural Systems, Huazhong University of Science and Technology, Wuhan, China, 2013. 77. H. Wu: P Systems as Formal Models for Distributed Algorithms, The University of Auckland, Auckland, New Zealand, 2014. 78. J. Xiao: The Research on Bio-Inspired Encoding Algorithms for DNA Computing, Huazhong Univ. of Science and Technology, Wuhan, China, 2008. 79. G. Xiong: Research on Methods for Fault Diagnosis of Power Grids Based on Computational Intelligence, Huazhong Univ. of Science and Technology, China, 2014. 80. W. Xiong: Research on Traffic Assignment Model Considering Emission Effects and Solution Algorithm, Wuhan University of Technology, Wuhan, China, 2009. 81. J. Xue: Two Classes of Biological Computing and Applications in Data Mining, Shandong Normal University, Ji’nan, China, 2015. 82. S. Yang: Research on P systems Based Optimization Algorithms and Applications, Zhejiang University, Hangzhou, China, 2012. 83. C. Zandron: A Model for Molecular Computing: Membrane Systems, University of Milano-Bicocca, Milano, Italy, 2001. 84. X. Zeng: Research on Computational Property of Spiking Neural P Systems, Huazhong University of Science and Technology, Wuhan, China, 2011. 85. X. Zhang: Research on the Computational Power of Spiking Neural P Systems, Huazhong University of Science and Technology, Wuhan, China, 2009. 86. J. Zhao: Research on Bio-inspired Optimization Algorithms Based on Membrane Computing and Applications, Zhejiang University, Hangzhou, China, 2010. It might be instructive to also have a view of the evolution of the number of PhD theses presented in each year (the increasing tendency of the last years is obvious – for sure, a consequence of the interest for MC in China): 54 PhD Theses in Membrane Computing 2001 2 2009 6 2002 2 2010 5 2003 5 2011 8 2004 4 2012 10 2005 1 2013 6 2006 6 2014 8 2007 5 2015 8 2008 7 2016 3? Membrane Computing 16th International Conference, CMC 2015 Valencia, Spain, August 17-21, 2015 Revised Selected Papers LNCS 9504, Springer-Verlag, Berlin, 2015 Grzegorz Rozenberg, Arto Salomaa, Jos´e M. Sempere, Claudio Zandon, editors Preface The present volume contains the invited contributions and a selection of papers presented at the 16th International Conference on Membrane Computing (CMC16), that was held in Valencia, Spain, 17-21 August, 2015 (website address: http://users.dsic.upv.es/workshops/cmc16/), as well as three selected papers from the Asian Conference on Membrane Computing (ACMC) 2015, held in Anhui University, Hefei, Anhui, China, 12-15 November, 2015 (website address: http://2015.asiancmc.org/). The CMC series started with three workshops organized in Curtea de Arge¸s, Romania, in 2000, 2001 and 2002. The workshops were then held in Tarragona, Spain (2003), Milan, Italy (2004), Vienna, Austria (2005), Leiden, The Netherlands (2006), Thessaloniki, Greece (2007), and Edinburgh, UK (2008). The 10th edition was organized again in Curtea de Arge¸s, in August 2009, where it was decided to continue the series as the Conference on Membrane Computing (CMC). The following editions were held in Jena, Germany (2010), Fontainebleau, France (2011), Budapest, Hungary (2012), Chi¸sin˘au, Moldova (2013), and Praha, Czech Republic (2014). A regional version of CMC, the Asian Conference on Membrane Computing, ACMC, started in 2012 in Wuhan (China), and continued in Chengdu, China (2013) and Coimbatore, India (2014). CMC16 has been organized, under the auspices of the European Molecular Computing Consortium (EMCC), by the Research Group on Computation Models and Formal Languages of the Universitat Polit`ecnica de Val`encia and it was supported by the Escuela T´ecnica de Ingenier´ıa Inform´atica (ETSINF, UPV). CMC16 consisted of three different parts: the first day was organized as a Tutorial Day, with lectures by Gheorghe P˘aun, Rudolf Freund, Claudio Zandron, Gyorgy Vaszil, and Agust´ın Riscos-N´u˜nez. From Tuesday to Thursday the con- 56 CMC 2015, Valencia, Spain, LNCS 9504 ference continued with standard sessions; invited lectures were given by Ion Petre (Abo Akademi University, Finland), Andr´es Moya (Universitat de Val`encia, Spain) and Vincenzo Manca (University of Verona, Italy). The last day of the conference was devoted to presentation of extended abstracts and interaction between participants. Based on the votes of the CMC16 participants, the Best Paper Award of this edition was given to Rudolf Freund and Petr Sos´ık for their paper “On the Power of Catalytic P Systems with One Catalyst”. The editors express their gratitude to the Program Committee, the invited speakers, the authors of the papers, the reviewers, and all the participants for their contributions to the success of CMC16. November 2015 Grzegorz Rozenberg Arto Salomaa Jos´e M. Sempere Claudio Zandron The Steering Committee of the CMC series consisted of Artiom Alhazov (Chi¸sin˘au, Moldova) Bogdan Aman (Ia¸si, Romania) Matteo Cavaliere (Edinburgh, Scotland) Erzs´ebet Csuhaj-Varj´u (Budapest, Hungary) Rudolf Freund (Wien, Austria) Thomas Hinze (Cottbus, Germany) Marian Gheorghe (Bradford, UK) – Honorary Member Florentin Ipate (Bucharest, Romania) Alberto Leporati (Milan, Italy) Linqiang Pan (Wuhan, China) Gheorghe P˘aun (Bucharest, Romania and Sevilla, Spain) - Honorary Member Agust´ın Riscos-N´u˜nez (Sevilla, Spain) Petr Sosik (Opava, Czech Republic) Gyorgy Vaszil (Debrecen, Hungary) Sergey Verlan (Paris, France) Claudio Zandron (Milan, Italy) – Chair The Organizing Committee of CMC16 consisted of Marcelino Campos (Valencia, Spain) Guillem Pitarch (Valencia, Spain) Mar´ıa Sambl´as (Valencia, Spain) Jos´e M. Sempere (Valencia, Spain) – Co-chair Claudio Zandron (Milan, Italy) – Co-chair CMC 2015, Valencia, Spain, LNCS 9504 57 The Programme Committee of CMC16 consisted of Artiom Alhazov (Chi¸sin˘au, Moldova) Matteo Cavaliere (Edinburgh, Scotland) Ludek Cienciala (Opava, Czech Republic) Gabriel Ciobanu (Ia¸si, Romania) Erzs´ebet Csuhaj-Varj´u (Budapest, Hungary) Giuditta Franco (Verona, Italy) Rudolf Freund (Wien, Austria) Marian Gheorghe (Bradford, UK) Thomas Hinze (Cottbus, Germany) Florentin Ipate (Bucharest, Romania) Shankara Narayanan Krishna (Bombay, India) Alberto Leporati (Milan, Italy) Vincenzo Manca (Verona, Italy) Maurice Margenstern (Metz, France) Giancarlo Mauri (Milan, Italy) Radu Nicolescu (Auckland, New Zealand) Linqiang Pan (Wuhan, China) Gheorghe P˘aun (Bucharest, Romania and Sevilla, Spain) Mario de Jes´us P´erez Jim´enez (Sevilla, Spain) Dario Pescini (Milan, Italy) Agust´ın Riscos-N´u˜nez (Sevilla, Spain) Jos´e M. Sempere (Valencia, Spain) – Co-chair Petr Sos´ık (Opava, Czech Republic) Gyorgy Vaszil (Debrecen, Hungary) Sergey Verlan (Paris, France) Claudio Zandron (Milan, Italy) – Co-chair Gexiang Zhang (Chengdu, Sichuan, China) Additonal reviewers: Bogdan Aman (Ia¸si, Romania) Raluca Lefticaru (Bucharest, Romania) Alin Stefanescu (Bucharest, Romania) ´ Alvaro Romero Jim´enez (Sevilla, Spain) Andrei Alexandru (Ia¸si, Romania) Miguel ´ A. Mart´ınez-Del-Amor (Sevilla, Spain) 64 A. Adamatzky and reservoir computing. As a dessert we have two vibrant memoirs by founding fathers of the field. The second volume is a tasty blend of experimental laboratory results, modelling and applied computing. Emergent molecular computing is presented by enzymatic logical gates and circuits, and DNA nano-devices. Reaction-diffusion chemical computing is exemplified by logical circuits in BelousovZhabotinsky medium and geometrical computation in precipitating chemical reactions. Logical circuits realised with solitons and impulses in polymer chains show advances in collisionbased computing. Photo-chemical and memristive devices give us a glimpse into the hot topics of novel hardware. Practical computing is represented by algorithms of collective and immune-computing and nature-inspired optimisation. Living computing devices are implemented in real and simulated cells, regenerating organisms, plant roots and slime moulds. Musical biocomputing and living architectures make the ending of our unconventional journey non-standard. The chapters are self-contained. No background knowledge is required to enjoy the book. Each chapter is a treatise of marvellous ideas. Volume 1 (ISBN-13: 978-3319339238) 1. Selim G. Akl: Nonuniversality in Computation: Fifteen Misconceptions Rectified 2. Vladik Kreinovich and Olga Kosheleva: What Is Computable? What Is Feasibly Computable? A Physicists Viewpoint 3. Norman Margolus: The Ideal Energy of Classical Lattice Dynamics 4. Tania Ambaram, Edwin Beggs, Jose Felix Costa, Diogo Pocas and John V. Tucker: An Analogue-Digital Model of Computation: Turing Machines with Physical Oracles 5. Bruce J. MacLennan: Physical and Formal Aspects of Computation: Exploiting Physics for Computation and Exploiting Computation for Physical Purposes 6. Jerome Durand-Lose: Computing in Perfect Euclidean Frameworks 7. Ed Blakey: Unconventional Computers and Unconventional Complexity Measures 8. Mark Burgin: Decreasing Complexity in Inductive Computations 9. Hector Zenil and J¨urgen Riedel: Asymptotic Intrinsic Universality and Natural Reprogrammability by Behavioural Emulation 10. Kenichi Morita: Two Small Universal Reversible Turing Machines 11. Dmitry I. Iudin and Yaroslav D. Sergeyev: Percolation Transition and Related Phenomena in Terms of Grossone Infinity Computations 12. Tommaso Bolognesi: Spacetime Computing: Towards Algorithmic Causal Sets with Special-Relativistic Properties 13. Antoine Spicher and Jean-Louis Giavitto: Interaction-Based Programming in MGS 14. Maurice Margenstern: Cellular Automata in Hyperbolic Spaces Advances in Unconventional Computing 65 15. Genaro J. Martinez, Andrew Adamatzky, and Harold V. McIntosh: A Computation in a Cellular Automaton Collider Rule 110 16. Karl Svozil: Quantum Queries Associated with Equi-partitioning of States and Multipartite Relational Encoding Across Space-Time 17. Cristian S. Calude and Michael J. Dinneen: Solving the Broadcast Time Problem Using a D-wave Quantum Computer 18. Alexis De Vos and Stijn De Baerdemacker: The Group Zoo of Classical Reversible Computing and Quantum Computing 19. Martin Lukac, Michitaka Kameyama, Marek Perkowski, Pawel Kerntopf, and Claudio Moraga: Fault Models in Reversible and Quantum Circuits 20. Hiroshi Umeo: A Class of Non-optimum-time FSSP Algorithms 21. Jia Lee: Universality of Asynchronous Circuits Composed of Locally Reversible Elements 22. Matthew Dale, Julian F. Miller, and Susan Stepney: Reservoir Computing as a Model for In-Materio Computing 23. Zoran Konkoli: On Reservoir Computing: From Mathematical Foundations to Unconventional Applications 24. Paolo Dini: Computational Properties of Cell Regulatory Pathways Through Petri Nets 25. Marian Gheorghe, Savas Konur, and Florentin Ipate: Kernel P Systems and Stochastic P Systems for Modelling and Formal Verification of Genetic Logic Gates 26. Erik Bergh and Zoran Konkoli: On Improving the Expressive Power of Chemical Computation 27. Andrew Schumann: Conventional and Unconventional Approaches to Swarm Logic 28. Christopher Bennett, Aldo Jesorka, Goran Wendin, and Zoran Konkoli: On the Inverse Pattern Recognition Problem in the Context of the Time-Series Data Processing with Memristor Networks 29. Nicholas J. Macias and Lisa J.K. Durbeck: Self-Awareness in Digital Systems: Augmenting Self-Modification with Introspection to Create Adaptive, Responsive Circuitry 30. Gheorghe P˘aun: Looking for Computers in the Biological Cell. After Twenty Years 31. Cristian S. Calude: Unconventional Computing: A Brief Subjective History Volume 2 (ISBN-13: 978-3319339207) 1. Matthew R. Lakin, Milan N. Stojanovic, and Darko Stefanovic: Implementing Molecular Logic Gates, Circuits, and Cascades Using DNAzymes 2. Evgeny Katz and Brian E. Fratto: Enzyme-Based Reversible Logic Gates Operated in Flow Cells 3. Sergii Domanskyi and Vladimir Privman: Modeling and Modifying Response of Biochemical Processes for Biocomputing and Biosensing Signal Processing 66 A. Adamatzky 4. Jerzy Gorecki, Joanna N. Gorecka, Bogdan Nowakowski, Hiroshi Ueno, Tatsuaki Tsuruyama, and Kenichi Yoshikawa: Sensing Parameters of a Time Dependent Inflow with an Enzymatic Reaction 5. Mingzhu Sun and Xin Zhao: Combinational Logic Circuit Based on BZ Reaction 6. James Stovold and Simon OKeefe: Associative Memory in Reaction-Diffusion Chemistry 7. Ben De Lacy Costello and Andrew Adamatzky: Calculating Voronoi Diagrams Using Chemical Reactions 8. Larry Bull, Rita Toth, Chris Stone, Ben De Lacy Costello, and Andrew Adamatzky: Light-Sensitive BelousovZhabotinsky Computing Through Simulated Evolution 9. Ivan Zelinka: On Synthesis and Solutions of Nonlinear Differential Equations – A Bio-Inspired Approach 10. Kohta Suzuno, Daishin Ueyama, Michal Branicki, Rita Toth, Artur Braun, and Istvan Lagzi: Marangoni Flow Driven Maze Solving 11. Jitka Cejkova, Silvia Holler, To Quyen Nguyenova, Christian Kerrigan, Frantisek Stepanek, and Martin M. Hanczyc: Chemotaxis and Chemokinesis of Living and Non-living Objects 12. Mariusz H. Jakubowski, Ken Steiglitz, and Richard Squier: Computing with Classical Soliton Collisions 13. Ken Steiglitz: Soliton-Guided Quantum Information Processing 14. Stefano Siccardi and Andrew Adamatzky: Models of Computing on Actin Filaments 15. Reem Mokhtar, Sudhanshu Garg, Harish Chandran, Hieu Bui, Tianqi Song, and John Reif: Modeling DNA Nanodevices Using Graph Rewrite Systems 16. Hajo Broersma, Julian F. Miller, and Stefano Nichele: Computational Matter: Evolving Computational Functions in Nanoscale Materials 17. Kacper Pilarczyk, Przemyslaw Kwolek, Agnieszka Podborska, Sylwia Gaweda, Marek Oszajca, and Konrad Szacilowski: Unconventional Computing Realized with Hybrid Materials Exhibiting the PhotoElectrochemical Photocurrent Switching (PEPS) Effect 18. Silvia Battistoni, Alice Dimonte, and Victor Erokhin: Organic Memristor Based Elements for Bio-inspired Computing 19. Ella Gale: Memristors in Unconventional Computing: How a Biomimetic Circuit Element Can be Used to Do Bioinspired Computation 20. Xin-She Yang: Nature-Inspired Computation: An Unconventional Approach to Optimization 21. Jeff Jones: On Hybrid Classical and Unconventional Computing for Guiding Collective Movement 22. Nikolaos P. Bitsakidis, Nikolaos I. Dourvas, Savvas A. Chatzichristofis, and Georgios Ch. Sirakoulis: Cellular Automata Ants 23. Krzysztof Pancerz and Andrew Schumann: Rough Set Description of Strategy Games on Physarum Machines Advances in Unconventional Computing 67 24. Daniel Lobo and Michael Levin: Computing a Worm: Reverse-Engineering Planarian Regeneration 25. Savas Konur, Harold Fellermann, Larent¸iu Marian Mierl˘a, Daven Sanassy, Christophe Ladroue, Sara Kalvala, Marian Gheorghe, and Natalio Krasnogor: An Integrated In Silico Simulation and Biomatter Compilation Approach to Cellular Computation 26. Ken Yokawa and Frantiˇsek Baluska: Plant Roots as Excellent Pathfinders: Root Navigation Based on Plant Specific Sensory Systems and Sensorimotor Circuits 27. B. Mazzolai, V. Mattoli, and L. Beccai: Soft Plant Robotic Solutions: Biological Inspiration and Technological Challenges 28. Andrew Adamatzky: Thirty Seven Things to Do with Live Slime Mould 29. Eduardo Reck Miranda and Edward Braund: Experiments in Musical Biocomputing: Towards New Kinds of Processors for Audio and Music 30. Alexander O. Tarakanov and Alla V. Borisova: Immunocomputing and Baltic Indicator of Global Warming 31. Rachel Armstrong: Experimental Architecture and Unconventional Computing Tutorials, Surveys Complexity Perspectives on Minimal Cooperation in Cell-like Membrane Systems Luis Valencia-Cabrera, David Orellana-Mart´ın, Agust´ın Riscos-N´u˜nez, Mario J. P´erez-Jim´enez Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: [email protected],[email protected],[email protected],[email protected] Summary. Cooperation is doubtless a critical ingredient of a computing model. This paper provides an overview on results showing how forbidding cooperation, or allowing it only a minimum degree, influences the computing power. In particular, we restrict ourselves to two types of cell-like membrane systems. On one hand, we analyze the efficiency of polarizationless P systems with active membranes without dissolution rules when minimal cooperation is permitted in object evolution rules. On the other hand, cell-like P systems with symport/antiport rules of minimal length are also addressed. Specifically, assuming that Pis not equal to NP, several frontiers of the efficiency are obtained in these two frameworks. 1 Introduction The dynamics of cell-like membrane systems is captured by means of rewriting rules that allow the evolution of objects. Any object, alone or together with one more object can be transformed into other objects, can pass through one membrane and can dissolve/divide/separate the membrane where it currently resides [8]. Noncooperative systems only contain rules abstracting proteins that transport only one solute across the membrane (for example, the glucose transporter in red blood cell membranes). P systems with active membranes [9] is an interesting particular case of noncooperative system. In the first version of these systems, electrical charges from the set {+,−,0}are associated with membranes. Besides, a rule associated with a 70 L. Valencia-Cabrera et al. membrane labelled by his applicable to a configuration if the object corresponding to its left-hand side is in membrane hof that configuration, and the membrane has a polarization prefixed in the rule. Thus, in some sense, there exists a kind of cooperation/collaboration in order to trigger the rule. A particular case of cooperative systems are the cell-like P systems with symport/antiport rules [7] where there exist rules with the length at least two. In these systems, communication is implemented by means of symport/antiport rules abstracting trans-membrane transport of couples of chemical substances, in the same or in opposite directions. As it is stated by the so-called Milano theorem [17], no computationally hard problems can be solved in polynomial time without using rules allowing the generation of an exponential number of membranes/cells in polynomial time, unless P=NP holds. So, in order to achieve efficiency (the ability to provide polynomialtime solution to computationally hard problems), division rules abstracting the cell division process and separation rules abstracting the membrane fission process are also included. It is worth pointing out that dissolution rules and division rules for nonelementary membranes are not necessary/relevant to get the computational efficiency in (non-cooperative) P systems with active membranes. Nevertheless, if electrical charges are forbidden, then dissolution rules start to play a relevant role in these systems from a computational complexity point of view. The reason is that only problems in class Pcan be efficiently solved by means of families of such systems without dissolution rules, even in the case that division rules for non-elementary membranes are allowed [3]. The situation is similar for cell-like P systems with symport/antiport rules where only a single object is involved in any rule (so, only symport rules with length 1 are permitted). The main goal of this work is to present recent results concerning the computational efficiency of both polarizationless P systems with active membranes and cell-like P systems with symport/antiport rules when minimal cooperation is considered. The term “minimal cooperation” is used in the following sense: in the first case, the left-hand side of each rule has at most a couple of objects; in the second case, at most two objects are involved in each communication (symport/antiport) rule. 2 The computational frameworks 2.1 Polarizationless P systems with active membranes A polarizationless P system with active membranes (Γ, H, µ, M1,...,Mq,R, iout) of degree q, can be viewed as a set of qmembranes, labelled by elements of H, arranged in a hierarchical structure µgiven by a rooted tree, such that: (a) M1, . . . , Mqrepresent the finite multisets of objects initially placed in the qmembranes of the system; (b) Ris a finite set of rules over Γassociated with the labels; (c) iout ∈H∪ {env}indicates the output region. The leaves of µare called Complexity Perspectives on Minimal Cooperation 71 elementary membranes; any other membrane is said to be non-elementary. The semantics of polarizationless P systems with active membranes is defined as usual P systems with active membranes (see [4, 9] for details). A new kind of models can be considered when separation rules, inspired by the membrane fission process, are used instead of division rules as a mechanism to produce an exponential number of membranes in linear time. These rules are associated with a (prefixed) partition {Γ0, Γ1}of the working alphabet Γand a (prefixed) partition {H0, H1}of the set of labels H. •Separation for elementary membranes: [ a]h→[Γ0]h[Γ1]hfor h∈H\ {iout}, a∈Γand his not the label of the root of µ. •Separation for non-elementary membranes: [[ ]h0[ ]h1]h→[Γ0[ ]h0]h[Γ1[ ]h1]h, where h∈H\ {iout}is not the label of the root of µ,h0∈H0and h1∈H1. A separation rule [ a]h→[Γ0]h[Γ1]his applicable to a configuration Ctat an instant t, if there exists a membrane labelled by hin Ctsuch that it is an elementary membrane in Ctand contains object a. When applying such a rule, the membrane is separated into two membranes with the same label; at the same time, object ais consumed and the multiset of objects contained in membrane h gets distributed: the objects from Γ0are placed in one membrane, those from Γ1 are placed in another. A separation rule [ [ ]h0[ ]h1]h→[Γ0[ ]h0]h[Γ1[ ]h1]his applicable to a configuration Ctat an instant t, if there exists a membrane labelled by hin Ct such that it contains a membrane labelled by h0and another membrane labelled by h1. When applying such a separation rule to a membrane labelled by hin Ct, that membrane is separated into two membranes with the same label, in such a way that the contents (objects and inner membranes) are distributed as follows: The first membrane receives the objects from Γ0, and all inner membranes whose label belongs to H0; while the second membrane receives the objects from Γ1, and all inner membranes whose label belongs to H1. Minimal cooperation in object evolution rules Next, minimal cooperation in objects evolution rules is introduced in the framework of polarizationless P systems with active membranes. The term “minimal cooperation” is used in the following sense: the left-hand side of such rules consists of two symbols. Definition 1. In the context of polarizationless P systems with active membranes, the following kinds of minimal cooperation in object evolution rules are considered. •Primary minimal cooperation (pmc): object evolution rules are of the form [u→v]h, where h∈H,u, v are multisets over Γ, and 1≤ |u|,|v| ≤ 2, but at least one object evolution rule verifies |u|= 2. 72 L. Valencia-Cabrera et al. •Bounded minimal cooperation (bmc): object evolution rules are of the form [u→v]h, where h∈H,u, v are multisets over Γ, and 1≤ |v| ≤ |u| ≤ 2, but at least one object evolution rule verifies |u|= 2. •Minimal cooperation and minimal production (mcmp): object evolution rules are of the form [a→b]h,[a b →c]h, for h∈Hand a, b, c ∈Γ, but at least one object evolution rule is of the second type. We denote by DAM0(α, β, γ, δ) (respectively, SAM0(α, β, γ, δ)) the class of all polarizationless P systems with active membranes and with division rules (respectively, separation rules), where the meaning of parameters α,β,γand δis the following: •If α=pmc (resp. α=bmc or α=mcmp) then primary minimal cooperation (resp. bounded minimal cooperation or minimal cooperation and minimal production) in object evolution rules are permitted. If α= +ethen any noncooperative object evolution rule is permitted. •If β= +c(resp. β=−c) then communication rules are permitted (resp. forbidden). •If γ= +d(resp. γ=−d) then dissolution rules are permitted (resp. forbidden). •If δ= +n(resp. δ=−n) then division/separation rules for elementary and non–elementary membranes are permitted (resp. only division/separation rules for elementary membranes are permitted). In this context, counting membrane systems instead of recognizer membrane systems can be considered [10]. The output of these systems will be natural numbers. 2.2 Cell-like P systems with symport/antiport rules Cell-like P systems with symport/antiport rules were introduced in [7] aiming to abstract the biological phenomenon of trans-membrane transport of couples of chemical substances, in the same or in opposite directions. A P system with symport/antiport rules of degree q Π= (Γ, E, µ, M1,...,Mq,R1,···,Rq, iout) can be viewed as a set of qmembranes, labelled by 1, . . . , q, arranged in a hierarchical structure µgiven by a rooted tree whose root is called the skin membrane, such that: (a) M1, . . . , Mqrepresent the finite multisets of objects initially placed in the qmembranes of the system; (b) Eis the set of objects initially located in the environment of the system, all of them available in an arbitrary number of copies; (c) R1,· · · ,Rqare finite sets of communication rules over Γ(Riis associated with the membrane iof µ); and (d) iout represents a distinguished region which will encode the output of the system. We use the term region i(0 ≤i≤q) to refer to membrane iin the case 1 ≤i≤qand to refer to the environment in the case i= 0. The length of rule (u, out) or (u, in) (resp. (u, out;v, in)) is defined as |u| (resp. |u|+|v|). Division rules and separation rules are introduced in these models Complexity Perspectives on Minimal Cooperation 73 in a similar way that in polarizationless P systems with active membranes, both in syntax and semantics. For each natural number k≥1, we denote by CDC(k) (respectively, CSC(k)) the class of P systems with symport/antiport rules and division rules (respectively, separation rules) such that the length of the communication rules is at most k. When division or separation for non-elementary membranes is permitted then we denote CDneC(k) and CSneC(k), respectively. If the alphabet of the environment is the empty set then we write d CDC(k), d CSC(k), respectively. 3 Proof techniques The results described at the next Section have been obtained by using three different proof techniques: •Dependency graph: a directed graph (dependency graph)GΠassociated with a P system Πis considered in such a way that there exists an accepting computation of Πif and only if there exists a path between two distinguished nodes in the dependency graph associated with it. •Algorithmic technique: a deterministic algorithm Aworking in polynomial time that receives as input a P system Πand an input multiset mof Πis considered in such a manner that algorithm Areproduces the behaviour of a single computation of Π+m. •Simulation technique: a P system Π′simulating (in an efficient way) a given P system Πis constructed, in such a way that there exists an efficient and injective correspondence between accepting computation of Π′and accepting computation of Π. 4 Recent results The role of minimal cooperation is studied from the computational complexity point of view. In the case of polarizationless P systems with active membranes, objects evolution rules whose left-hand side consists of a couple of objects are considered. In the case of cell-like P systems with symport/antiport rules, minimal cooperation is expressed by the property of the length of communication rules to be equal to two. 4.1 Polarizationless P systems with active membranes By using the dependency graph technique it has been shown that families of noncooperative polarizationless P systems with active membranes which make no use of dissolution rules, can only solve tractable problems in an efficient way [3, 14]. Theorem 1. P =PMCDAM0(+e,+c,−d,+n)=PMCSAM0(+e,+c,−d,+n). 80 A. Alhazov, R. Freund, S. Ivanov As indicated by its name, membrane computing draws inspiration from the structure and functioning of the living cell [16]. Indeed, one can see the cell as a hierarchical arrangement of containers (rooted at the cellular wall) performing biochemical processing. A great variety of abstract representations of substance flow within the membranes as well as across them has been proposed: communication rules, symport/antiport rules, dissolution rules, etc. [17]. On the other hand, P systems have a distinctive computer science touch: objects evolve in discrete, synchronous steps determined by a global clock, the rules defining the behaviour are typically (multiset) rewriting rules. Although computer science and cell biology are arguably distinct domains, they do have one feature in common: the description of the “program” can be modified by the organism itself. In cells, this paradigm (sometimes referred to as “program is data”) is represented by mechanisms such as reverse transcription [8], while in computer science this is embodied by the fact that the program is stored in the memory alongside the data it manipulates. It is therefore only natural that there have been quite a number of attempts to represent the “program is data” paradigm in membrane computing. Examples of such possible presentations include generalised P systems [9], rule creation [5], activators [1], inhibiting/deinhibiting rules [7], symport/antiport of rules [6], etc. One notable characteristic of the majority of these cited approaches is that, even though the set of rules associated with a given membrane may evolve, the rules appearing in this set may only be chosen from a finite, statically fixed, collection. Polymorphic P systems are an implementation of the “program is data” paradigm for membrane systems which does not limit the set of available rules by a finite cardinality and which allows direct tampering with the form of the rules. In polymorphic P systems, rules are not statically defined, but are instead dynamically inferred from the contents of specially designated pairs of membranes. One member of such a pair defines the multiset representing the left-hand side of the rule; the other member defines the right-hand side. Dynamic definition of rules via pairs of membranes has numerous interesting consequences: •natural rule dynamics: since rules are defined by the contents of membranes, sending an object across a membrane and changing a rule are exactly the same operation; •nested rules: the definition does not restrict the membranes defining the sides of a rule to occupying some particular slots of the membrane hierarchy; in particular, we are allowed to place rules inside the membranes defining other rules; •inexpensive simulation: there is almost no additional overhead to naively simulating polymorphic P systems on a conventional computer: instead of only moving symbols from membranes to membranes, the simulator should be made capable of also moving symbols into and out of the collections representing the sides of rules. Polymorphic P Systems: A Survey 81 Polymorphic P systems can thus modify their own “program” in a quite natural way: by moving around symbols. Furthermore, nesting rules quickly gives rise to highly non-trivial behaviour. This, on the one hand, means that polymorphism may be used to solve complex problems (like recognising the factorial language) with relative ease. On the other hand, polymorphic rules may be in quite complex interdependence, which often makes reasoning about their behaviour a quite difficult task. Polymorphic P systems were originally introduced in the 2011 paper [4]; the subsequent work [11] analyses the power of the minimal variant of polymorphic P systems, in which most of the usual ingredients (cooperative rules, communication rules, etc.) are not allowed. The paper [3] considers general states in P systems; this framework generalises, among other things, the idea of polymorphism. Unfortunately, apart from the three cited works, polymorphic P systems have received relatively little attention. The goal of the present article is to give an overview of the existing (scanty) results on polymorphic P systems and to list the numerous research directions that are still open. This article is structured as follows. Section 2 recalls some basic notions from the theory of formal languages and defines conventional P systems as well as polymorphic P systems. The immediately following Section 3 recalls how polymorphism and target indications can be used to achieve fast growth rates and to generate complex languages. The following Section 4 recalls several more specific terms which capture some details of polymorphism more precisely. These terms are used in Section 5 to describe the power of non-cooperative polymorphism without target indications. Section 6 briefly recalls the concept of state in P systems as introduced in [3] and shows how states generalise polymorphism. Finally, Section 7 gives an overview of some of the possible directions of research on polymorphic P systems listing 11 major open questions. 2 Preliminaries An alphabet Vis a finite set, and a multiset over Vis any function w:V→N; w(a)isthemultiplicity of ain w. A multiset wis often represented by one of the strings containing exactly w(a) copies of each symbol a∈V.Thesupport supp(w) of the multiset wis the set of elements appearing in wa non-zero number of times: supp(w)={a∈V|w(a)>0}. The set of all multisets over the alphabet Vis denoted by V◦. The empty multiset is denoted by 0(supp(0)=∅). The projection (restriction) of wover a subalphabet V⊆Vis the multiset w|Vdefined as follows: w|V(a)=w(a),a∈V; 0,a∈VV. We denote the family of recursively enumerable sets of non-negative integers by NRE. 82 A. Alhazov, R. Freund, S. Ivanov For further introduction to the theory of formal languages and computability, we refer the reader to [15, 17]. 2.1 P Systems: The Basic Model APsystemis a construct Π=(O, T,μ,w1,...,w n,R 1,...R n,h i,h o), where Ois the alphabet of objects, T⊆Ois the alphabet of terminal objects, μis the membrane structure injectively labelled by the numbers from {1,...,n} and usually given by a sequence of correctly nested brackets, wiare the multisets giving the initial contents of each membrane i(1 ≤i≤n), Riis the finite set of rules associated with membrane i(1 ≤i≤n), and hiand hoare the labels of the input and the output membranes, respectively (1 ≤hi≤n,1≤ho≤n). The depth of the membrane structure μis the height of this structure seen as a tree. Thus, a membrane system which only has one membrane is of depth 1; a membrane system with two nested membranes is of depth 2, etc. Quite often the rules associated with membranes are multiset rewriting rules (or special cases of such rules). Multiset rewriting rules have the form u→v, with u∈ Oo\{0}and v∈Oo.If|u|=1,theruleu→vis called non-cooperative;otherwiseit is called cooperative.Incommunication P systems, rules are additionally allowed to send symbols to the neighbouring membranes. In this case, for rules in Ri, v∈O×Tar i,whereTar icontains the symbols out (corresponding to sending the symbol to the parent membrane), here (indicating that the symbol should be kept in membrane i), and inh(indicating that the symbol should be sent into the child membrane hof membrane i). In P systems, rules are often applied in a maximally parallel way: in one derivation step, only a non-extendable multiset of rules can be applied. The rules are not allowed to consume the same instance of a symbol twice, which creates competition for objects and may lead to the P system choosing non-determinstically between the maximal collections of rules applicable in one step. A computation of a P system is traditionally considered to be a sequence of configurations it can successively pass through, stopping at the halting configuration. A halting configuration is a configuration in which no rule can be applied any more, in any membrane. The result of a computation of a P system Πas defined above is the contents of the output membrane hoprojected over the terminal alphabet T. While maximal parallelism and halting by inapplicability are staple ingredients, various other derivation modes and halting conditions have been considered for P systems [17]. 2.2 Polymorphic P Systems Apolymorphic P system is the following construct: Polymorphic P Systems: A Survey 83 Π=(O, T,μ,ws,w1L,w 1R,...,wnL,w nR,h i,h o), where Ois a finite alphabet of objects, Tis the subalphabet of terminal objects, μis a tree structure consisting of 2n+1membranes,wsis the multiset giving the contents of the skin membrane, wiL,w iRare pairs of multisets giving the contents of membranes iL and iR (1 ≤i≤n), and hiand hoare the labels of the input and the output membranes, respectively, with hi∈Hand ho∈H∪{0},where0 denotes the environment. We require that, for every 1 ≤i≤n, the membranes iL and iR have the same containing (parent) membrane. The depth of (the membrane structure of) Πis defined as for conventional P systems: it is the height of μseen as a tree. The rules of Πare not statically given in its description and are instead dynamically inferred for each configuration based on the contents of the pairs of membranes iL and iR. Thus, if in a configuration of the system these membranes contain the multisets uand v, respectively, then, in the next step, their parent membrane hwill evolve as if it had the multiset rewriting rule u→vassociated with it. If, however, in some configuration, iL is empty, we consider the rule defined by the pair iL, iRto be disabled, i.e. no rule will be inferred from the contents of iL and iR. Polymorphic P systems evolve by applying the dynamically inferred rules in a maximally parallel way. A computation of a polymorphic P system Πis a finite sequence of configurations Πmay successively visit, ending in the halting configuration in which no rules can be applied any more in any membrane. Like for other classes of P systems, the output of Πis the contents of the output membrane ho projected onto the terminal alphabet T. It follows from the definition of polymorphic P systems that the total set of rules which may be applied during a derivation of such a system Πis unbounded. Indeed, Πmay ensure unbounded growth of the contents of a right-hand-side membrane iR. Remark however that the total number of rules available in an evolution step is statically bounded by the number of membranes. Not too many additional ingredients have been considered for polymorphic P systems up to now. The only one actually discussed in [4] is target indications. Target indications for polymorphic P systems were defined by adding the following mapping to the definition of a system: ϕ:{iR |1≤i≤n}→{inh|h∈H}∪{here, out}. This mapping assigns a target indication to every right-hand-side membrane. The target indication is interpreted as in the case of conventional P systems. Note that, by this definition, ϕis allowed to assign any target indication inh to any right-hand-side membrane, which would effectively allow ignoring the hierarchical membrane structure for communication purposes. Nevertheless, in all the examples considered in the present article (and in the other works published to date), targets are always given with respect to the membrane structure of the system. 84 A. Alhazov, R. Freund, S. Ivanov In the present article we follow the tradition of not explicitly drawing membranes defining invariable rules in graphical illustrations [4, 11]. Thus, if the contents wiL and wiR never change, we graphically represent the defined rule by the usual notation wiL →wiR. 3 The Power of Polymorphism In this section we showcase the power of polymorphic P systems by giving concrete constructions achieving complex behaviour while retaining low levels of descriptional complexity. We use the term growth rate to refer to the formula describing the size of the multiset contained in a membrane of a P system (or the union of the contents of all membranes) as a function of time (number of steps). 3.1 Polymorphism without Target Indications We start by showing how superexponential growth (in time) can easily be achieved using polymorphism alone without any additional ingredients. Example 1 (superexponential growth [11]). Consider the following polymorphic P system: Π1=({a},{a},μ,a,a, a,a, aa,s),where μ=[[ ] 1L[[ ] 2L[] 2R]1R]s. Π1has superexponential growth rate. A graphical illustration of Π1is given in Figure 1. 2:a→aa a 1R a1L as Fig. 1. The polymorphic P system Π1with superexponential growth In the initial configuration, the membranes 1Land 1Rdefine the rule a→ain the skin membrane s. Rule 2 in membrane 1Ris formally represented by the pair of membranes 2L, 2R, but graphically depicted as a→aa, because the contents of 1Rand 1Rnever change. In the first derivation step, rule 1 (a→a) is applied in the skin, leaving the contents of the membrane intact, and rule 2 (a→aa) is applied in membrane 1R, doubling the number of a’s; therefore, after the first step, rule 1 will be of the form a→aa. In the second step of the derivation, rule 1 will transform the multiset ain the skin into aa, and rule 2 will double the contents of the right-hand-side Polymorphic P Systems: A Survey 85 membrane 1Ronce again, thus transforming rule 1 into a→a4.Consequently,in the third derivation step, rule 1 will quadruple the number of a’s in the skin. In general, after kderivation steps, the contents of the right-hand-side membrane 1Rwill be 2k, and rule 1 will have the form a→a2k.Thenumberofa’s in the skin will be given by the product 1 ·2·4·...·2k−1or, equivalently, by the following formula: 20·21·22·...·2k−1=2 1+2+...+k−1=2 k(k−1) 2. The rate of growth of the contents of the skin membrane therefore is superexponential. Besides showing off impressive growth rates, the previous example also helps to fix an upper bound on how fast a polymorphic P system can grow. Proposition 1. [11, Theorem 4],[4, page 7] The growth rate of the contents of any membrane of a polymorphic P system Πof depth d(without target indications) is bounded by the polynomial Icp(n),where: •Iis the total number of objects in the initial configuration of Π, •cis the maximal size of a right-hand side of an invariable rule of Π, •p(n)is a polynomial of degree at most d−1. Indeed, a polymorphic P system Πachieves superexponential growth by nesting right-hand-side membranes. Each level of nesting contributes a factor to the exponent of the formula expressing the growth rate. Since the depth of the membrane structure is statically bounded, the degree of the polynomial in the exponent is bounded as well, and its form is determined by the initial contents of the membranes. Even though the P system Π1of Example 1 does achieve superexponential growth rates, it never halts and the language it generates is therefore empty. More effort is needed to actually generate the set of the powers of two. A first idea would be embedding the pair of rules a→aand a→λinto 1L, thereby making it possible to disable the multiplying rule 1 at an arbitrary moment. This will effectively stop multiplication, but 1Rwill keep evolving, since rule 2 is always applicable. If, additionally, we decide to arbitrarily disable rule 2, it may become disabled before rule 1 (before the contents of 1Lis erased), which will lead to several multiplications of the contents of the skin by a constant factor. The construction from the following example illustrates how to properly stop the multiplications. The main idea for achieving rule inapplicability consists in rewriting all instances of ainto a different symbol. Example 2 (powers of two [11]). Consider the following polymorphic P system: Π2=({a, b},{b},μ,a,a, a,a, aa,a, a,a, a,a, b,s),where μ=[[ ] 1L[[ ] 2L[[ ] 3L[[ ] 4L[] 4R[] 5L[] 5R]3R]2R]1R]s. 86 A. Alhazov, R. Freund, S. Ivanov 4:a→a 5:a→b a 3R a3L aa 2R a2L a 1R a1L as Fig. 2. The P system Π2generating the number language 2 n(n−1) 2  n∈N,n>3 The number language generated by Π2is N(Π2)=2n(n−1) 2n∈N,n>3.A graphical representation of Π2is given in Figure 2. Membranes s,1L,1R,2L,and2Rof Π2have the same initial contents as the corresponding membranes of Π1. The role of the additional infrastructure in membrane 2Rof Π2is to ensure proper halting. Π2operates in two phases. During the first phase, rule 4 is always applied in membrane 3R, keeping rule 3 in the form a→a, which does not change the righthand-side membrane 2R. In the first phase Π2therefore does the same thing as Π1. The second phase of a computation of Π2starts with the application of rule 5 in 3R, which changes rule 3 into a→b. This, in the next step, changes rule 2 into a→bb. In the following step, all the a’s of 1Rare rewritten into b’s, which finally leads to rewriting all the a’s in the skin into b’s. The second phase takes four steps and rewrites all a’s into b’s, while keeping the multiplications going. This explains the constraint n>3 in the definition of the number language N(Π2) generated by Π2:N(Π2)=2n(n−1) 2n∈N,n>3. 3.2 Polymorphism with Target Indications Adding target indications to polymorphic P systems allows a more fine-grained control of the evolution. For example, it is relatively easy to generate the factorial number language using only four rules without nested right-hand-side membranes. Example 3 (factorial [4]). Consider the following polymorphic P system with target indications: Π3=({a, b, c, d},{b},μ,abd,a, a,b, bd,b, c,d, a,ϕ,s),where μ=[[ ] 1L[] 1R[] 2L[] 2R[] 3L[] 3R[] 4L[] 4R]s, ϕ(1R)=ϕ(2R)=here, ϕ(3R)=in1L,ϕ(4R)=in1R. Π3generates the number language N(Π3)={n!|n∈N}. A graphical representation of Π3is given in Figure 3. For rules 3 and 4 whose right-hand-side membranes Polymorphic P Systems: A Survey 87 3Rand 4Rare attributed targets different from here,weusethestandardPsystem notation for targets as a shortcut; for example (c, in1L) stands for “produce acand send it into membrane 1L”. a1La1R 2:b→bd 3:b→(c, in1L) 4:d→(a, in1R) abd s Fig. 3. The polymorphic P system Π3generating the factorial number language Π3calculates the factorial in a very straightforward fashion: by successive multiplications. The whole process is controlled by the symbol bwhich chooses between rules 2 and 3. If rule 2 is applied, bis sustained and an instance of dis produced, which, in the next step, adds an ato the right-hand side of rule 1 (by applying rule 4). Thus, while bchooses rule 2, the right-hand side of rule 1 grows by one a symbol a step, which leads to the multiplication of the contents of the skin by successive natural numbers, starting from 1 in the first step. Π3halts by applying rule 3, which erases the control symbol band renders rule 1 inapplicable by adding an extra dummy cto 1L. Remark that the complexity of computing n! is linear in n. More precisely, Π3 needs nsteps to generate n!(n≥1). Indeed, rule 1 is applied in every step effecting multiplications by successive natural numbers, and, when rule 1 is inapplicable, we are sure that bhas been erased by rule 3 and dby rule 4, which renders all rules inapplicable. Note that, while this example takes over the example shown at the top of page 9 of [4], there is a minor difference: in Example 3 we add an instance of dto the skin from the very beginning. This avoids an extra “warm-up” step in which the first instance of dis produced by rule 2. Finally, we would like to point out that Π3uses “half” of the appearance checking functionality provided by cooperativity: rule 1 becomes non-cooperative only in the halting configuration and is never applied. As we will later see, rule 1 of Π3is a weakly non-cooperative rule. Besides generation of the factorial language, the article [4] also shows how to generate the double exponential language 22nn∈Nin linear time using polymorphism coupled with target indications. This language of 2n-th powers of 2 is obtained by iterated squaring of the number of symbols present in the skin of the system. 88 A. Alhazov, R. Freund, S. Ivanov Example 4 (double exponential [4]). Consider the following polymorphic P system with target indications: Π4=({a, b, a,b ,c},{a},μ,b 2,a, λ,a, a,a, c, b, λ,b, ab,a,a,b,b,ϕ,s),where μ=[ [[ ] 2L[] 2R[] 3L]1L[[ ] 4L[] 4R]1R [] 5L[] 5R[] 6L[] 6R[] 7L[] 7R]s, ϕ(h)=here, h ∈{iR |1≤i≤6}, in1R,h=7R. This P system generates the number language N(Π4)=22nn∈N. A graphical presentation of Π4is given in Figure 4. 2:a→a 3:a→c a1L 4:b→λ λ1R 5:b→ab 6:a→a 7:b→(b, in1R) b2 s Fig. 4. The polymorphic P system Π4generating the language 22n  n∈N A computation of Π4is structured into three-step phases. A phase starts with an application of rule 5, which splits each binto a band an a. In the second step of a phase, rules 6 and 7 are applied. Rule 6 rewrites every ainto an a;rule7 removes primes from band moves all of the resulting instances of binto 1R.In the third step of a phase, rule 1 may become applicable, rewriting each ain the skin into as many instances of bas there were initially at the start of the phase. The first two steps of a phase ensure that there are as many instances of bin 1Ras there are instances of ain the skin. An application of rule 1 therefore squares the number of symbols in the skin. In total, if the skin contains the multiset bkat the beginning of a phase, it will contain the multiset bk2at the end of the phase. To allow Π4to chain multiple such phases, rule 4 discards all b’s immediately after rule 1 is applied at the end of a phase. Remark that the only time when the skin contains a’s and when rule 1 is applicable is when 1Ralso contains some instances of b; rule 1 is thus never applied to erase instances of a. Finally, rules 2 and 3 in 1Lcontrol the liveliness of Π4. While the system applies rule 2 keeping an ain 1L, the other rules may keep on squaring the contents of the skin. When Π4chooses to apply rule 3, rule 1 is rendered forever inapplicable, because cnever appears in the skin. Rules 5, 6, and 7 may split b’s into band a, sending some b’s into 1R, but the skin does not contain rules for processing a Polymorphic P Systems: A Survey 89 any more. Rule 4 will drop the last packet of b’s sent in by rule 7 and will stop evolving as well, thus leading to the total halting of Π4. The claim that Π4produces 22ninstances of ain a time linear in nfollows from the fact that it takes Π4only three steps to square the number represented by the symbols in the skin. Notice that, independently of the moment at which rule 3 is applied to disable rule 1, the first two steps of a phase will always take place. In the third step, however, only rule 4 in 1Rwill be applied, discarding the last instances of bin the system. We can thus give a more accurate value for the time complexity of the work of Π4: this system takes 3(n+ 1) steps to calculate 22n. Comparing the constructions from the previous two subsections leads to an interesting conclusion: Proposition 1 sets an upper bound on the power of polymorphism without target indications which is surpassed by Π4using target indications. Thus, adding target indications to polymorphic P systems strictly increases their expressive power. This result is formally summarised in Corollary 2 stated in Section 5. The original article [4] introducing polymorphic P systems gives further examples of constructions with intricate behaviour, like generating the language {n!·nk|n, k ∈N}[4, Example 2], deterministically computing the function n→22n[4, Example 5], deciding the factorial language [4, Example 6], etc. We refer the reader to the cited article for details. 4 Some Formal Aspects of Polymorphism Now that we have seen several examples showing off the power of polymorphism, we will recall some definitions from [11, Subsection 2.2] which will allow us to describe the expressivity of polymorphic P systems using a more fine-grained language. Definition 1 (strong non-cooperativity [11]). Rule i(defined by the pair of membranes iL, iR) of a polymorphic P system Πis said to be strongly noncooperative if, in any evolution, iL contains at most one symbol. Definition 2 (weak non-cooperativity [11]). Rule i(defined by the pair of membranes iL, iR) of a polymorphic P system Πis said to be weakly noncooperative if, whenever it is applied, its left-hand-side membrane iL contains exactly one symbol. Weak non-cooperativity therefore allows a rule to have more than one symbol in the left-hand side and only requires that this rule to be not applicable in such situations. For example, all rules of Examples 1, 2, and 4 are strongly non-cooperative, while rule 1 of Example 3 is weakly non-cooperative, because its left-hand side is of the form ac in the halting derivation and because it is never applied after cis added to 1L. 96 A. Alhazov, R. Freund, S. Ivanov 7 Open Questions We choose to employ the concluding section of this article to outline some of the possible research directions around polymorphic P systems. For readability, we group the research directions into subsections. 7.1 Expressive Power The expressive power of polymorphic P systems is largely understudied. The original article [4] introducing the model barely scratched the surface of the problem, pointing out the sufficiently obvious computational completeness in the general case (because polymorphic P systems generalise conventional P systems, which are computationally complete) and focused on showing off the power of the model almost exclusively. The later work [11] considered the most basic variant without cooperativity and communication, and showed that bare polymorphism may induce pretty non-trivial behaviour. The following list gives some concrete questions concerning the expressivity of polymorphism, in no particular order. Question 1 (right polymorphism [11]). Are non-cooperative, right-polymorphic P systems less powerful than general polymorphic P systems? While it is relatively easy to give a positive answer to the counterpart of this question for left-polymorphic P systems – such systems have insufficiently deep membrane structures to capture general polymorphism, as shown in Corollary 1 and Theorem 3 – right polymorphism is a more difficult subject to handle. Indeed, Corollary 1 seems to imply that the contribution of the variability of left-hand sides of membranes is rather unimportant. Given that virtually no synchronisation is possible between the right- and the left-hand-side membranes defining a rule, it maywellbepossiblethatnon-cooperative, right-polymorphic P systems are just as powerful as P systems in which both rule sides are allowed to vary. Question 2 (upper bounds [11]). What are the upper bounds on the expressive power of non-cooperative (left-, right-) polymorphic P systems? Subsection 5.3 recalls a series of results giving a hint of the computational power of different kinds of polymorphism, but no actual upper bounds have been set yet. Proving such upper bounds may be quite helpful in improving our understanding of polymorphism. Question 3 (target indications [11]). What is the expressive power of (strongly, weakly) non-cooperative polymorphic P systems with target indications? Examples 3 and 4 seem to suggest that the contribution of target indications to the computing power of polymorphic P systems is considerable. Adding targets to rules seems to be a change sufficiently fundamental to actually differentiate between strong and weak non-cooperativity (cf. Conjecture 1). Polymorphic P Systems: A Survey 97 7.2 Better Target Indications The original article [4] already considers polymorphic rules with targets indications. It turns out that pretty coarse indications, sending the whole right-hand side into a membrane, already allow building interesting behaviour. However, in a typical communication P system, target indications are assigned to individual symbols, not to entire right-hand sides. The following question therefore seems very natural to be asked. Question 4 (finer targets). What is the most natural way to generalise target indications attached to individual symbols? This question is not exactly as trivial as it may sound, because assigning target indications enriches the structure of right-hand sides of rules, making them more than just multisets. In the coarse definition given in [4] and taken over in the present work, the extra structure is factored out into the mapping ϕassigning target indications to right-hand-side membranes; this allows a uniform treatment of left- and right-hand sides, as well as of the contents of the skin. Attaching targets to individual symbols may break this symmetry and should be handled carefully. For example, if we consider that symbols like (a, inh) may appear in a right-hand-side membrane, what happens if such a symbol is moved into a lefthand-side membrane? Furthermore, do we allow nested target indications, like in ((a, inh),in m)? The quest for finer target indications hides one more, orthogonal question. Question 5 (dynamic targets). What is the most natural way to define dynamic targets? Having dynamic targets would mean that a polymorphic P system could change the targets assigned to its right-hand-side membranes or to some particular symbols contained in such a membrane. This question is interesting not only in the context of finer-grained target indications: one may consider, for example, the ways in which a polymorphic P system as defined in this article (i.e., with coarse target indications given by the mapping ϕ) could dynamically modify the targets assigned to some right-hand-side membranes. Finally, the classical question on the topology of the membrane structure may also be considered for polymorphic P systems. Question 6. What is the most natural way to define polymorphic tissue Psystems? The conventional definition of tissue P systems relies on unrestricted target indications which allow any rule to place a symbol in any membrane (see [10] for a comprehensive overview). In this case, the membrane structure is typically omitted, since it has no influence on the evolution of the system. One of the implications of having such relaxed target indications in polymorphic P systems would probably be some kind of “flattening” of the membrane structure, since it will no longer be necessary for a rule to be “physically” located within a left- or a right-hand-side membrane of a another rule to be able to modify it. 98 A. Alhazov, R. Freund, S. Ivanov 7.3 Dissolution and Division Dissolution and division are among the most fascinating aspects of membrane computing. They were introduced to parallel the corresponding processes happening in the living cell, and have become notorious for the complexity of the behaviour they induce. This is particularly true for membrane division which has been shown to allow solving NP-complete problems in polynomial time. Introducing these concepts for polymorphic P systems seems to be a quite challenging task. Question 7 (dissolution). What is the most natural way of introducing membrane dissolution for polymorphic P systems? In polymorphic P systems, membranes are no longer independent entities and go in pairs defining the dynamic rules. What would be the semantics of dissolving a member of such a pair? Should the other member be dissolved as well (rule dissolution)? Should the other member become an ordinary membrane? This direction seems more promising, since dissolving pairs of rule membranes should be equivalent to simply disabling rules. Defining membrane division is even more challenging. Question 8 (division). What is the most natural way of introducing membrane division for polymorphic P systems? Just as in the case of dissolution, interdependence within pairs of rule membranes is what renders defining division difficult. What happens to membrane iL if its corresponding membrane iR is divided? Perhaps one of the simplest ways of dealing with this situation would be demoting both iL and the offspring of iR to regular membranes. Yet, considering more complex semantics may be very interesting. For example, we may consider that, dividing iR will also divide iL,inwhichcaseone will probably be able to achieve similar computational complexity feats as with P systems with active membranes. 7.4 Increasing the Exoticism Polymorphic P systems are already a relatively exotic member of the family of P systems, but this should not prevent the enthusiastic from increasing the exoticism of the model by adding other ingredients. One may consider membrane polarisations affecting the semantics of rules, target selection forcing only rules with the same target indications to be picked in a single evolution step [2], or even sending rules across membranes [13]. Various frameworks generalising many models of P systems [3, 10] may be of help in finding the extra ingredients and in properly introducing them alongside polymorphism. Polymorphic P Systems: A Survey 99 7.5 Applications One of the most exciting aspects of polymorphic P systems is that, unlike in the case of P systems with active membranes [18], naively simulating polymorphism on conventional computers does not seem to incur additional costs with respect to simulating conventional multiset rewriting rules. This is because, essentially, a naive simulator of multiset rewriting would be moving around collections of symbols; to enable polymorphism, it would just have to support moving symbols into and out of rule sides. Nevertheless, this reasoning may quickly become irrelevant for specific optimised implementations which expect the rules to be invariable. One notable example are simulators running on SIMD architectures (e.g., general purpose GPUs), which may have some particular restrictions on how data is to be moved around [14]. Question 9 (optimising simulators). Is polymorphism always easy to be simulated on conventional computers? On the other hand, applications of polymorphic P systems may be of interest in topics related to complexity. Question 10 (polymorphism vs. complexity). Can polymorphism be used for solving some complex problems faster? This question is particularly interesting in the context of comparing polymorphic P systems with P systems with active membranes. The latter model is known to be able to solve NP-complete problems in polynomial time; would something similar be possible with polymorphism? We conjecture a negative answer to the strongest formulation of this question: otherwise, supposing trivial simulation of polymorphism on conventional computers, we could end up solving NP-complete problems in polynomial time using the existing technology. The conjectured inferiority of the computing power of polymorphism with respect to that of active membranes implies a new question which is arguably more interesting. Question 11. What are the problems that polymorphic P systems can solve faster than conventional P systems? We have seen that polymorphism allows achieving non-trivial speed-ups in generation of some complex languages. Are there any other examples? If yes, why is polymorphism more efficient than conventional P systems? Overall, polymorphic P systems seem to be a field full of interesting questions and results awaiting exploration. Given the scarcity of publications focusing on this extension of P systems, we conjecture that not all of the questions left unanswered require superhuman powers to be handled. 100 A. Alhazov, R. Freund, S. Ivanov References 1. Artiom Alhazov. A note on P systems with activators. In Gheorghe P˘aun, Agust´ın Riscos-N´u˜nez, Alvaro Romero-Jim´enez, and Fernando Sancho-Caparrini, editors, Second Brainstorming Week on Membrane Computing, Sevilla, Spain, February 2-7 2004, pages 16–19, 2004. 2. Artiom Alhazov and Rudolf Freund. Variants of small universal P systems with catalysts. Fundamenta Informaticae, 138(1-2):227–250, 2015. 3. Artiom Alhazov, Rudolf Freund, Sergiu Ivanov, and Marion Oswald. Observations on P systems with states. In Marian Gheorghe, Ion Petre, Mario J. P´erez-Jim´enez, Grzegorz Rozenberg, and Arto Salomaa, editors, Multidisciplinary Creativity. Hommage to Gheorghe P˘aun on His 65th Birthday. Spandugino, 2015. 4. Artiom Alhazov, Sergiu Ivanov, and Yurii Rogozhin. Polymorphic P systems. In Marian Gheorghe, Thomas Hinze, Gheorghe P˘aun, Grzegorz Rozenberg, and Arto Salomaa, editors, Membrane Computing, volume 6501 of Lecture Notes in Computer Science, pages 81–94. Springer, 2011. 5. Fernando Arroyo, Angel V. Baranda, Juan Castellanos, and Gheorghe P˘aun. Membrane computing: The power of (rule) creation. Journal of Universal Computer Science, 8:369–381, 2002. 6. Matteo Cavaliere and Daniela Genova. P systems with symport/antiport of rules. In Gheorghe P˘aun, Agust´ın Riscos-N´u˜nez, Alvaro Romero-Jim´enez, and Fernando Sancho-Caparrini, editors, Second Brainstorming Week on Membrane Computing, Sevilla, Spain, February 2-7 2004, pages 102–116, 2004. 7. Matteo Cavaliere, Mihai Ionescu, and Tseren-Onolt Ishdorj. Inhibiting/de-inhibiting rules in P systems. In Pre-proceedings of the Fifth Workshop on Membrane Computing (WMC5), Milano, Italy, June 2004, pages 174–183, 2004. 8. John M. Coffin, Stephen H. Hughes, and Harold E. Varmus, editors. Overview of Reverse Transcription – Retroviruses. Cold Spring Harbor Laboratory Press, 1997. 9. Rudolf Freund. Generalized P-Systems. In Gabriel Ciobanu and Gheorghe P˘aun, editors, Fundamentals of Computation Theory, 12th International Symposium, FCT ’99, Ia¸si, Romania, August 30–September 3, 1999, Proceedings, volume 1684 of Lecture Notes in Computer Science, pages 281–292. Springer, 1999. 10. Rudolf Freund and Sergey Verlan. A formal framework for static (tissue) P systems. In George Eleftherakis, Petros Kefalas, Gheorghe P˘aun, Grzegorz Rozenberg, and Arto Salomaa, editors, Membrane Computing, volume 4860 of Lecture Notes in Computer Science, pages 271–284. Springer, 2007. 11. Sergiu Ivanov. Polymorphic P systems with non-cooperative rules and no ingredients. In Marian Gheorghe, Grzegorz Rozenberg, Arto Salomaa, Petr Sos´ık, and Claudio Zandron, editors, Membrane Computing - 15th International Conference, CMC 2014, Prague, Czech Republic, August 20–22, 2014, Revised Selected Papers, volume 8961 of Lecture Notes in Computer Science, pages 258–273. Springer, 2014. 12. Ivan Korec. Small universal register machines. Theoretical Computer Science, 168(2):267–301, 1996. 13. Shankara Narayanan Krishna and Gheorghe P˘aun. P systems with mobile membranes. Natural Computing, 4(3):255–274, 2005. 14. Miguel A. Mart´ınez-del-Amor, Luis F. Mac´ıas-Ramos, Luis Valencia-Cabrera, Agust´ ın Riscos-N´u˜nez, and Mario J. P´erez-Jim´enez. Accelerated simulation of P systems on the GPU: A survey. In Linqiang Pan, Gheorghe P˘aun, Mario J. P´erez- Jim´enez, and Tao Song, editors, Bio-Inspired Computing - Theories and Applications: Polymorphic P Systems: A Survey 101 9th International Conference, BIC-TA 2014, Wuhan, China, October 16-19, 2014. Proceedings, pages 308–312. Springer, Berlin, Heidelberg, 2014. 15. Gheorghe P˘aun. Computing with membranes. Journal of Computer and System Sciences, 61:108–143, 2000, and TUCS Report 208, November 1998 (www.tucs.fi). 16. Gheorghe P˘aun. Membrane Computing: An Introduction. Natural Computing Series Natural Computing. Springer, 2002. 17. Gheorghe P˘aun, Grzegorz Rozenberg, and Arto Salomaa, eds. The Oxford Handbook of Membrane Computing. Oxford University Press, Inc., New York, NY, USA, 2010. 18. Antonio E. Porreca, Alberto Leporati, Giancarlo Mauri, and Claudio Zandron. P systems with active membranes: Trading time for space. Natural Computing, 10(1):167– 182, 2011. 19. Bulletin of the International Membrane Computing Society (IMCS). http://membranecomputing.net/IMCSBulletin/index.php. 20. The P Systems Website. http://ppage.psystems.eu/. Some Notes on Membrane Computing and Image Processing Daniel D´ıaz-Pernil1, Miguel A. Guti´errez-Naranjo2, Hong Peng3 1CATAM Research Group - Dept. of Applied Mathematics I University of Seville, Spain [email protected] 2Dept. of Computer Science and Artificial Intelligence University of Seville, Spain [email protected] 3School of Computer and Software Engineering Xihua University, Chengdu, 610039, China [email protected] Summary. The application of Membrane Computing techniques to the study of digital images has been a vivid research area in the last years. In this paper, some of the research lines are presented and many of the main published papers are cited in the bibliography. 1 Introduction Computer vision [131] is one of the most promising challenges for computer scientists in the next years. This research area is placed in the interplay of many disciplines, such as artificial intelligence, pattern recognition, signal processing, neurobiology, psychology or image processing among others. It concerns the automated processing of images from the real world to extract and interpret information on a real time basis. Roughly speaking, a digital image is a two dimensional surface where each point is associated to a set of features such as bright or color. It is natural to consider only a discrete version of the definition, since only a finite amount of pixels placed in a lattice of integer coordinates is usually considered. The set of features can also have a finite amount of values (e.g., values in a range {0, . . . , 255} for colors). Such discrete amount of data makes digital images appropriate to be dealt with Membrane Computing techniques, but other features can be also considered. One of them is that the treatment of the image can be parallelized and locally solved. Regardless how large is the picture, many of the processes can be performed in parallel in different local areas of the image. Another interesting feature is that the local information needed for an image transformation can also be easily encapsulated in a membrane and represented as a multiset of objects. Such 104 D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, H. Peng features, together with the maximal parallelism, have encouraged many researchers to explore the links between Membrane Computing and digital image processing. Formally, a 2D digital image I of size n×m(n, m ∈N) is a rectangular net of objects (i, j) called pixels (voxels in 3D images), with 1 ≤i≤nand 1 ≤j≤m(in general, any subset of the integer plane Z×Zcan be chosen). Let C,the alphabet of colors of I, be the ordered set of all colors in I. We define the size of C,|C|, as the number of colors of this alphabet. Moreover, we will assume that each pixel of Iis associated to a color of C. So, we encode the pixel (i, j) with associated color a∈ C as the object aij . Therefore, the image Ican be codified as the set {aij :a∈ C ∧ 1≤i≤n∧1≤j≤m}. Another basic concept associated to pixels is the adjacency. In such case a distance is defined and two pixels are adjacent if the distance between them is one. Depending on the chosen distance, we can talk about 4-adjacency or 8-adjacency relation. The different treatments of such mappings (digital images) provide a big amount of current applications in biometrics [1], surveillance [27], medical imaging [3], human fingerprints classification [72], cartography [82], data compression and data storage [59], automated inspection of printed circuit boards [148] or optical character recognition (OCR) [134] among others. In the literature, one can find many examples of the use of bio-inspired techniques for dealing with problems associated to the treatment of digital images. One of the classic examples is the use of cellular automata [124, 129]. Other efforts are related to artificial neural networks as in [42, 154] or, more recently, deep learning [63]. In this paper, we present some of the main research lines bridging Membrane Computing and digital images. In Section 2, we recall the first attempts of linking both disciplines, mainly based on array grammars and on a graphical interpretation of the information encoded in a P system configuration which allows to associate a picture to it. Section 3 is devoted to one of the main applications of Membrane Computing to image processing, namely the segmentation of images. Segmentation is the process of splitting a digital image into sets of pixels in order to make it simpler and easier to analyze. One of its main uses is the localization of objects and boundaries. Technically, the process consists on assigning a label to each pixel, in such way that pixels with the same label form a meaningful region. Among the applications of segmentation of digital images, we can find the face recognition [153] or location of objects in satellite images (roads, forests, etc.) [50], but probably its main application area is medical imaging [8]. Section 4 is devoted to the skeletonization of images. Skeletonization is one of the approaches for representing a shape with a small amount of information by converting an image into a more compact representation and keeping the meaningful features. The conversion should remove redundant information, but it should also keep the basic structure. Other of the most promising applications focuses on algebraic-topological aspects of the images (Section 5) as those related to homology theory or discrete Morse theory (see, e.g., [24, 116]). The paper ends with an example of application (Section 6) and some final conclusions. Notes on MC and Image Processing 105 2 First Steps One of the first steps towards bridging Membrane Computing and digital images was considering two dimensional objects. The objects placed in a membrane are usually 0-dimensional or 1-dimensional (in the case of string-objects [46, 107]). The first step for considering images in Membrane Computing is the use of 2- dimensional objects, called arrays. Array grammars have been widely studied in the literature. They can be considered as a straightforward extension of string grammars to two dimensional pictures. Such pictures are sets of symbols placed in the points with integer coordinates of the plan (see, e.g. [28, 48, 123, 143]). In [15], the model of array-rewriting P systems was presented on the basis of the transition P systems [105]: Rules are of type A → B(tar) where Ais the array to be rewritten, Bis the new one and tar ∈ {here, in, out}indicates the emplacement of the picture where the substitution has been made. Different approaches can be found in [108, 137]. In a natural way, transition P systems were extended to other P systems models, as in [20], where tissue P systems with arrays are used for dealing with the segmentation of images (see Section 3). For example4, let us consider a P system with three nested membranes [ [ [ ]3]2]1, an alphabet with two symbols aand # (the blank), an initial configuration with membranes 2 and 3 empty and the array a aplaced in the membrane 1. Let us consider the sets of rules R1={# #a→a #a(in)}, R2={a# #→a a #(out),a# # #→a a a #(in)}, R3=∅. This P system generates all the L-shaped angles with equal arms, each arm being of length at least three. In the literature, there are many approaches setting bridges between array grammars and Membrane Computing (see, e.g. [2, 14, 15, 30, 31, 45, 81, 108, 137]). Other of the first links between P systems and digital images was the generation of graphical representation of branching structures able to simulate the growing of higher plants. The growth of plants, considered as a function of time, has attracted the attention of scientific community for a very long time. Features such as the bilateral symmetry of leaves, the central symmetry of flowers have been matter of study for computer scientists, mathematicians and life scientists among others. In 1968, Aristid Lindenmayer presented a theoretical framework for studying the development of simple multicellular organisms. The devices introduced in this framework are known as parallel rewriting systems or L-systems. L-systems were 4Adapted from the Example 1 in [15]. 112 D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, H. Peng 5 Algebraic-Topological Aspects A different approach to computer vision can also be obtained from Topology. Topology in Computer Vision is referred to connectivity, in a general way. For example, we look for connected components, holes in these connected components, etc., where the compulsory idea is the connection. In particular, algebraic topology [47] provides techniques and algorithms for dealing digital images from a topological point of view. The relationship between Algebraic Topology and Natural Computing is not new. In 1996, J. Chao and J. Nakayama [17] connected both areas using Neural Networks by extended Kohonen maps. Some years after, Giavitto et al. studied in [54] the topological structure of the Membrane Computing and Ceterchi et al. published two works where Digital Image is introduced in the framework of the Membrane Computing [14, 15]. 5.1 Effective Homology Recently, the links between algebraic topology and membrane computing have started to be explored via Homology Theory [23, 24, 37]. In such cases black and white images are taken and using labeling techniques the number of black connected components and the number of holes5of these connected components are calculated. This information is known as the Betti numbers from a 2D picture. Effective Homology [110, 130, 120], is a algebraic-topological theory mainly based on the computational notion of chain homotopy equivalence, a concept which algebraically connects a cell complex or subdivided object with its homology groups. Roughly speaking, a chain homotopy equivalence can be specified by an operator, called chain homotopy operator, working at level of linear combinations of cells which represents an efficient and non-redundant way of connecting cells. For instance, a chain homotopy operator at level of cells of dimension 0 of a cell complex Kcan be completely described by a directed spanning forest (as many trees as connected components the object has) of the graph subcomplex formed by all the cells of Kof dimension 0 and 1. Effective Homology uses chain homotopy operators for capturing homology information and for representing the object in an algebraic-topological way. In fact, this idea is underlying the Eilenberg-MacLane work [43, 44] for computing the homology of prime spaces in homotopy theory, and it has been recently used in discrete image context. In [62], a method for computing homology aspects (with coefficients in the finite field Z/2Z={0,1}) of a three dimensional digital binary-valued volume Vconsidered over a body-centered-cubic grid is described. The representation used in that paper for a digital image is an algebraic-topological model (AT-model) consisting in two parts: •Geometric modeling level: A cell complex K(V) topologically equivalent to the original volume is constructed. A 3D–cell complex consists of vertices (0–cells), 5White connected components surrounded by black connected components Notes on MC and Image Processing 113 edges (1–cells), faces (2–cells) and polyhedra (3–cells). In particular, each edge connects two vertices, each face is enclosed by a loop of edges, and each 3–cell is enclosed by an envelope of faces; •Homology analysis level: Homology information about K(V) is exclusively codified in terms of a chain homotopy operator [60, 61]. This method has recently evolved to a technique for generating a Z/2Z- coefficients. It takes an AT-model for a 26–adjacency voxel-based digital binary volume Vusing a polyhedral cell complex at geometric modeling level [76, 77, 89] and a chain homotopy operator described by a combinatorial vector field (a set of semidirected forests or a discrete differential form) at homology analysis level [111, 112]. For instance, a chain homotopy operator at level of cells of dimension 0 (vertices) of a cell complex K(V) can be completely described by a semidirected spanning forest of the graph subcomplex formed by all the cells of K(V) of dimension 0 and 1. In Figure 4, a pixel-based digital object O(first picture from the left) is analyzed as a cell complex in which the square pixels are the 0-cells. The 1-cells are edges joining 8-neighbor pixels and these 2-cells are triangles or squares formed by three or four mutually (and in a maximal way) 8-adjacent pixels. Picture (b) describes this cell complex (in dark grey) in which the barycenters of the different cells are drawn (solid circles for the 0-cells, crosses for the 1-cells and solid squares for the 2-cells). The subcomplex formed by the 0 and 1-cells can be seen as a subgraph of the 8-adjacency graph of O. In (c), a spanning tree covering all the vertices of the cell complex is specified. In fact, we consider a subdivision of this tree, having as 0-cells the vertices of the cell complex and the barycenters of the 1-cells belonging to the tree. An arrow in the tree determines the pairing of the source (0-cell) and sink (1-cell) cells and, consequently, indicating in this way that both are killed in homology group computation. Let us emphasize that only the top left 0-cell of the complex is not paired. It is a representative cycle (critical 0-cell of the homological process determined by the tree) of the unique connected component that the object has. Finally, in (d) we also draw the trees covering the rest of cells. They are semidirected, with arrows from the barycenters of 1-cells to the barycenter of the 2-cells. In terms of a process for computing homology groups, an arrow also means here that its source and sink cells are both killed. There is a edge marked in yellow which is not paired with an arrow. This 1-cell is a representative critical cell of the one-dimensional homology generator that the object has. Using Effective Homology Theory as main tool for designing algorithms for computing complexes topological invariants (cohomology ring, (co)homology operations, homotopy groups,...), the problem of decomposing the objects into combinatorial graph-like pieces appears in a natural way. A possible solution to solve the high complexity costs of these processes is provided here by Membrane Computing. Authors use in [32, 34] a well known tool from Membrane Computing, promoters. They are used to speed up the membrane algorithms. In that way, a bigger 114 D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, H. Peng Fig. 4. Example. Pictures (a) left up, (b) right up, (c) left down and (d) right down. amount of information is handled. Within the Digital Imagery setting, we determine here an Membrane Computing strategy for partially specifying a chain homotopy operator at the level of pixels for a pixel-based digital 2D binary object O. This fundamental data structure in Effective Homology is obtained in terms of a forest spanning every vertex of its associated adjacency graph. Every tree of this forest determines and localizes the corresponding connected component. In [32] authors obtain something more than the Betti numbers, they obtain the representative objects of each connected components and the borders of the holes. In this way, they get the homology groups. Until here, the efficiency of the membrane models with these kind of problems is tested. But, we have to think to a bigger problem: what will happen when we want to work with bigger dimensions? We have two different ways to follow. We could carry on as before, where the simplicity (from algebraic point of view) enables high efficiency. Or, we can introduce new algebraic-topological concepts where the amount of information to deal would be increased. Reina-Molina et al. decided to take this second option in [114, 115, 116]. They present a simulation of the Morse theory algorithms in a parallel way, getting the homology groups of n-D objects. We have introduced two different theoretical ways to solve problems from Algebraic Topology, but software based on these theories have been development too. On one hand, Pe˜na-Cantillana et al. in [32] generate a parallel software using Notes on MC and Image Processing 115 GPUs by CUDA to get the homology groups of 2D shapes based on techniques of spanning trees generated with membrane models where the promoters are compulsory. On the other hand, Reina-Molina et al. use PyCUDA (Python plus CUDA) to solve homological problems in a practical way in [117]. But, the complexity to adapt the Morse theory to parallel algorithms is high. So, this last software is working almost completely parallel. Many open questions arise in the relation of Membrane Computing and Topology. From Algebraic Topology, we wonder if the Membrane Computing techniques can help for a better understanding of the problems and the design of more effective solutions. From Membrane Computing, a deeper study is necessary in order to explore how specific techniques of the different models can be applied. In particular, the use of priority in the application of rules is a strong requirement. It is worth to study if it can be avoided. From an implementation point of view, the exploration of the different parallel hardware architectures (clusters, grids, FPGA, . . . ) for the efficient implementation of the algorithms theoretically developed is an open research line. 6 An Example of Application Image analysis and processing have a great significance in the field of medicine, especially in non-invasive treatment and clinical study. However, with the development of new technologies, larger quantity of data, especially high quality images, is available. Therefore, there is a new necessity of efficient and fast algorithms capable of processing and extracting meaningful features from images in a reasonable time. This is the case of mass screening programs for the early detection of retinal diseases such as glaucoma or diabetic retinopathy. Visual inspection of the large number of images so obtained is a time consuming task for the medical experts. Moreover, CAD (Computer Aided Diagnosis) tools based on retinal image processing developed in the past are limited by the balance between accuracy and complexity due to their sequential programming. In [35], a fully automatized algorithm based on Membrane Computing techniques for the parallel segmentation of the optic disc in retinal fundus images was presented (see Fig. 5). The optic disc is seen on fundus color photographs as a bright yellowish disc in human retina from where the blood vessels and optic nerves emerge. Its relevance resides in the fact that it is a key point for the diagnosis of a wide variety of diseases such as glaucoma or diabetic retinopathy. Moreover, it is usually taken as a base for detecting other anatomical structures (macula, blood vessels) and retinal abnormalities (microaneurysms, hard exudates, drusens, etc.). Most of the methods found in the literature are semi-automatized. This means that the computer treatment is crucial in the localization and detection of the optic disc, but the human expert is the one who takes the final decision. In this paper, a fully automatized method is presented where no human expert is necessary for the detection of the optic disc. 116 D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, H. Peng Fig. 5. Retinal image taken from the Standard Diabetic Retinopathy Database (DIARETDB1). The optic disc can be located as a yellow disc inside the image. Changes in the optic disc can indicate the current state and progression of a certain disease while its diameter is usually used as a reference for measuring retinal distances and sizes [128]. Therefore, accurate optic disc localization and detection of its boundary is a principal and basic step for automated diagnosis systems [94]. In [35], a new method has been implemented with the Graphics Processing Units (GPU) technology. Image edges are extracted using a new operator called AGP-color segmentator based on the Membrane Computing approach presented in [33]. It is a Membrane Computing implementation on CUDATM of the 3×3 and 5×5 versions of the Sobel algorithm [135] for edge detection. In order to choose an appropriate threshold to the binarization, a P system implementation [98] of the Hamadani algorithm [69] is applied. In order to avoid erroneous results, the obtained image is processed by eliminating the eye border. This is performed by applying a threshold on each color plane of the original image with the algorithm presented in [98]. The circular Hough transform is applied in parallel to the image in an interval of radius wide enough to consider all the possible optic discs. The Hough transform is a well-known feature extraction technique used in image analysis. The classical Hough transform was concerned with the identification of lines in the image, but later the Hough transform has been extended to identifying positions of arbitrary shapes, most commonly circles or ellipses [4, 40, 73]. The basic idea behind the Hough transform is to convert the image into a parameter space that is constructed specifically to describe the desired shape analytically. The reliability of the tool was tested with 129 images from the public databases DRIVE [136] and DIARETDB1 [75] obtaining an average accuracy of 99.6% and a Notes on MC and Image Processing 117 mean consumed time per image of 7.6 and 16.3 sec. respectively. A comparison with several state-of-the-art algorithms shows that the algorithm represents a significant improvement in terms of accuracy and efficiency. 7 Final Conclusions Parallelizing classical digital image algorithms is a big challenge in the years to come [29, 97]. Such paralleling is much more complex than the merely simultaneous application of the sequential algorithm to different pieces of the image. The coordination of different simultaneous processes in a whole algorithm is so hard task that commonly the parallel algorithm needs to be re-designed with only slight references to the classical one. Usually, the design of a new parallel implementation not inspired by the sequential one allows an open-mind vision of the problem and the proposal of new creative solutions. Such new parallel solutions needs a strong theoretical support that allows to control, to formalize, to check and to formally verify new algorithms. As pointed out above, many of the problems in digital images share features very interesting for using these techniques: the information can be split into little pieces and expressed as (multi)sets of objects; the computation steps can be processed by rewriting rules; and the same sequential algorithm must be applied in different regions of the image which are independent and they can be treated locally by a set of processors. All these features lead us to consider Membrane Computing to deal with digital images. The key point of paralleling classical sequential algorithms is the search of the efficiency and this efficiency is strongly linked to the development of new parallel hardware architectures which allows a realistic implementation of the theoretical advantages of the parallel processes. Different hardware architectures (clusters, grids, FPGA, . . . ) propose different solutions [78, 79, 93, 127]. One of the most used architectures in the papers presented above has been the Compute Unified Device Architecture, CUDATM. This is a general purpose parallel computing architecture that allows the parallel NVIDIA Graphics Processing Units (GPUs) to solve many complex computational problems in a more efficient way than on a CPU. GPUs have emerged as general-purpose coprocessors in recent years. Traditionally designed for gaming applications, GPUs offers many computing threads arranged in a Single-program Multiple-data (SPMD) model. The chosen hardware architecture for our parallel implementation has been the Compute Unified Device Architecture, (CUDAT M ), which allows the parallel NVIDIA GPUs [155] to solve many complex computational problems in a more efficient way than on a sequential Central Processing Unit (CPU)6. This architecture has been widely used in Membrane Computing not only for dealing with images [12, 13]. The choice of this parallel architecture is supported by several reasons. The first one is that the computing language CUDATM allows programmers a friendly model 6For a good overview, the reader can refer to [95]. 118 D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, H. Peng for implementing easily parallel programs, but the main reason comes from the practical side. In the last years, there exists an increasing interest in the specialized industry for the development of more and more powerful Graphic Processing Units which can be used for general purposes. This interest leads, on the one hand, to a more economically accessible (and hence, more extended) hardware and, on the other hand, to the development of more powerful computational units. The use of this new parallel architecture is currently explored as a tool for paralleling the treatment of digital images [11, 90]. Many other problems related to digital images have been addressed with Membrane Computing techniques. We can cite smoothing [99] which study how to enhance an image by removing regions which do not provide relevant information, the approach presented in [150], where Membrane Computing and quantum-inspired evolutionary algorithms are combined or the search of partially bounded regions [19]. This problem is also related to the HGB2I problem which consists on calculating the number of connected components and the representative curves of the holes of these components. Special attention deserves the work by Gimel’farb et al. [56, 58], where the symmetric dynamic programming stereo (SDPS) algorithm [57] for stereo matching was implemented by using Membrane Computing techniques. Many other approaches not cited in this paper have also been reported in the literature. This research area is rather active and it provides many lines for future researchers. Many open questions about new P system models, new digital image problems, new real-life application cases or new architectures will need deep studies in the next years. References 1. Adeoye, O.S.: A survey of emerging biometric technologies. International Journal of Computer Applications 9(10), 1–5 (November 2010) 2. Annadurai, S., Kalyani, T., Dare, V.R., Thomas, D.G.: P systems generating isopicture languages. Progress in Natural Science 18(5), 617 – 622 (2008) 3. Ayache, N.: Medical image analysis and simulation. In: Shyamasundar, R.K., Ueda, K. (eds.) ASIAN. Lecture Notes in Computer Science, vol. 1345, pp. 4–17. Springer (1997) 4. Ballard, D.: Generalizing the Hough transform to detect arbitrary shapes. Pattern Recognition 13(2), 111 – 122 (1981) 5. Blum, H.: An associative machine for dealing with the visual field and some of its biological implications. In: Bernard, E.E., Kare, M.R. (eds.) Biological Prototypes and Synthetic Systems. vol. 1, pp. 244–260. Plenum Press, New York (1962), proceedings of the 2nd Annual Bionics Symposium, held at Cornell University, 1961. 6. Blum, H.: An associative machine for dealing with the visual field and some of its biological implications. Computer and Mathematical Sciences Laboratory, Electronics Research Directorate, Air Force Cambridge Research Laboratories, Office of Aerospace Research, United States Air Force (1962) Notes on MC and Image Processing 119 7. Borrego-Ropero, R., D´ıaz-Pernil, D., P´erez-Jim´enez, M.J.: Tissue simulator: A graphical tool for tissue P systems. In: Vaszil, G. (ed.) Proceedings of the International Workshop Automata for Cellular and Molecular Computing. pp. 23–34. MTA SZTAKI, Budapest, Hungary (August 2007), satellite of the 16th International Symposium on Fundamentals of Computational Theory 8. Campadelli, P., Casiraghi, E., Esposito, A.: Liver segmentation from computed tomography scans: A survey and a new algorithm. Artificial Intelligence in Medicine 45(2-3), 185–196 (2009) 9. Carnero, J., D´ıaz-Pernil, D., Guti´errez-Naranjo, M.A.: Designing tissue-like P systems for image segmentation on parallel architectures. In: Mart´ınez-del-Amor, M.A., P˘aun, Gh., P´erez-Hurtado, I., Romero-Campero, F.J., Valencia-Cabrera, L. (eds.) Ninth Brainstorming Week on Membrane Computing. pp. 43–62. F´enix Editora, Sevilla, Spain (2011) 10. Carnero, J., D´ıaz-Pernil, D., Molina-Abril, H., Real, P.: Image segmentation inspired by cellular models using hardware programming. Image-A: Applicable Mathematics in Image Engineering 1(3), 143–150 (2010) 11. Carranza, C., Murray, V., Pattichis, M., Barriga, E.S.: Multiscale AM-FM decompositions with GPU acceleration for diabetic retinopathy screening. In: Image Analysis and Interpretation (SSIAI), 2012 IEEE Southwest Symposium on. pp. 121–124 (2012) 12. Cecilia, J.M., Garc´ıa, J.M., Guerrero, G.D., Mart´ınez-del-Amor, M.A., P´erez- Hurtado, I., P´erez-Jim´enez, M.J.: Simulating a P system based efficient solution to SAT by using GPUs. Journal of Logic and Algebraic Programming 79(6), 317– 325 (2010) 13. Cecilia, J.M., Garc´ıa, J.M., Guerrero, G.D., Mart´ınez-del-Amor, M.A., P´erez- Hurtado, I., P´erez-Jim´enez, M.J.: Simulation of P systems with active membranes on CUDA. Briefings in Bioinformatics 11(3), 313–322 (2010) 14. Ceterchi, R., Gramatovici, R., Jonoska, N., Subramanian, K.G.: Tissue-like P systems with active membranes for picture generation. Fundamenta Informaticae 56(4), 311–328 (2003) 15. Ceterchi, R., Mutyam, M., P˘aun, Gh., Subramanian, K.G.: Array-rewriting P systems. Natural Computing 2(3), 229–249 (2003) 16. Chang, Y., Li, X.: Adaptive image region-growing. IEEE Trans. Image Processing 3(6), 868–872 (1994) 17. Chao, J., Nakayama, J.: Cubical singular simplex model for 3D objects and fast computation of homology groups. In: 13th International Conference on Pattern Recognition (ICPR’96). vol. IV, pp. 190–194. IEEE Computer Society, IEEE Computer Society, Los Alamitos, CA, USA (1996) 18. Cheng, H., Jiang, X., Sun, Y., Wang, J.: Color image segmentation: advances and prospects. Pattern Recognition 34(12), 2259–2281 (2001) 19. Christinal, H.A., Berciano, A., D´ıaz-Pernil, D., Guti´errez-Naranjo, M.A.: Searching partially bounded regions with P systems. In: Pant, M., Deep, K., Nagar, A., Bansal, J.C. (eds.) Proceedings of the Third International Conference on Soft Computing for Problem Solving: SocProS 2013, Volume 1. pp. 45–54. Springer India, New Delhi (2014) 20. Christinal, H.A., D´ıaz-Pernil, D., Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J.: Array tissue-like P systems. In: Mart´ınez del Amor, M.A., P˘aun, Gh., P´erez Hurtado, I., Riscos-N´u˜nez, A. (eds.) Eighth Brainstorming Week on Membrane Computing. pp. 37–51. F´enix Editora, Sevilla, Spain (2010) 120 D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, H. Peng 21. Christinal, H.A., D´ıaz-Pernil, D., Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J.: Thresholding of 2D images with cell-like P systems. Romanian Journal of Information Science and Technology (ROMJIST) 13(2), 131–140 (2010) 22. Christinal, H.A., D´ıaz-Pernil, D., Real, P.: Segmentation in 2D and 3D image using tissue-like P system. In: Bayro-Corrochano, E., Eklundh, J.O. (eds.) Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications 14th Iberoamerican Conference on Pattern Recognition, CIARP 2009, Guadalajara, Jalisco, Mexico, November 15-18, 2009. Proceedings. Lecture Notes in Computer Science, vol. 5856, pp. 169–176. Springer, Berlin Heidelberg (2009) 23. Christinal, H.A., D´ıaz-Pernil, D., Real, P.: Using membrane computing for obtaining homology groups of binary 2D digital images. In: Wiederhold, P., Barneva, R.P. (eds.) Combinatorial Image Analysis 13th International Workshop, IWCIA 2009, Playa del Carmen, Mexico, November 24-27, 2009. Proceedings. Lecture Notes in Computer Science, vol. 5852, pp. 383–396. Springer, Berlin Heidelberg (2009) 24. Christinal, H.A., D´ıaz-Pernil, D., Real, P.: P systems and computational algebraic topology. Mathematical and Computer Modelling 52(11-12), 1982 – 1996 (December 2010), the BIC-TA 2009 Special Issue, International Conference on Bio-Inspired Computing: Theory and Applications 25. Christinal, H.A., D´ıaz-Pernil, D., Real, P.: Region-based segmentation of 2D and 3D images with tissue-like P systems. Pattern Recognition Letters 32(16), 2206 – 2212 (2011), advances in Theory and Applications of Pattern Recognition, Image Processing and Computer Vision. 26. Christinal, H.A., D´ıaz-Pernil, D., Real Jurado, P., Selvan, S.E.: Color segmentation of 2D images with thresholding. In: Mathew, J., Patra, P., Pradhan, D.K., Kuttyamma, A.J. (eds.) Eco-friendly Computing and Communication Systems: International Conference, ICECCS 2012, Kochi, India, August 9-11, 2012. Proceedings. pp. 162–169. Springer, Berlin, Heidelberg (2012) 27. Collins, R., Lipton, A., Kanade, T.: Introduction to the special section on video surveillance. Pattern Analysis and Machine Intelligence, IEEE Transactions on 22(8), 745 –746 (aug 2000) 28. Cook, C.R., Wang, P.S.P.: A Chomsky hierarchy of isotonic array grammars and languages. Computer Graphics and Image Processing 8(1), 144 – 152 (1978) 29. Davies, E.: Computer and Machine Vision: Theory, Algorithms, Practicalities. Elsevier Science, Waltham, Mass. (2012) 30. Dersanambika, K.S., Krithivasan, K.: Contextual array P systems. International Journal of Computer Mathematics 81(8), 955–969 (2004) 31. Dersanambika, K.S., Krithivasan, K., Subramanian, K.G.: P systems generating hexagonal picture languages. In: Mart´ın-Vide, C., Mauri, G., P˘aun, Gh., Rozenberg, G., Salomaa, A. (eds.) Membrane Computing, International Workshop, WMC 2003, Tarragona, Spain, July 17-22, 2003, Revised Papers. Lecture Notes in Computer Science, vol. 2933, pp. 168–180. Springer, Berlin Heidelberg (2003) 32. D´ıaz-Pernil, D., Berciano, A., Pe˜na-Cantillana, F., Guti´errez-Naranjo, M.A.: Bioinspired parallel computing of representative geometrical objects of holes of binary 2D-images, in press 33. D´ıaz-Pernil, D., Berciano, A., Pe˜na-Cantillana, F., Guti´errez-Naranjo, M.A.: Segmenting images with gradient-based edge detection using membrane computing. Pattern Recognition Letters 34(8), 846 – 855 (2013) Notes on MC and Image Processing 121 34. D´ıaz-Pernil, D., Christinal, H.A., Guti´errez-Naranjo, M.A., Real, P.: Using Membrane Computing for Effective Homology. Applicable Algebra in Engineering, Communication and Computing 23(5-6), 233–249 (2012) 35. D´ıaz-Pernil, D., Fond´on, I., Pe˜na-Cantillana, F., Guti´errez-Naranjo, M.A.: Fully automatized parallel segmentation of the optic disc in retinal fundus images. Pattern Recognition Letters 83, Part 1, 99 – 107 (2016), Geometric, Topological and Harmonic Trends to Image Processing 36. D´ıaz-Pernil, D., Guti´errez-Naranjo, M.A., Molina-Abril, H., Real, P.: A bio-inspired software for segmenting digital images. In: Nagar, A.K., Thamburaj, R., Li, K., Tang, Z., Li, R. (eds.) Fifth International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2010, University of Hunan, Liverpool Hope University, Liverpool, United Kingdom / Changsha, China, September 8-10 and September 23-26, 2010. vol. 2, pp. 1377 – 1381. IEEE Computer Society, Beijing, China (2010) 37. D´ıaz-Pernil, D., Guti´errez-Naranjo, M.A., Real, P., S´anchez-Canales, V.: Computing homology groups in binary 2D imagery by tissue-like P systems. Romanian Journal of Information Science and Technology 13(2), 141–152 (2010) 38. D´ıaz-Pernil, D., Pe˜na-Cantillana, F., Guti´errez-Naranjo, M.A.: Skeletonizing images by using spiking neural P systems. In: Mart´ınez-del-Amor, M.A., P˘aun, Gh., P´erez- Hurtado, I., Romero-Campero, F.J. (eds.) Tenth Brainstorming Week on Membrane Computing. vol. I, pp. 91–110. F´enix Editora, Sevilla, Spain (2012) 39. D´ıaz-Pernil, D., Pe˜na-Cantillana, F., Guti´errez-Naranjo, M.A.: A parallel algorithm for skeletonizing images by using spiking neural P systems. Neurocomputing 115, 81 – 91 (2013) 40. Duda, R.O., Hart, P.E.: Use of the Hough transformation to detect lines and curves in pictures. Communications of the ACM 15(1), 11–15 (1972) 41. Dufresne, T.E., Sarwal, A., Dhawan, A.P.: A gray-level thinning method for delineation and representation of arteries. Computerized Medical Imaging and Graphics 18(5), 343 – 355 (1994) 42. Egmont-Petersen, M., de Ridder, D., Handels, H.: Image processing with neural networks - a review. Pattern Recognition 35(10), 2279–2301 (2002) 43. Eilenberg, S., MacLane, S.: Relations between homology and homotopy groups of spaces. The Annals of Mathematics 46(3), pp. 480–509 (1945) 44. Eilenberg, S., MacLane, S.: Relations between homology and homotopy groups of spaces. II. The Annals of Mathematics 51(3), pp. 514–533 (1950) 45. Fernau, H., Freund, R., Schmid, M.L., Subramanian, K.G., Wiederhold, P.: Contextual array grammars and array P systems. Annals of Mathematics and Artificial Intelligence 75(1-2), 5–26 (2015) 46. Ferretti, C., Mauri, G., Zandron, C.: P systems with string objects. In: P˘aun et al. [109], pp. 168 – 197 47. Freedman, D., Chen, C.: Algebraic topology for computer vision. Science And Technology (2009) 48. Freund, R.: Array grammars. Tech. Rep. 15/00, Research Group on Mathematical Linguistics, Rovira i Virgili University, Tarragona (2000) 49. Frijters, D., Lindenmayer, A.: A model for the growth and flowering of aster novaeangliae on the basis of table <1, 0 >L-systems. In: Rozenberg, G., Salomaa, A. (eds.) L Systems, Most of the papers were presented at a conference in Aarhus, Denmark, January 14-25, 1974. Lecture Notes in Computer Science, vol. 15, pp. 24–52. Springer (1974) 128 D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, H. Peng 154. Zhou, Y., Chellappa, R.: Artificial neural networks for computer vision. Research notes in neural computing, Springer-Verlag (1992) 155. NVIDIA Corporation. NVIDIA CUDAtm Programming Guide. http://www.nvidia.com/ (2012) P Colonies Lucie Ciencialov´a1, Erzs´ebet Csuhaj-Varj´u2, Ludˇek Cienciala1, and Petr Sos´ık1 1Institute of Computer Science and Research Institute of the IT4Innovations Centre of Excellence, Silesian University in Opava, Czech Republic {lucie.ciencialova, ludek.cienciala, petr.sosik}@fpf.slu.cz 2Department of Algorithms and Their Applications, Faculty of Informatics, E¨otv¨os Lor´and University, Budapest, Hungary [email protected] Summary. P colonies are abstract computing devices modelling communities of very simple reactive agents (cells) living and acting in a joint shared environment. The concept was motivated by colonies, grammar systems based on interplay of very simple agents, on one hand, and by membrane systems, massively parallel computational models inspired by cell biology, on the other hand. Some variants of P colonies also allow the environment to participate actively in the system’s evolution. In this paper we summarize the most important results on P colonies, present open problems concerning these constructs, and suggest new research directions in their study. 1 Introduction In contemporary computer science, there has been a growing demand for reliable and efficient computing devices to describe the behaviour of communities of dynamically changing agents which are in interaction with their shared environment. Multi-agent systems with very simple reactive agents are of special interest, in particularly with respect to their emerging behaviour and the limits of their power. P colonies, introduced in [25], were motivated by these problems. They are variants of very simple tissue-like P systems, where the agents (the cells) have only one region and they interact with their shared environment by using programs (collections of rules of special form). P systems (or membrane systems), introduced in [30], are a family of computing devices inspired by biology and biochemistry of cells. Colonies of simple formal grammars, also motivating P colonies, were introduced in [23]. During the years, P colonies have been studied in detail; a summary of results can be found in [26]. Although several variants of P colonies have been developed, all of them have some common basic features. Inside each agent (each cell) there is a finite multiset of objects. These objects are processed by a finite set of programs associated to the 130 L. Ciencialov´a et al. agent. The number of objects inside each agent is constant (does not change) during the functioning of the agent community and it is called the capacity of the P colony. The agents share an environment which is represented by a multiset of objects. One type of these objects, called the environmental object, is distinguished, and it is supposed to be in a countably infinite number of copies in the environment. (In the literature, the reader may also find that the environmental symbol appears in an arbitrarily large number of copies in the environment). Using their programs, the agents can change the objects present at their disposal and can exchange some of their objects with objects present in the environment. These synchronized actions correspond to a configuration change (a transition) of the P colony; a finite sequence of consecutive configuration changes starting from the initial configuration is a computation. The result of the computation is the number of copies of a distinguished object, called the final object, present in the environment in a final configuration of the P colony. It can easily be seen that the environment is both a communication channel for the agents and a storage for the objects. It plays strategic role in synchronizing the work of the agents during the computation. One major research topic in the theory of P colonies is the study of their computational power related to their descriptional complexity. These investigations focus on that questions how many components are necessary and how much extent the programs can be simplified to obtain a certain computational power. In addition to these problems, the working modes of P colonies have obtained attention as well, whether or not parallelism in the joint work of the agents plays significant role in increasing the expressive power of P colonies. The rules of P colonies demonstrate strong similarities with instructions or rules of some well-known computing devices (register machines, rewriting systems based on point mutations, other variants of membrane systems), thus comparisons of these constructs with other classical and non-classical computing devices are also of interest. P colonies, due to their original motivation, model multi-agent systems (complex systems) acting in an environment. According to the basic definitions, the objects present in the environment have significant role in the change of the states of the agents. Therefore, one of the research directions in the theory is devoted to studying the role of the dynamics of the environment in the behaviour of P colonies, i.e., the case when the objects in the environment are provided step-by- step not only by the actions of the agents but by some special object provider device. Due to their simplicity and distributed nature, P colonies are convenient tools for modelling complex systems as robot collections, sender and consumer systems, eco-systems. We expect several new areas of applications in the future. P Colonies 131 2 Notations We assume that the reader is familiar with formal language and automata theory, computability, and the basics of membrane computing [31, 29]. Throughout the paper we use the following notions and notations. Let Σbe the alphabet and let Σ∗be the set of all words over Σ(including the empty word ε). The length of a word w∈Σ∗is denoted by |w|and the number of occurrences of the symbol a∈Σin wby |w|a. A multiset of objects Mis a pair M= (V, f), where Vis an arbitrary (not necessarily finite) set of objects and fis a mapping f:V→N;fassigns to each object in Vits multiplicity in M. Each multiset of objects Mwith the set of objects V′={a1, . . . an}can be represented as a string wover alphabet V′, where |w|ai=f(ai); 1 ≤i≤n. Obviously, all words obtained from wby permuting the letters represent the same multiset M. Symbol εrepresents the empty multiset. The set of all multisets with the set of objects Vis denoted by V∗. The cardinality of M, denoted by |M|, is defined by |M|=∑a∈Vf(a). The set of all non-negative integers is denoted by N. We use REG,CF and RE as notations for the families of regular, context-free and recursively enumerable languages. The family of languages accepted by matrix grammars without appearance checking and with erasing rules is denoted by MATϵand the family of interactionless L systems is denoted by 0L.NRE denotes the family of recursively enumerable set of non-negative integers. Definition 1. [28] A register machine is a construct M= (m, H, l0, lh, P)where: -mis the number of registers, -His the set of instruction labels, -l0is the start label, -lhis the final label, -Pis a finite set of instructions injectively labeled with the elements from the set H. The instruction of the register machine are of the following forms: l1: (ADD(r), l2, l3) Add 1 to the content of the register rand proceed to the instruction (labeled with) l2or l3. l1: (SUB(r), l2, l3) If the register rstores the value different from zero, then subtract 1 from its content and go to instruction l2, otherwise proceed to instruction l3. lh:HALT Halt the machine. The final label lhis only assigned to this instruction. Without loss of generality, one can assume that in each ADD-instruction l1: (ADD(r), l2, l3) and in each SUB-instruction l1: (SUB(r), l2, l3) the labels l1, l2, l3 are mutually distinct. The register machine Mcomputes a set N(M) of numbers in the following way: it starts with all registers empty (hence storing the number zero) with the instruction labelled l0and it proceeds to apply the instructions as indicated by the labels 132 L. Ciencialov´a et al. (and made possible by the contents of registers). If it reaches the halt instruction, then the number stored at that time in the register 1 is said to be computed by Mand hence it is introduced in N(M). It is known (see e.g. [28]) that in this way we compute all Turing computable sets of numbers. The register machine is called partially bind if the SUB-instruction is executed as follows: If register rstores a non-zero value then this value is decreased by one and the next instruction will be l2or l3, otherwise the computation aborts. When the partially blind register machine enters the final state, the result obtained in the first register is only taken into account if the remaining registers store value zero. The family of sets of non-negative integers generated by partially blind register machines is denoted by NRM pb. The partially blind register machines accept a proper subfamily of NRE. 3 The basic model of P colonies The original concept of a P colony was introduced in [25] and presented in a developed form in [24, 16]. Definition 2. A P colony of capacity k,k≥1, is a construct Π= (A, e, f, vE, B1, . . . , Bn), where •Ais an alphabet, its elements are called objects; •e∈Ais the basic (or environmental) object of the colony; •f∈Ais the final object of the colony; •vEis a finite multiset over A− {e}, called the initial state (or initial content) of the environment; •Bi,1≤i≤n, are agents, where each agent Bi= (oi, Pi)is defined as follows: –oiis a multiset over Aconsisting of kobjects, the initial state (or the initial content) of the agent; –Pi={pi,1, . . . , pi,ki}is a finite set of programs, where each program consists of krules, which are in one of the following forms each: ·a→b,a, b ∈A, called an evolution rule; ·c↔d,c, d ∈A, called a communication rule; ·r1/r2, called a checking rule; r1, r2are both evolution rules or both communication rules. We add some brief explanations to the components of the P colony. We first note that throughout the paper, we use term ”object ainside agent B” and term ”a∈w, where wis the state of agent B” as equivalent. The first type of rules associated to the programs of the agents, the evolution rules, are of the form a→b. This means that object ainside the agent is rewritten to (evolved to be) object b. The second type of rules, the communication rules, are of the form c↔d. If a communication rule is performed, then object cinside the agent and object din P Colonies 133 the environment agent swap their location. Thus, after executing the rule, object dappears inside the agent and object cis located in the environment. The third type of rules are the checking rules. A checking rule is formed from two rules of one of the two previous types. If a checking rule r1/r2is performed, then the rule r1has higher priority to be executed over the rule r2. This means that the agent checks whether or not rule r1is applicable. If the rule can be executed, then the agent must use this rule. If rule r1cannot be applied, then the agent uses rule r2. We note that these types of rules are the basic ones; in some variants of P colonies other types of rules have been also considered. We will discuss them in later sections. The program determines the activity of the agent: the agent can change its state and/or the state of the environment. The environment is represented by a finite number (zero included) of copies of non-environmental objects and a countably infinite copies of the environmental object e. In every step, each object inside the agent is affected by the execution of a program. Depending on the rules in the program, the program execution may affect the environment as well. This interaction between the agents and the environment is the key factor of the functioning of the P colony. The functioning of the P colony starts from its initial configuration (initial state). The initial configuration of a P colony is an (n+1)-tuple of multisets of objects present in the P colony at the beginning of the computation. It is given by the multisets oifor 1 ≤i≤nand by multiset vE. Formally, the configuration of the P colony Πis given by (w1, . . . , wn, wE), where |wi|=k, 1≤i≤n,wirepresents all the objects present inside the i-th agent, and wE∈(A− {e})∗represents all the objects in the environment different from the object e. At each step of the computation (at each transition), the state of the environment and that of the agents change in the following manner: In the maximally parallel derivation mode, each agent which can use any of its programs should use one (non-deterministically chosen), whereas in the sequential derivation mode, one agent uses one of its programs at a time (non-deterministically chosen). If the number of applicable programs for an agent is higher than one, then the agent non-deterministically chooses one of the programs. A sequence of transitions is called a computation. A computation is said to be halting, if a configuration is obtained where no program can be applied anymore. With a halting computation, we associate a result which is given as the number of copies of the objects fpresent in the environment in the halting configuration. Because of the non-determinism in choosing the programs, starting from the initial configuration we obtain several computations, hence, with a P colony we can associate a set of numbers, denoted by N(Π), computed by all possible halting computations of given P colony. 134 L. Ciencialov´a et al. In the original model (see [25]) the number of objects inside each agent is set to two. Therefore, the programs were formed from only two rules. Moreover, the initial configuration was defined as (n+ 1)-tuple (ee, . . . , ee, ε) so at the beginning of the computation the environment of the P colony is “empty”, it is without an input information. The number of agents in a given P colony is called the degree of Π; the maximal number of programs of an agent of Πis called the height of Πand the number of the objects inside an agent is the capacity of Π. The family of all sets of numbers N(Π) computed as above by P colonies of capacity at most c≥0, degree at most n≥0 and height at most h≥0, using checking programs, and working in the sequential mode is denoted by NPCOLseqK(c, n, h); whereas the corresponding families of P colonies working in the maximally parallel way are denoted by NPCOLparK(c, n, h). If one of the parameters nand his not bounded, then we replace it with ∗. If only P colonies using programs without checking rules are considered, then we omit parameter K. 4 Computational power of P colonies Although P colonies are very simple computing devices, due to their (mainly parallel) working mode and distributed nature they demonstrate large expressive (computational) power. In most cases, computational completeness can be obtained with these constructs even with a very few components and a very few restrictions on the programs. In this section, we briefly summarize some important results concerning their expressive power. Most of the statements are based on simulations of register machines, thus providing further knowledge on the nature of these classical computing devices as well. To demonstrate a connection between P colonies and register machines, we add an example how the ADD-instruction of a register machine can be simulated by a P colony. Example 1. Let Π= (A, e, f, vE, B) be the P colony with capacity two and let the current content of the agent be l1e. Let M= (m, H, l0, lh, P) be a non-deterministic register machine with mregisters. The ADD-instruction l1= (ADD(r), l2, l3) of Mcan be simulated by the following programs associated with the agent: P: 1 : ⟨l1→l′ 1;e→ar⟩; 2 : ⟨l′ 1→l2;ar↔e⟩; 3 : ⟨l′ 1→l3;ar↔e⟩; At the beginning, objects l1and eare placed inside the agent. The content of register ris encoded to the number of objects arplaced in the environment. The computation is done in such a way that the agent rewrites its content to l′ 1arby using the first program (there are two rewriting rules in it). In the second step the agents rewrites l′ 1to object corresponding to the label of the next instruction l2( or l3) to be executed and it puts object arinto the environment. P Colonies 135 4.1 Restricted P colonies By [25], P colonies of capacity two are computationally complete. Furthermore, their programs have special forms: one of the rules is an evolution rule and the other one is either a communication rule or a checking rule with two communication rules. These variants of P colonies are called restricted P colonies. The family of all sets of numbers computed by restricted P colonies without checking rules and with parameters c, n, h and working modes par and seq, see above, is denoted by NP COLparR(c, n, h) or NPCOLseqR(c, n, h), respectively. If the restricted P colonies are with checking rules, then we add Kin front of R. Let us have one more example. Example 2. Let Π= (A, e, f, vE, B) be the P colony with capacity two and let the current contents of the agent be l1e. Let M= (m, H, l0, lh, P ) be a non-deterministic register machine with mregisters. The ADD-instruction l1= (ADD(r), l2, l3) can be simulated by the following programs associated with the agent: P: 1 : ⟨e→ar;l1↔e⟩; 3 : ⟨l1→l2;d↔e⟩; 2 : ⟨e→d;ar↔l1⟩; 4 : ⟨l1→l3;d↔e⟩; At the beginning, objects l1and eare inside the agent. The content of register r is encoded to the number of objects arplaced in the environment. The computation is done in such a way that at one computational step the agent must rewrite one of the objects inside it and should exchange the other one with an object from the environment. At the first step the agent rewrites eto object arand sends object l1into the environment. In the second step it rewrites eto auxiliary object dand exchanges object arand l1from the environment. At the last step the agent rewrites object l1to the object corresponding to the label of the next instruction l2( or l3) to be executed and it puts object dinto the environment. For restricted P colonies, using the maximally parallel working mode, the following results hold: •NPCOLparKR(2,∗,5) = NRE in [16, 25], •NPCOLparR(2,∗,5) = NRE in [18], •NPCOLparK(2,∗,4) = NRE in [16], •NPCOLparKR(2,1,∗) = NRE in [18], •NPCOLparR(2,2,∗) = NRE in [8]. The reader can easily see that the family of sets of natural numbers computed by restricted P colonies with or without the use of checking rules having at most five programs associated with agent equals to NRE. If we remove the restriction on the type of rules in the programs, P colonies need only at most four programs associated with every agent to obtain computational completeness. The difference in the last two results demonstrates the power of checking rules and the power 136 L. Ciencialov´a et al. of synchronized cooperation. To generate NRE, the restricted P colonies need only one agent if the agent can use checking rules and two agents if they are not equipped with checking rules. The maximally parallel application of rules does not necessarily add power, as the following results demonstrate: •NPCOLseqKR(2,∗,5) = NRE in [18], •NPCOLseqKR(2,1,∗) = NRE in [18], •NPCOLseqK(3,∗,6) = NRE in [16, 24]. However, if only restricted P colonies with the sequential working modes are considered, the maximal computation power to be obtained is equal to the recognition power of blind counter machines, thus significantly reduced, irrespectively from the number of programs and agents in the P colony. Notice that the property ”restricted” demonstrates strong similarity to some normal forms of variants of regulated grammars, where some of the production is used for programming the action and some other production is responsible for its execution. By using some well-organized synchronizing mechanisms, simulation of standard P colonies with restricted ones can be demonstrated, thus, we may consider restricted P colonies as ”normal forms” for the family of P colonies. We note that the idea of restriction can be extended, with prescribing the ratio of evolution and communication rules in the programs of capacity k,k≥2. 4.2 Homogeneous P colonies If each program in the P colony consists of rules of the same type (for a P colony with capacity two, this means that the program is formed from two evolution rules, or two communication rules or two checking rules of the same type), then we can call the P colony homogeneous. Indicating by symbol Hthat homogeneous P colonies are considered, the following results were obtained: •NPCOLparKH(2,∗,4) = NRE in [9], •NPCOLparKH(2,1,∗) = NRE in [9]. As for the previous variants, we provide an example. Example 3. Let Π= (A, e, f, vE, B) be the P colony with capacity two and let the current content of the agent be l1e. Let M= (m, H, l0, lh, P) be a non-deterministic register machine with mregisters. The ADD-instruction l1= (ADD(r), l2, l3) can be simulated by the following programs associated with the agent: P: 1 : ⟨l1→l′ 1;e→ar⟩; 4 : ⟨l′ 1→l2;e→e⟩; 2 : ⟨l′ 1↔e;ar↔e⟩; 5 : ⟨l′ 1→l3;e→e⟩; 3 : ⟨e↔l′ 1;e↔e⟩; P Colonies 137 At the beginning, objects l1and eare placed inside the agent. The content of register ris encoded to the number of objects arplaced in the environment. The computation is done in such a way that the agent at one computational step must rewrite all object inside it or must exchange all of its objects with objects from the environment. At the first step, the agent rewrites multiset l1eto multiset l′ 1ar. In the second step, it sends both objects of multiset l′ 1arinto the environment. At the third step, it consumes objects of multiset l′ 1eand at the last step the agent rewrites object l1to the object corresponding to the label of the next instruction to be executed, namely, l2(or l3). The results have been recalled so far concern mainly P colonies with agents of capacity at least two. It is a challenging question, whether the work of agents with capacity one, i.e., with agents having one rule in each program can be organized in such way that they obtain the same power as P colonies in the general sense. Notice that in this case the objects play more important rule in the synchronization of the work of the agents. The following results give positive answer to this question. •NPCOLparK(1,∗,5) = NRE in [10], •NPCOLparKH(1,∗,6) = NRE in [9], •NPCOLparK(1,4,∗) = NRE in [8], •NPCOLpar(1,6,∗) = NRE in [13]. Finally, we provide two more interesting results dealing with P colonies with capacity three [16, 4]. •NPCOLparK(3,∗,3) = NRE in [16], •NPCOLparH(3,2,∗) = NRE in [4]. In Table 1 the reader can find a summarized list of results concerning the computational complete variants of P colonies. 5 P colonies with prescribed teams P colonies with prescribed teams were introduced in [19]. Unlike the original variants of P colonies, the agents use finite sets of rules called teams instead of programs; with each agent a finite set of teams is given, with priorities (pri) among them. The used rules can be communicating (com), rewriting (rew), and so-called membrane rules (mem). The membrane rules are in a form ab(agoes out and becomes b) or ba(agoes in and becomes b). The P colony can work in sequential (seq) or parallel (par) manner. The rules are applied by the team in parallel manner with various stop conditions: ∗(stop after arbitrary number of derivation steps), ≤l,≥l, resp. = l(stop after at most l, at least lresp. after exactly lderivation steps) and t0(the team becomes inactive when it is no longer able to work as a team.) 144 L. Ciencialov´a et al. For each i, 1≤i≤n, we distinguish tape programs and non-tape programs. The set of tape programs (T-programs), denoted by PT i, are formed from one tape rule and k−1non-tape rules, the set of non-tape programs (N-programs) which contain only non-tape rules, is denoted by PN i, thus, Pi=PT i∪PN iand PT i∩PN i=∅. The computation starts in the initial configuration, i.e., when the input word is on the input tape and all agents are in initial state. For a configuration (wE, w1, . . . , wn) and an input symbol a, the sets of applicable programs, P, can be constructed. To pass from one configuration to some other one in one step we define the following types of transitions: •t-transition ⇒a t: There exists at least one set of applicable programs P∈ P such that every p∈Pis T-program with T-rule in the form xT →aor xT ↔a, x ∈A and the set Pis maximal. •n-transition ⇒n: There exists at least one set of applicable program P∈ P such that every pi∈Pis N-program and the set Pis maximal. •tmin-transition ⇒a tmin: If exists at least one set of applicable program P∈ P such that there is at least one T-program in Pin the form xT →aor xT ↔a, x ∈ Aand possibly N-programs. The set Pis maximal. •tmax-transition ⇒a tmax: There exists at least one set of applicable program P∈ P such that Pcontain as many T-programs (they are in a form xT →aor xT ↔a, x ∈A) as possible, Pcan contain N-programs too, and the set Pis maximal. We say that a PCol automaton works in t (tmax, tmin) mode of computation if it uses only t- (tmax-, tmin-) transitions. It works in nt (ntmax or ntmin) working mode if it uses t-(tmax- or tmin-) transitions and there is no set of applicable T-programs that can use n-transition. PCol automaton works in init mode if it performs only t-transitions and after reading all the input symbols it makes n-transitions. If the PCol automaton works in tn,tmax or tmin mode, then it reads one input symbol in every step of computation. Consequently, the length of the computation equals to the length of the input string. Notice that this property strongly resembles to some property of ε-free finite automata. The computation by a PCol automaton may end in a final state. It is successful if the whole input tape is read and the PCol automaton is in some configuration in F. Let M={t, nt, tmax, ntmax, tmin, ntmin, init}. The language accepted by a PCol automaton Π, given as above, is defined as the set of strings which can be read during a successful computation: L(Π, mode) = {w∈A∗|(w;vE, o1, . . . , on) can be transformed by Π into (ε;wE, w1, . . . , wn)∈Fwith a computation in mode mode ∈M}. Let L(PColA, mode) denote the class of languages accepted by PCol automata in the computational mode mode ∈M. P Colonies 145 Language classes of the Chomsky hierarchy can be described by PCol automata as follows [7]. •For every regular language Lthere exists a PCol automaton working in the t-mode having only one agent accepting all words from L. •There exists a context-free language that can be accepted by a PCol automaton with only one agent and working in the t-mode. •The family of languages accepted by PCol automata with one agent working in the t-mode is a subfamily of the family of context-sensitive languages. It is open question whether the family of context-sensitive languages is equal to the family of languages accepted by PCol automata with one agent working in the t-mode. Notice that unlike other variants of P colonies PCol automata working in the t-mode are not computationally complete. In [7], it was shown that class of languages accepted by PCol automata working in the nt, ntmin or ntmax mode equals to the class of recursively enumerable languages, respectively. The workspace needed to obtain this computational power is provided by the interaction between the agents and the environment. • L(PColA, nt) = RE in [7], • L(PColA, ntmin) = RE in [7], • L(PColA, ntmax) = RE in [7], • L(PColA, init) = NRE in [4]. In [22] the concept of a PCol automaton was generalized in the following manner: as in the case of the original model, the agents work in a maximally parallel way, but the agents are allowed to use any of their tape rules at every computation step. Those symbols that are read by the agents from the tape at a certain step of the computation form a multiset. If the symbols in this multiset form a prefix of the not-yet read part of the input, then this prefix of the input is considered to be read. The process continues until the whole string is read and no agent is able to apply any program. The class of languages accepted by generalized PCol automata where all the communication rules are tape rules are denoted by L(genP Col, com −tape), the class of languages accepted by generalized PCol automata with all programs having at least one tape rule by L(genPCol, all−tape), and, finally, the class of languages accepted by generalized PCol automata where the programs are with arbitrary types of rules are denoted by L(genPCol, ∗). In [22] it is shown that • L(genPCol, com −tape)∪ L(genPCol, all −tape)⊆ L(genPCol, ∗), • L(genPCol, com −tape)∩ L(genPCol, all −tape)− L(CF)=∅, • L(REG)⊂ L(genP Col, com −tape)∩ L(genPCol, all −tape). One of the most important results in [22] is L(genPCol, com −tape)∪ L(genPCol, all −tape)⊆r−1LOGSPACE, 146 L. Ciencialov´a et al. where r−1LOGSP ACE is a proper subclass of the class of languages accepted by Turing machines with a one-way input tape using logarithmic space on work tapes. The authors compare the accepting power of generalized PCol automata to standard P automata, constructs combining properties of antiport P systems and finite automata. For more information on P automata the reader is referred to Chapter 5 of [29]. 9 APCol systems In [6] the authors make one step further in combining properties of P colonies and automata. While the behaviour of the agents of PCol automata is determined both by the string to be processed and the environment consisting of multisets of symbols, in the case of APCol systems (Automaton-like P colonies), the agents act only on the input string. This interaction between the agents of the P colony and the input string is realized by exchanging symbols between the objects of the agents and that of the string (communication rules), and the states of the agents can change both by communication and evolution; the latter one is an application of a rewriting rule to an object. The distinguished symbol, e(in the previous models the environmental symbol) has a special role: whenever it is exchanged by a symbol in the environmental string, this symbol is erased. An evolution rule is of the form a→b. It means that object ainside the agent is rewritten (evolved) to the object b. The second type of rules are called communication rules. A communication rule is in the form c↔d. When this rule is performed, the object cinside the agent and a symbol din the string are exchanged, so, we can say that the agent rewrites symbol dto symbol cin the input string. If c=e, then the agent erases dfrom the input string and if d=e, symbol cis inserted into the string. The computation in APCol systems starts with an input string, representing the environment, and with each agents having only symbols ein their state. (Note that the initial states of the agents can be chosen not to consist of only e.) A computational step means a maximally parallel action of the active agents, i.e., agents that can apply their rules. Every symbol can be object of the action of only one agent. The computation ends if the input string is reduced to the empty word, there are no more applicable programs in the system, and meantime at least one of the agents is in so-called final state. Definition 5. An Automaton-like P colony (an APCol system, for short) is a construct Π= (A, e, B1, . . . , Bn),n≥1, where •Ais an alphabet; its elements are called the objects, •e∈A, called the basic object, •Bi,1≤i≤n, are agents. Each agent is a triplet Bi= (oi, Pi, Fi), where –oiis a multiset over A, describing the initial state (content) of the agent, |oi|= 2, P Colonies 147 –Pi={pi,1, . . . , pi,ki}is a finite set of programs associated with the agent, where each program is a pair of rules. Each rule is in one of the following forms: ·a→b, where a, b ∈A, called an evolution rule, ·c↔d, where c, d ∈A, called a communication rule, –Fi⊆A∗is a finite set of final states (contents) of agent Bi. As in the case of other variants of P colonies, the number of objects inside the agents are called the capacity of the APCol system, which is 2. During the work of the APCol system, the agents perform programs. Since both rules in a program can be communication rules, an agent can work with two objects in the string in one step of the computation. In the case of program ⟨a↔b;c↔d⟩, a substring bd of the input string is replaced by string ac. If the program is of the form ⟨c↔d;a↔b⟩, then a substring db of the input string is replaced by string ca. That is, the agent can act only in one place in one step of the computation and the change of the string depends both on the order of the rules in the program and on the interacting objects. In particular, we have the following types of programs with two communication rules: • ⟨a↔b;c↔e⟩-bin the string is replaced by ac, • ⟨c↔e;a↔b⟩-bin the string is replaced by ca, • ⟨a↔e;c↔e⟩-ac is inserted in a non-deterministically chosen place in the string, • ⟨e↔b;e↔d⟩-bd is erased from the string, • ⟨e↔d;e↔b⟩-db is erased from the string, • ⟨e↔e;e↔d⟩;⟨e↔e;c↔d⟩, . . . - these programs can be replaced by programs of type ⟨e→e;c↔d⟩. At the beginning of the computation of the APCol system the environment is given by a string ωof objects which are different from e. Consequently, an initial configuration of the APCol system is an (n+ 1)-tuple c= (ω;o1, . . . , on) where ω is the input string and the other ncomponents are multisets of strings of objects, given in the form of strings, the initial states the of agents. A configuration of an APCol system Πis given by (w;w1, . . . , wn), where |wi|= 2,1≤i≤n,wirepresents the state of the i-th agent and w∈(A− {e})∗ is the string to be processed. At each step of the (parallel) computation every agent attempts to find one of its programs to use. If the number of applicable programs is higher than one, the agent non-deterministically chooses one of them. At every step of the computation, the maximal possible number of agents have to be active, i.e., have to perform a program. By computation steps given above, the APCol system performs a transition, i.e., it passes from one configuration to some other configuration. A sequence of configurations started from the initial configuration is called a computation. A configuration is halting if the APCol system has no applicable program. A computation is called accepting if and only if at least one agent is in final state and 148 L. Ciencialov´a et al. the string to be processed is ε. Hence, the string ωis accepted by the APCol Πif there exists a computation by Πsuch that it starts in the initial configuration (ω;o1, . . . , on) and the computation ends by halting in the configuration (ε;w1, . . . , wn), where at least one of wi∈Fifor 1 ≤i≤n. The language Lacc(Π) accepted by Πis the set of words over (A− {e}) which are accepted by Π. APCol systems are powerful computational devices as it is shown in [6]: Let Abe an alphabet and let L⊆A∗be a recursively enumerable language. Let L′=S·L·E, where S, E /∈A. Then there exists an APCol system Πwith two agents such that L′=L(Π) holds. APCol systems can also be used not only for accepting but generating strings. A string wFis generated by an APCol system Πif there exists a computation starting in an initial configuration (ε;ee, . . . , ee) and the computation ends by halting in configuration (wF;w1, . . . , wn), where wi∈Fifor at least one wi, 1 ≤i≤n. The language Lgen(Π) generated by Πis the set of words over (A− {e}) which are generated by Π. In particularly important are those variants, where the programs are restricted (as defined for standard P colonies). We denote by APColaccR(n) (or APColacc(n)) the family of languages accepted by APCol systems having at most nagents, n≥1, with restricted programs only (or without this restriction). Analogously, we denote by APColgenR(n) the family of languages generated by APCol systems having at most nagents, n≥1, with restricted programs only, and APColgen(n) denotes the case when the programs are without any restriction. We may associate sets of numbers to APCol systems working in the generating or the accepting mode in the usual manner. For an APCol system Π,NLacc(Π) and NLgen(Π) denote the length sets of Lacc(Π) and Lgen(Π), respectively. The family of length sets of languages accepted or generated by restricted APCol systems with at most nagents, n≥1, is denoted by NAPColxR(n), x∈ {acc, gen}, respectively, and NAPColx(n) denotes the case when the programs are without any restriction. The following results were obtained in [6]: •NAPColgenR(2) = NRE. •NRMpb ⊆NAPColgenR(1). •APColgenR(1) ⊆MATε. •APColgenR(1) ⊂MATε. 10 2D P colonies In [11] a new model, called 2D P colony was introduced. As in the original model, the P colony is of capacity two and the agents are equipped with sets of the programs formed from rules – communication and evolution. The main change is in the environment. Namely, the authors put the agents into the 2D grid of square cells and they provide the agent with the possibility to move – the motion rule. P Colonies 149 The direction of the movement of the agent is determined by the contents of cells surrounding the cell in which the agent is placed. The program can contain at most one motion rule. To achieve the greatest simplicity in agent behaviour, one other condition was set. If the agent moves, it cannot communicate with the environment. So if the program contains a motion rule, then the other rule is an evolution rule. Definition 6. A 2D P colony is a construct Π= (A, e, Env, B1, . . . , Bk, f), k ≥1, where •Ais an alphabet of the colony, its elements are called objects, •e∈Ais the basic environmental object of the 2D P colony, •Env is a pair (m×n, wE), where m×n, m, n ∈Nis the size of the environment and wEis the initial contents of environment, it is a matrix of size m×nof multisets of objects over A− {e}. •Bi,1≤i≤k, are agents, each agent is a construct Bi= (oi, Pi,[o, p]) ,0≤ o≤m, 0≤p≤n, where –oiis a multiset over A, it determines the initial state (contents) of the agent, |oi|= 2, –Pi={pi,1, . . . , pi,li}, l ≥1,1≤i≤kis a finite set of programs, where each program contains exactly 2rules, which are in one of the following forms each: ·a→b, called the evolution rule, a, b ∈A, ·c↔d, called the communication rule, c, d ∈A, ·[aq,r]→s, 0≤q, r ≤2, s ∈ {⇐,⇒,⇑,⇓}, called the motion rule, •f∈Ais the final object of the colony. A configuration of the 2D P colony is given by the state of the environment - matrix of type m×nwith multisets of objects over A− {e}as its elements, and by the state of all agents - pairs of objects from alphabet Aand the coordinates of the agents. An initial configuration is given by the definition of the 2D P colony. A computational step consists of three parts. The first part lies in determining the applicable set of programs according to the actual configuration of the 2D P colony. There are programs belonging to all agents in this set of programs. In the second part we have to choose one program corresponding to each agent from the set of applicable programs. There is no collision between the communication rules belonging to different programs. The third part is the execution of the chosen programs. A change of the configuration is triggered by the execution of programs and it involves changing the state of the environment, contents and placement of the agents. A computation is non-deterministic and maximally parallel. The computation ends by halting when no agent has an applicable program. The result of the computation is the number of copies of the final object placed in the environment at the end of the computation. 150 L. Ciencialov´a et al. The aim of introducing 2D P colonies is not studying their computational power but monitoring their behaviour during the computation. In [11] an example for a 2D P colony simulating a kind of cellular automata – Conway’s Game of Life ([20]) is presented. The following example is the pattern called beacon (see Fig. 1). Fig. 1. Pattern beacon changes in two consecutive steps Let Π2be 2D P colony defined as follows: Π2= (A, e, Env, B1, . . . , B16, f), where •A={e, f, D, S, Z, M, O, L, N}, •e∈Ais the basic environmental object of the 2D P colony, •Env = (6 ×6, wE), •wE=         D D D D D D D S S D D D D S S D D D D D D S S D D D D S S D D D D D D D         , •B1= (ee, P1,[1,1]), B2= (ee, P2,[1,2]),. . . , B16 = (ee, P16,[4,4]), •f∈Ais the final object of the 2D P colony. The states of the automata are stored inside the cells ( D- dead automaton, S- live automaton ). There is only one kind of agent in this 2D P colony, so there are sixteen identical agents located in the matrix 4×4 of inner cells with following programs: The first program is to initialize the agent ⟨e↔e;e→Z⟩; We sort the programs using the number of copies of object Sin the condition of the motion rule. 1. when neighbouring automata are dead - a single program for both dead as well as alive automaton ⟨ D D D D e D D D D  → ⇑;Z→M⟩. P Colonies 151 2. when there is one alive neighbouring automaton - there are eight possible programs for dead and alive automata ⟨ S D D D e D D D D  → ⇑;Z→M⟩and seven other combinations. 3. when there are two alive neighbouring automata - twenty-eight programs for alive automata ⟨ S S D D S D D D D  → ⇑;Z→O⟩and other twenty-seven combinations. 4. when there are two alive neighbouring automata - twenty-eight programs for dead automata ⟨ S S D D D D D D D  → ⇑;Z→M⟩and other twenty-seven combinations. 5. when there are three alive neighbouring automata - fifty-six eight possible programs for dead and alive automata ⟨ S S S D e D D D D  → ⇑;Z→O⟩and other fifty-five combinations. 6. when there are four alive neighbouring automata - eight possible programs for dead and alive automata ⟨ SSS S e D D D D  → ⇑;Z→M⟩and other sixty-nine combinations. 7. when there are at least five alive neighbouring automata - fiftyeight possible programs for dead and alive automata ⟨ S S S S e S ∗ ∗ ∗  → ⇑;Z→M⟩and other fifty-five combinations. After executing one of the above programs, all agents move one step forward and rewrite one of their objects eto object M(automaton will be dead) or to object O(automaton will be live). The following programs are for downward movement and for updating the state of an automaton - i.e., the replacement of the object in the cell for an object in the agent to change the state of the automaton. ⟨ ∗ ∗ ∗ ∗e∗ ∗ ∗ ∗ → ⇓;O→S⟩;⟨ ∗ ∗ ∗ ∗e∗ ∗ ∗ ∗ → ⇓;M→D⟩; ⟨e→L;S↔S⟩;⟨e→L;D↔S⟩;⟨S→e;L→e⟩;⟨D→e;L→e⟩; ⟨e→L;S↔D⟩;⟨e→L;D↔D⟩. (see Fig.2). 152 L. Ciencialov´a et al.         D D D D D D D S(ee)S(ee)D(ee)D(ee)D D S(ee)S(ee)D(ee)D(ee)D D D(ee)D(ee)S(ee)S(ee)D D D(ee)D(ee)S(ee)S(ee)D D D D D D D                 D D D D D D D S(eZ)S(eZ)D(eZ)D(eZ)D D S(eZ)S(eZ)D(eZ)D(eZ)D D D(eZ)D(eZ)S(eZ)S(eZ)D D D(eZ)D(eZ)S(eZ)S(eZ)D D D D D D D                 D D(eO)D(eO)D(eM)D(eM)D D S(eO)S(eM)D(eM)D(eM)D D S(eM)S(eM)D(eM)D(eO)D D Ds(eM)D(eM)S(eO)S(eO)D D D D S S D D D D D D D                 D D D D D D D S(eS)S(eS)D(eD)D(eD)D D S(eS)S(eD)D(eD)D(eD)D D D(eD)D(eD)S(eD)S(eS)D D D(eD)D(eD)S(eS)S(eS)D D D D D D D                 D D D S S D D S(LS)S(LS)D(LD)D(LD)D D S(LS)D(LS)D(LD)D(LD)D D D(LD)D(LD)D(LS)S(LS)D D D(LD)D(LD)S(LS)S(LS)D D D D D D D                 D D D D D D D S(ee)S(ee)D(ee)D(ee)D D S(ee)D(ee)D(ee)D(ee)D D D(ee)D(ee)D(ee)S(ee)D D D(ee)D(ee)S(ee)S(ee)D D D D D D D         Fig. 2. The sequence of configurations of the 2D P colony simulating beacon 11 Applications of P colonies Robot controllers P colonies and PCol automata were introduced as robot controllers in [2]. The authors followed two ideas of controlling a robot with use of P colonies. The first controller model used the PCol automaton with instructions for the robot on the input tape. The agents have to read the current information from the tape and together with objects in the environment coming from the receptors, they generate objects - commands for actuators. The agents are assembled into modules. All the modules are controlled by the main control unit. Each input symbol on the input tape represents a single instruction which has to be done by the robot, so the input string is the sequence of the actions which guides the robot in reaching its goal; performing all the actions. In this meaning the computation ends by halting, and it is successful if the whole input tape is read. The second idea was to use original model of the P colony and put all information to the environment. They also used module-oriented structure of agents, each module performs the individual functions in the control of the robot. The authors constructed a P colony with four modules: The control unit, the left actuator controller, the right actuator controller and the infra-red receptors. The controller (the P colony) is completed by the input and output filter. The input filter codes signals from the robots receptors and spread the coded signal into the environment. In the environment there is the coded signal used by the agents. The output P Colonies 153 filter decodes the signal from the environment which the actuator controllers sent into it. Decoded signal is forwarded to the robots actuators. Surface runoff 2D P colonies appear to be suitable to simulate multi-agent systems. In [1] the authors presented hydrological modelling flow of liquid over the earth’s surface using 2D P colonies. The issue of the flow of liquid over the Earth’s surface is studied by experts from two areas - hydrology and geoinformatics. Both of these disciplines work closely together on the issue of the so-called “surface runoff”. Surface runoff is the water flow that occurs when the soil is saturated to full capacity and excess water from rain, meltwater, or other sources flows over the land. Agents in the model have capacity 2, the agent contains two objects. Each of the objects carries the information about the state of the agent. One of the objects stores information about the activity of the agent. At this stage of the simulation it is the information that the agent “flows” down the terrain or the agent is still inactive (belonging to the rainfall that have not fall). The other object stores information about the previous direction of flow. This information can further modify the way of the agent as inertia. Based on the entered data - the slope surface, a source of fluid and quantity - they simulated the fluid distribution in the environment. The research continues in [12] where the model can fill sinks (places without output). 12 Open problems and conclusions We recalled the idea and functioning of the basic model of P colonies. This model was introduced in [25] in 2004. Since that time many papers and studies about the model and its variations have been published. Almost all these works are focused on describing the computational power of more or less restricted variants of P colonies. Although extensive investigations have been made in this direction, some basic questions have remained open: what about deterministic P colonies, furthermore how to define determinism in P colonies. Notice that determinism can be defined in several levels of the syntax and the semantics of the system. Another interesting question can be the problem of reversibility: how to define reversible P colonies and, thus, reversible computation in P colonies? Automaton-like P colonies (PCol automata and their variants) are topics of further study as well. Although they have been compared to some classical and nonclassical automata variants, precise descriptions of their relation to P automata and to some further variants of classical and non-classical automata would be very useful. Several other, related open problems can be found in [21]. 256 Gh. P˘aun the initial resources are pre-computed in a honest way, they do not contain too much information? How the associated complexity classes can look like, which is their relation with the existing complexity classes? Maybe even more interesting: can the internet be used as a pre-computed support for computations, of an arbitrary size? In a certain sense, internet has been already used in this way – it was the case of the SETI project, maybe of other projects, known or not. Something more: the algorithms considered in the complexity theory are deterministic, what it is happening in a test tube or in a cell is far from that. However, the result is either “reliable”, in the sense that it is obtained with a probability close to 1 (Adleman has used sufficiently many DNA molecules so that he was “sure” that all paths in the graph were constructed in the first phase of the experiment), either the computation, even if it is non-deterministic, is confluent, with two possibilities: strongly confluent, that is, after a non-deterministic phase, the computation converges to a unique configuration, and after that the continuation is deterministic, or weakly/logically confluent, that is, irrespective which was the followed path, the answer is the same. In MC, most of the solutions were initially semi-uniform and (strongly or weakly) confluent, after that for a while the solutions were uniform and confluent, while in the last time most of the considered solutions are uniform and deterministic. Once again, there appears here a challenge for the complexity theory, to clarify the relationships between complexity classes defined using non-deterministic solutions, confluent solutions (in the two versions), and the deterministic solutions. 11. All these are challenges for the theory – also having some practical interpretations and consequences. However, let us refer also to some much more specific aspects, at least at the fist sight closer to applicative computer science. Let us compare the computer programs, as they are usually conceived, as precise sequences of instructions, with a well specified order in which they are executed, maybe with the ordering controlled by using labels, go to instructions, conditional instructions, cycles, with the “programs” in a cell and the completely different way they are executed. In a cell, the molecules, present in the form of multisets, react/evolve by the means of possible reactions. Instead of a sequence of instructions, we have a set of reactions, a non-ordered set, without any organization, which are applied to “data” (to the molecules) in a concurrent manner, each possible reaction in competition with other possible reactions in finding molecules to process, with many reactions developing concomitantly if sufficient reactants are available and if the necessary conditions are met for the reactions to take place (temperature, salinity, acidity, the presence of certain catalysts and promoters, the absence of inhibitors, and so on). There appear probabilities, stoichiometric coefficients which predict-control the frequency of applying the reactions, depending on the population of reactants and the reaction conditions, there appears the dependence on promoters and inhibitors, but not the precise chain of instruction from a program in Algol-Fortran-Pascal-Basic or in any programming language closer to our days. In a large extent, the functioning of a cell is much more similar to the functioning Some Wonders of a Bio-Computer-Scientist 257 of a Chomsky grammar than to the functioning of an automaton, of a Turing machine, where the states control the used instructions, maybe uniquely identifying them, in the case of deterministic automata. Can we learn something at least interesting if not even useful for computability from these aspects? Similarly in a tissue or in an organ, and still more in a colony of bacteria, there appears a functioning “in a community” which is not at all similar to the functioning of a set of processors put to work together. In biology, the parallelism is not total, the processes are not perfectly synchronized, in spite of the fact that there are rather precise “biological clocks”, circadian cycles, annual seasons. For instance, the bacteriologists do not fully understand the way in which the bacteria realize the so-called quorum sensing, the “silent communication” before reaching a threshold after which the bacteria become aggressive. One discusses also in computer science about asynchronous computing, about amorphous computing, but nature is much ahead along these directions. I end with another aspect of a practical interest: who is computing in Adleman experiment (and in many other similar experiments), who is the computer? The DNA molecules or... Adleman itself, the biochemist, the human? Without the human control, the molecules will not do what we expect from them to do, they will do almost nothing useful for us. It is true, a robotic system can replace the human operator. In this framework, “the computer” is a hybrid, and this is the plausible form of the computer of the future. 12. Of course, there are many other wonders-questions which are worth mentioning. In what concerns the DNA, we have remained at the level of the primary structure, while neither for the protein channels we have mentioned the fact that the shape plays a fundamental role, the coupling between surfaces is crucial for the execution of the symport/antiport operations. Actually, one can imagine computations based on the matching of certain shapes (computing by shapes), a sort of puzzle game with specific rules and restrictions, which is again universal and which can get (purely theoretical for the time being) “implementations” in terms of DNA biochemistry. Similarly, at the level of the brain there are many things to be discussed. An old hypothesis claims that there are two parts of the brain, one which is conscious, controllable, and one which is sub/inconscious; the first one sends problems to the latter one, which proposes solutions, which are evaluated by the cortex and, if they are real solutions, then the problem is solved, otherwise the problem is pushed once again to the subconscious part – and the process is iterated. There is here a dialogue between a deterministic component and a non-deterministic one, again something new for computer science. Can such a process be modeled, for instance, in terms of SN P systems? Has computer science something to learn from this supposed functioning of the brain? (Let us remember that NP is the class of problems for which a solution proposed non-deterministically can be deterministically checked in polynomial time, without counting any time for the “guessing” 258 Gh. P˘aun of the solution, therefore a “bi-automaton, with one deterministic and one nondeterministic module”, with the non-deterministic component working in no time, could be of a real practical interest.) Then, concerning the learning: adaptation, evolution, learnability are common facts in biology, almost absent in the electronic technology, with the learning, at least, intimately present in the neural computing, a branch of bio-computing. Even if the type of learning here looks reductionistic, limited to the tuning of certain numerical coefficients (weights) on synapses linking “neurons” of a rather abstract form, this approach proves to be surprisingly efficient, having unexpectedly good results, comparable with the results which another area of bio-computing has, the evolutionary computing – without escaping the so-called no free lunch theorems. Recently, the neural computing has obtained a performance of a historical importance: one of the best GO players in the world was defeated, in March 2016, by AlphaGO, a..., a..., there is a problem here, as AlphaGO is not a program, it is not a computer (of the kind it was used twenty years ago in the game of chess, when Kasparov was defeated by Deep Blue computer). This time, billions of GO games among human players were stored on some thousands of computers, and a program based on neural computing has learned from these games and then from games played alone, the program against itself, so that, in the end, the South Korean GO player Lee Sedol, 9-dan, was defeated. The achievement belongs to a Google team, a detail of importance, because a routine to efficiently search through the thousand computers was also important. The result is remarkable. For many years it was said that GO is the ultimate challenge for the artificial intelligence. Now, this frontier is already behind us. I confess that I have expected a bigger enthusiasm in the bio-computing community after this event. Of course, now the challenge is to extend the strategy used by AlphaGO to other domains than GO, and I am sure that there are works in this direction. I stop here, confident that the reader has his/her own wonders-questions in front of biology and in front of biology relations with other disciplines, from engineering to computer science. Anyway, the progresses in this area, of the collaboration of biology with computer science, should not be underestimated... References 1. L.M. Adleman: Molecular computation of solutions to combinatorial problems. Science, 226 (Nov. 1994), 1021–1024. 2. B. Alberts, A. Johnson, J. Lewis, M. Raff, K. Roberts, P. Walter: Molecular Biology of the Cell. 4th Edition, Garland Science, New York, 2002. 3. P. Bottoni, G. Mauri, P. Mussio, Gh. P˘aun: Computing with shapes. Journal of Visual Languages and Computing, 12, 4 (2001), 601–626. 4. C. Calude, Gh. P˘aun: Bio-steps beyond Turing. BioSystems, 77 (2004), 175–194. 5. B.J. Copeland: Hypercomputation, Minds and Machines, 12, 4 (2002), 461–502. 6. M. Davis: The myth of hypercomputation. In Alan Turing: Life and Legacy of a Great Thinker, C. Teuscher, ed., Springer-Verlag, Heidelberg, 2003, 195–211. Some Wonders of a Bio-Computer-Scientist 259 7. J. Engelfriet, G. Rozenberg: Fixed point languages, equality languages, and representations of recursively enumerable languages.Journal of the ACM, 27 (1980), 499–518. 8. J. Gruska: Quantum Computing. McGraw-Hill, New York, 1999. 9. T. Head: Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors. Bulletin of Mathematical Biology, 49 (1987), 737–759. 10. T. Head, Gh. P˘aun, D. Pixton: Language theory and molecular genetics. Chapter 7 in vol. 2 of Handbook of Formal Languages, G. Rozenberg, A. Salomaa, eds., Springer- Verlag, Berlin, 1997, 295–360. 11. A.M. Ionescu, Gh. P˘aun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae, 71 (2006), 279–308. 12. T.-O. Ishdorj, A. Leporati: Uniform solutions to SAT and 3-SAT by spiking neural P systems with pre-computed resources. Natural Computing, 7, 4 (2008), 519–534. 13. V. Manca: On the logic and geometry of bilinear forms. Fundamenta Informaticae, 64 (2005), 261–273. 14. V. Manca: Infobiotics. Information in Biotic Systems. Springer-Verlag, Berlin, 2013. 15. S. Marcus: Linguistic structures and genetic devices in molecular genetics. Cahiers de Linguistique Th´eorique et Appliqu´ee, 11, 2 (1974), 77–104. 16. L. Pan, T. Wu, Z. Zhang: A bibliography of spiking neural P systems, Bulletin of IMCS, 1 (June 2016), 63–78. 17. Ch.P. Papadimitriou: Computational Complexity. Addison-Wesley, Reading, Mass., 1994. 18. A. P˘aun, Gh. P˘aun: The power of communication: P systems with symport/antiport. New Generation Computing, 20, 3 (2002), 295–305. 19. A. P˘aun, Gh. P˘aun: Small universal spiking neural P systems. BioSystems, 90 (2007), 48–60. 20. Gh. P˘aun: On the splicing operation. Discrete Applied Mathematics, 70 (1996), 57– 79. 21. Gh. P˘aun: Regular extended H systems are computationally universal. Journal of Automata, Languages, and Combinatorics, 1, 1 (1996), 27–36. 22. Gh. P˘aun: Computing by carving. Soft Computing, 3, 1 (1999), 30–36. 23. Gh. P˘aun: Computing with membranes. Journal of Computer and Systems Sciences, 61, 1 (2000), 108–143, and Turku Centre for Computer Science-TUCS Report No. 208 (1998). 24. Gh. P˘aun: P systems with active membranes: Attacking NP-complete problems. Journal of Automata, Languages, and Combinatorics, 6, 1 (2001), 75–90. 25. Gh. P˘aun: Membrane Computing. An Introduction. Springer-Verlag, Berlin, 2002. 26. Gh. P˘aun: Towards “fypercomputations” (in membrane computing). In Languages Alive. Essays Dedicated to J¨urgen Dassow on the Occasion of His 65 Birthday, H. Bordihn, M. Kutrib, B. Truthe, eds., LNCS 7300, Springer-Verlag, Berlin, 2012, 207– 221. 27. Gh. P˘aun: Looking for Computers in the Biological Cell. After Twenty Years (in Romanian). Reception Discourse in Romanian Academny, The Publ. House of the Romanian Academy, Bucharest, 2014. 28. Gh. P˘aun, G. Rozenberg, A. Salomaa: DNA Computing. New Computing Paradigms. Springer-Verlag, Berlin, 1998. 29. Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.: The Oxford Handbook of Membrane Computing. Oxford Univ. Press, 2000. 30. M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, ´ A. Romero-Jim´enez, D. Woods: Complexity – Membrane division, membrane creation. Chapter 12 in The Oxford Handbook of 260 Gh. P˘aun Membrane Computing, Gh. P˘aun, G. Rozenberg, A. Salomaa, eds., Oxford Univ. Press, 2010, 302–336. 31. G. Rozenberg, A. Salomaa: Watson-Crick Complementarity, Universal Computations and Genetic Engineering. Technical Report 96-28, Dept. of Computer Science, Leiden University, Oct. 1996. 32. G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages, 3 vols., Springer- Verlag, Berlin, 1997. 33. A.M. Turing: On computable numbers, with an application to the Entscheidungsproblem. Proceedings of London Mathematical Society, Ser. 2, 42 (1936), 230– 265; with a correction, 43 (1936), 544–546. 34. J.D. Watsonm, F.H. Crick: Molecular structure of nucleic acids. Nature, 4356 (April 25, 1953), 737–738. 35. C. Zandron: A Model for Molecular Computing: Membrane Systems. PhD Thesis, Universit´a degli Studi di Milano, 2001. 36. G. Zhang, J. Cheng, T. Wang, X. Wang, J. Zhu: Membrane Computing. Theory and Applications (in Chinese). Science Press, Beijing, 2015. 37. The website of membrane computing: http://ppage.psystems.eu. 38. The website of Bulletin of IMCS (International Membrane Computing Society): http://membranecomputing.net/IMCSBulletin/.