» Apply now PDF Show all positions

Abstract

The project's aim is to develop and implement a framework for cellular automata over concrete categories, expanding on the work by Capobianco and Uustalu (2010) and Behrisch et al. (2017).

Research field: Information and communication technology
Supervisors: Dr. Tarmo Uustalu
Dr. Silvio Capobianco
Availability: This position is available.
Offered by: School of Information Technologies
Department of Software Science
Application deadline:Applications are accepted between September 01, 2021 00:00 and September 30, 2021 23:59 (Europe/Zurich)

Description

Cellular automata (CA) are an example of context-dependent computation, which can be modeled as coKleisli maps of comonads or, more generally, arrows. In a CA, entities occupy the nodes of a grid which has a group of translations, and their state, taken from an alphabet, is updated synchronously according to a local rule (coKleisli map); this induces a global function (coalgebra) which updates the state of the entire grid. If the group or the alphabet have special properties, these can reflect into special properties of the rules.

The project will develop and implement a framework for CA over concrete categories whose objects can "reasonably" be seen as sets. More in general, we will study cellular automata over value spaces with algebraic structure, e.g. an abelian group. Local computations can be required to be linear or additive and this ensures that so is also the global computation (the coKleisli extension of the coKleisli map). This framework will expand on the ideas from Capobianco and Uustalu (2010) and Behrisch et al. (2017).

A first nontrivial example of CA on a concrete category is given by linear CA, where the alphabet is a ring and the local rule (equivalently, the global function) is linear: these are precisely the CA on the concrete category of modules over the given ring. It is known (Sato (1993)) that reversibility and surjectivity of linear CA over finite commutative rings are decidable in arbitrary dimension, and correspond to algebraic properties of the Laurent polynomial describing the local rule. A first step in the project can then be a translation of this fact in the language of category theory.

The PhD student will be affiliated with the ALICE (Automata in Learning, Interaction and Concurrency) group, Department of Software Science, TalTech. The ALICE project aims at extending and exploiting classical automata theory for the requirements of modern software.

 

Applicants should fulfil the following requirements:

  • MSc in Mathematics, Computer Science, or related field.
  • Previous experience with category theory and/or cellular automata theory.

 

References:

[1] Mike Behrisch, Sebastian Kerkhoff, Reinhard Pöschel, Friedrich Martin Schneider, Stefan Siegmund. Dynamical Systems in Categories. Applied Categorical Structures 25 (2017), 29--57. https://doi.org/10.1007/s10485-015-9409-8 Preprint: https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa-129909

[2] Silvio Capobianco and Tarmo Uustalu. A categorical outlook on cellular automata. In J. Kari, ed., Proc. of 2nd Symp. on Cellular Automata, JAC 2010 (Turku, Dec. 2010), v. 13 of TUCS Lecture Notes, pp. 88--99. Turku Centre for Computer Science, 2010. https://hal.archives-ouvertes.fr/hal-00542015

[3] Tullio Ceccherini-Silberstein and Michel Coornaert. Cellular Automata and Groups. Springer, 2010.

[4] Tullio Ceccherini-Silberstein and Michel Coornaert. Surjunctivity and reversibility of cellular automata over concrete categories. In: Picardello M. (eds) Trends in Harmonic Analysis. Springer INdAM Series, vol 3. Springer, Milano. doi:10.1007/978-88-470-2853-1_6 Preprint: arXiv:1203.6492

[5] John Hughes. Generalising monads with arrows. Science of Computer Programming. 37 (1–3): 67–111. doi:10.1016/S0167-6423(99)00023-4

[6] Jarkko Kari. Theory of cellular automata: a survey. Theoretical Computer Science 334 (2005) 3--33.

[7] Tadakazu Sato. Decidability of some problems of linear cellular automata over finite commutative rings. Information Processing Letters, 46:151–155, 1993.