Evènement pour le groupe Séminaire Méthodes Formelles


Date 2021-03-23  07:00-07:00
TitreShuffles, Operads, and Associahedra in Theoretical Computer Science 
RésuméThe use of "shuffling together decks of cards" as a metaphor for interleaving execution of processes is well-established in computer science, and has allowed for the transfer of concepts and tools from pure mathematics to areas such as the analysis of Race Conditions. This talk aims to demonstrate that, when we extend this intuition and related models to the infinitary case, we find further connections with many topics in theoretical computing. These range from logical models to cryptographic platforms and questions of complexity and computability. The starting point for the talk is a (still unresolved) conjecture of Lothar Collatz. We describe this in these terms as a simple game played between three players, and consider how the individual steps may be modelled and composed. Doing this allows us to place the core operator from his conjecture within a suitably general setting : the theory of operads based on invertable operations, and closely related geometric / combinatorial polyhedra such as the associahedra of J. Stasheff. We give an overview of such structures in a variety of different fields, with particular emphasis on a series of closely related examples from theoretical computer science and logic. We then take a categorical approach and - based on constructions from a well-known series of models of linear logic - give a categorical framework within which the structures we study may be thought of as canonical coherence arrows. This includes the operator from our original motivating example, as a particularly significant example. 
LieuOnline 
OrateurPeter Hines 
Emailhttp://www.peterhines.info/index_fr.html 
UrlUniversité de York 



Aucun document lié à cet événement.

Retour
Retour à l'index