Plenary Lecture
The Challenge of Hyperbolic Cellular Automata: From NP-Problems To Bacteria
Professor Maurice Margenstern
Universite de Lorraine
France
E-mail: margenstern@gmail.com
Abstract: In this talk, we remind how to implement cellular automata in hyperbolic spaces. We survey the results obtained in this field from already 14 years. The research addresses theoretical questions as well as applied ones.
The tools intorduced to implement hyperbolic cellular automata allowed us to solve theoretical problems as tiling problems and universality issues. The tools also address the NP=P questions onto which they shed a new light. Many applications can be listed from communication networks to bacteria colonies.
Brief Biography of the Speaker: MARGENSTERN Maurice, was graduated with a PhD in mathematics in 1974 at the University Paris-Sud. Until 1995, he belonged to the department of mathematics, becoming there associate professor in 1982. From 1995 until 2011, he was full professor at the University of Metz, France, in the field of computer science, ending his carrier as professor of exceptional class, a degree he was given by the National Council of Universities in France. He is now professor emeritus of the University of Lorraine, starting from 2011. His scientific activity deals with the frontier between decidability and undecidability which is studied in various models of discrete computations. He has important results in Turing machines, in cellular automata and in (bio)molecular computing. He is very active in the field of cellular automata. He introduced an original method in order to implement these automata in hyperbolic spaces. He wrote more than 200 papers, among them 72 in well known international journals, 59 in international conferences with proceedings. He also wrote three books in the field of cellular automata in hyperbolic spaces. He is a member of the Editorial Board of the Journal of Universal Computer Science, of the Journal of Cellular Auotmata and he is a member of the Advisory Board of the Computer Science Journal of Moldova. He is a member of WG 1.5 in the TC1 of IFIP.