Invited and Keynote Speakers
- Gheorghe Paun (Romanian Academy, Bucharest, Romania)
- Erzsébet Csuhaj-Varjú (Eötvös Loránd University, Budapest, Hungary)
- Alberto Leporati (University Milan-Bicocca, Italy)
- Thomas Preußer (Accemic Technologies GmbH Dresden, Germany)
- Stefan Schuster (Friedrich Schiller University Jena, Germany)
Gheorghe Paun graduated from Faculty of Mathematics of Bucharest University in 1974 and was a senior researcher in the Institute of Mathematics of the Romanian Academy until December 2015, when he retired. Many scholarships and scientific visits in many countries, including long stages in Germany, Finland, Spain, Japan, China. Several contributions to formal language theory (e.g, regulated rewriting, Marcus contextual grammars, grammar systems), natural computing (DNA and membrane computing), combinatorics on words, operation research, applications. In the fall of 1998 he initiated membrane computing and after that he completely devoted to this research area. ISI highly cited researcher, author of numerous papers, author of monographs and editor of many collective volumes. Member of the Romanian Academy and of Academia Europaea.
Membrane Computing after 20 Years
The presentation is a quick glimpse on the evolution of membrane computing, with an autobiographical character, starting with the initial motivation, describing shortly the main research directions, the bibliography, the dedicated meetings, the more active research groups. A special attention is paid to the recently organized International Membrane Computing Society, its Bulletin and the forthcoming Journal of Membrane Computing, to be published by Springer-Verlag. Bibliographical hints are provided - several papers which introduced classes of P systems well investigated and monographs and collective volumes which are comprehensive sources of information, both in what concerns the theoretical developments and the application s of P systems.
Erzsébet Csuhaj-Varjú, full professor, is the head of the Department of Algorithms and Applications at the Faculty of Informatics, Eötvös Loránd University, Budapest, and the head of the PhD School in Informatics at the University. Her main research interests are formal languages and its applications in natural computing, distributed systems, and natural language processing. She has been co-founder of the area of grammar systems, a formal language-theoretic counterpart of the theory of multi-agent systems. She also has several important contributions to molecular computing and membrane computing. Among others, she has launched (with co-authors) research vistas theory of networks of language processors and P automata theory. Her publications obtained more than 1500 independent citations. She has been the principal investigator and participant of several Hungarian and bilateral granted research projects, team leader of EU projects. In the last ten years, she has been programme committee chair, co-chair, or programme committee member, organizer of more than 50 international workshops and conferences. In P systems community, she is the chair of the Advisory Board of the International Membrane Computing Society and member of the Steering Committee of the annual series of Conference on Membrane Computing.
How Membrane Computing Influences Theoretical Computer Science
Membrane computing has become a vivid, successful area of natural computing since 1998 when the notion of a membrane system (later called a P system) was introduced by Gheorghe Paun. The original concept aimed at providing a formal computational model of a distributed system that mimics the living cell. Although a lot of research has been devoted to studying P systems as computing devices, in particular variants that are as powerful as Turing machines, the applicability of membrane systems in several other areas of theoretical computer science has also been demonstrated during the years. Algorithms in terms of P systems, applications in graphics, cryptography, Boolean circuits, parallel architectures have been presented and links to Petri nets, process algebra, X-machines have been examined, only to mention a few. The aim of this talk is twofold. Firstly, by well-chosen models and results we demonstrate the benefits of applying methods and approaches of membrane computing for solving some well-known problems in different areas of theoretical computer science. Secondly, we discuss how much extent the boundaries of certain areas of theoretical computer science can be expanded by using P system variants as computing devices.
Alberto Leporati is an Associate Professor at the Department of Informatics, Systems and Communication (DISCo) of the University of Milan-Bicocca, Italy. He has obtained his Ph.D. from the University of Milan in 2003, defending a thesis on Quantum Computing. His research activity is in the field of Theoretical Computer Science. In particular, he studies the computational power of models of computation wich are inspired by the operation of living cells (Membrane Computing) or by the laws of quantum mechanics (Quantum Computing), using techniques from the theory of Computational Complexity. He has also interests towards Cryptography, and the implementation of strong cryptographic primitives through parallel computation devices, mainly Boolean circuits and Cellular Automata. On these subjects, he has published about 100 papers in peer-reviewed scientific journals and conferences. He has participated to several nationally and internationally funded competitive projects. He has supervised two Ph.D. theses and two post-doc research projects. In the Membrane Computing community, he serves as the vice-president of the International Membrane Computing Society, and as a member of the Steering Committee for the annual series of Conferences on Membrane Computing (CMC).
Time and Space Complexity of P Systems - And Why They Matter
P systems constitute an incredibly rich and interesting framework for defining parallel and distributed models of computation. Computational complexity theory can be used to study the computing capabilities, and the computational features of these systems, mainly with two goals: (1) understanding what kind of problems can or cannot be solved, and (2) how much time and space the P systems need to solve a given problem. During my presentation, I will review some of the techniques which are typically used to prove this kind of results. In particular, we will see how the comparison (by simulations) with other models of computation - usually Turing machines, register machines, and Boolean circuits - allows one to obtain different views on both the investigated problems and the computational models. Rather than delve into the technical details of the simulations I will discuss over their significance, both at the theoretical level and in the view of possible applications.
Thomas Preußer is a Managing R&D Engineer at Accemic Technologies in Dresden. He studied Computer Science at the Technische Universität Dresden and at the University of Texas at Austin before earning his PhD at TU Dresden. After having spent many years as PostDoc researcher and instructor in academia, Thomas joined Michaela Blott's research group at Xilinx Ireland as an EU-funded Marie-Sklodowska-Curie Fellow. There he was working on the efficient implementation of neural network inference engines on the Xilinx portfolio of heterogeneous hardware devices. His research interests are embedded and digital design with a focus on computer arithmetic and high-performance data processing. Thomas has published more than 50 peer-reviewed research papers and articles, has won a Michael-Servit-Award and has been the holder of the world record in computing solution counts of the N-Queens Puzzle since 2009.
A Brute-Force Solution to the 27-Queens Puzzle Using Distributed Computation
The N-Queens Puzzle is an intriguing mathematical riddle that provokes many interesting but hard questions albeit having an astonishingly simple problem statement. One of these questions asks for the number of non-attacking placements of N queens onto a generalized NxN chessboard. While estimates and bounds can certainly be given, the exact solution counts, so far, have not lent themselves to a reasonable closed-form solution but rather to showcasing the arts of computer programming - and of digital design - in a tedious systematic exploration of the vast solution space. Already, Donald Knuth has made it a classic example illustrating the technique of backtracking. The largest problem sizes with known solution counts are N=26 and N=27. Both of them were first obtained by distributed computations relying on nodes featuring solver engines built within field-programmable hardware. This presentation will briefly introduce the capabilities and opportunities of programmable hardware highlighting its great fit for exploring the N-Queens Puzzle. It will illustrate how the computations were partitioned and how symmetries were used to prune the search spaces before even starting. Finally, the distributed architectures running the actual computations over several months each will be detailed.
Stefan Schuster is a full professor for Bioinformatics at the Faculty of Biological Sciences, University of Jena, Germany. He studied biophysics at Humboldt University, Berlin and obtained his PhD in Theoretical Biophysics at that university in 1988. He worked as a postdoc at Bordeaux University (France) and the Netherlands Cancer Institute in Amsterdam and returned as a lecturer to Humboldt University. In 2003, he was appointed to his present position. Stefan’s research interests include the mathematical modelling of metabolic networks and intracellular signaling, evolutionary game theory, alternative splicing and the molecular structure of biomolecules. His work is at the interface between biology, biochemistry, mathematics and computer science. One of his most prominent achievements is the development of elementary flux modes, which has proved to be instrumental in analyzing metabolic networks. He is one of the Editors of the journal BioSystems.
Algebra Meets Biology
Fibonacci numbers and the Golden Section occur in many instances in Biology. We have recently found that the potential number of fatty acids increases with their chain length according to the famous Fibonacci series, when cis/trans isomerism is neglected. Since the ratio of two consecutive Fibonacci numbers tends to the Golden section, 1.618…, organisms can increase fatty acid variability approximately by that factor per carbon atom invested. Moreover, we show that, under consideration of cis/trans isomerism, modification by hydroxy and/or oxo groups, triple bonds or adjacent double bonds, diversity can be described by generalized Fibonacci numbers (e.g. Pell numbers). Similar calculations can be applied to aliphatic amino acids. Our results should be of interest for mass spectrometry, combinatorial chemistry, synthetic biology, patent applications, use of fatty acids as biomarkers and the theory of evolution. A second example of the role of algebra in biology discussed in this talk concerns intracellular calcium oscillations. Such oscillations are transformed (in a sense, decoded) in the cell by phosphorylation of proteins. In this way, an approximate temporal integral of the signal is computed. This implies that the number of spikes in the oscillation can be counted. In plant cells, an effect is often triggered only if a certain number of spikes (e.g., five) occurred. Some techniques for the mathematical modelling of such phenomena are reviewed here.