Speaker:Prof. Enrico Formenti, University of Nice Sophia Antipolis, France
Brief Bio of the Speaker:Prof. Enrico Formenti currently works as a Full Professor at the Department Laboratoire d'Informatique, Signaux et Systèmes de Sophia-Antipolis, University of Nice Sophia Antipolis, Nice, France.
He received his master's degree in Computer Science from the University of Milan and defended his PhD in Computer Science at the Ecole Normale Supérieure de Lyon in October 1998. He became assistant professor in 2001 at the
Univiersité de Provence (now Aix-Marseille Université) and got his "Habilitation à diriger des recherches" in 2002 from the same university. He became full professor at the Université de Nice Sophia Antipolis (now Université
Côte d'Azur) in September 2003.
He is a member of the editorial board of the "Journal of Automata, Languages , and Combinatorics", "Journal of Cellular Automata", "Natural Computing" and has organized 7 international
conferences or workshops. He has more than 150 articles under his name. His research interests cover discrete dynamical systems, symbolic dynamics, computational complexity, dynamical complexity, chaotic behavior, dynamical
systems for artificial intelligence. Abstract of the talk: This talk is divided into two parts. In the first, we will survey the decidability of important properties of the dynamics of additive cellular automata over finite
abelian groups together a discussion on the computational complexity of the respective decision algorithms. In the second part, we will apply the techniques and the algorithms of the first part to some cryptographic settings
appeared in literature.
- June 19, 2021
Labels: Second Webinar Series
Location: Kolkata, West Bengal, India
Speaker:Dr. Sudhakar Sahoo
Brief Bio of the Speaker:Dr. Sudhakar Sahoo currently works at the Institute of Mathematics and Applications, Bhubaneswar, India where he has joined as an Assistant Professor in 2010. He has completed his PhD in Computer
Science from Utkal University, India. His area of interest is Theory of Computation, Algorithms, Fractals, and Cellular Automata. He has authored 36 research articles in reputed journals and conferences. His current project
is 'PATTERNS: SCIENCE & FUN (A Cellular Automata & Integral Value Transformations (IVT) Application for Research & Development)'.
Abstract of the talk: In this lecture I will discuss some of our results on number
conservation and Density classification problem. Though simple in nature, they are considered to be hard in the field of Cellular Automata (CA). While working on the CA model a variant of it named as Integral Value Transformations
(IVTs) have been defined and I will also discuss some of our research findings over IVTs.
- July 10, 2021
Labels: Second Webinar Series
Location: Kolkata, West Bengal, India
Speaker:Dr. Kamalika Bhattacharjee, National Institute of Technology, Tiruchirappalli, India
Brief Bio of the Speaker:Dr. Kamalika Bhattacharjee is an Assistant Professor in the Department of Computer Science and Engineering, National Institute of Technology, Tiruchirappalli. She received her B.Tech (Information
Technology) from Govt. College of Engineering & Textile Technology, Serampore in 2011 and M.E. (Information Technology) from Indian Institute of Engineering Science and Technology (IIEST), Shibpur (Erstwhile, Bengal Engineering
& Science University Shibpur) in 2013. She was the college topper in her B.Tech and Gold Medalist in her M.E.. She completed her Ph.D. from her alma mater IIEST, Shibpur in 2019 as recipient of INSPIRE fellowship from the Department
of Science and Technology, Govt. of India. Her research interests include cellular automata, randomness, logic and algorithmic complexity theory.
She is also one of the organizers of the webinar series and the moderator
of the group Cellular Automata India.
Abstract: While studying the reversibility (i.e. injectivity) of infinite and finite cellular automata (CAs), one can identify (at least) the following four cases:
1. An infinite CA whose global function is injective
on the set of “all infinite configurations”.
2. An infinite CA whose global function is injective on the set of “all periodic configurations”.
3. An infinite CA whose global function is injective on the set of “all finite configurations of length n” for all n∈ℕ.
4. A finite CA whose global function is injective on the set of “all configurations of length n” for a fixed n.
Hence, in one-dimension, cases 1, 2 and 3 are equivalent, and Case 4 is different from them. To decide reversibility of a finite CA (Case 4), we need to know both the rule and the CA size. But, for infinite CAs, reversibility is decided based on the local
rule only. Therefore, apparently, these two seem to be divergent. To construct a bridge between these two cases, reversibility of CAs is redefined and the notion of semi-reversible CAs is introduced. Hence, we get a new classification
of finite CAs – (1) reversible CAs (reversible for every n∈ℕ), (2) semi-reversible CAs (reversible for some n∈ℕ) and (3) strictly irreversible CAs (irreversible for every n∈ℕ). We then use a well-known characterization tool,
Reachability Tree and devise an algorithm to decide whether a finite CA is reversible or semi-reversible. This leads us to a new relationship between reversibility of finite and infinite CAs.
- July 31, 2021
Labels: Second Webinar Series
Location: Kolkata, West Bengal, India
Speaker:Prof. Jarkko J Kari
Brief Bio of the Speaker:Prof. Jarkko J Kari is currently a professor at the Department of Mathematics, University of Turku and a leading personality in the domain of Theoretical Computer Science, especially for his contributions to the theory of Wang tiles and Cellular Automata. He received his Ph.D in 1990 from the University of Turku.In a remarkable work, he has proved that the reversibility of two-dimensional CA is an undecidable problem. He is one of the pioneers of developing security systems using reversible CA. His research interest also includes computation theory, automata theory and image compression. Besides serving as chair, committee member and editor of some premier conferences and journals and has delivered invited lectures and tutorials all over the globe in the domain of Theoretical Computer Science.
Abstract: Wang tiles, or square tiles with local matching rules, are a convenient and visual way to describe two-dimensional subshifts of finite type. The domino problem is the decision problem to determine if a given finite set of Wang tiles admits a tiling of the infinite plane. The problem is closely related to aperiodicity, the property of some tile sets that they only admit tilings that are not periodic. A classical result by R. Berger from the 1960's states that aperiodic tile sets exist, and that the domino problem is undecidable: no algorithm exists that correctly solves the domino problem for every finite tile set. Wang tiles easily translate into two-dimensional cellular automata so that aperiodicity yields cellular automata with unexpected properties, and the undecidability of the domino problem leads to various undecidable problems concerning cellular automata. In particular, reversibility of a two-dimensional CA cannot be decided by an algorithm. Even one-dimensional cellular automata theory benefits from tiles: space-time diagrams can namely be viewed as tilings with determinism properties. In this talk we review these topics and explain some old results.
- August 28, 2021
Labels: Second Webinar Series
Location: Kolkata, West Bengal, India