Costanza CATALANO - PhD student at Gran Sasso Science Institute - SYNCHRONIZING DIGRAPHS VIA A PRIMITIVE SETS APPROACH
Automata were introduced in Computer Science as models of computing devices: they are labelled multidigraphs where the vertices represent the states of the device, and the labels represent the different control commands. An automaton is synchronising if there exists a sequence of commands (a reset word) that brings the automaton into a particular state regardless of the initial one. Synchronizing automata are suitable models for resilient systems as they can restore control over a device and they are also used in cybersecurity and robotics for part orienting problems. Determining whether an automaton is synchronising is decidable but finding its (shortest) reset word is usually hard. A long-standing open conjecture states that every synchronising automaton on n vertices has a reset word of length not greater than (n - 1)2; in practice, few automata with such long reset words are known. In this seminar, Dr Catalano will present a novel approach to the synchronisation process by making use of the notion of primitive set, conceived as an extension of the concept of primitive matrix developed in the Perron-Frobenius theory. In this perspective, synchronisation is connected to the property of a labelled directed network, by admitting a sequence of labels that link each pair of vertices. Primitive sets also find applications in stochastic switching systems, consensus for discrete-time multi-agent systems and time-inhomogeneous Markov chains. Dr. Catalano will survey theoretical questions on the topic and present novel results on the randomised generation of primitive sets. Finally, she will study the primitivity phenomenon in a probabilistic game framework.
Biography
Costanza Catalano is a student at the last year of the doctoral program in Mathematics of Natural, Social and Life Sciences at the School of Advanced Studies Gran Sasso Science Institute, L’Aquila. She received both the B.Sc. (2012) and the M.Sc. (2015) in Mathematics from the University of Florence and she has been a visiting PhD student at UCLouvain, Belgium (Oct. 2017- Jun. 2018).
Her primary interests lie in the fields of Applied Probability, Graph Theory and Discrete event systems. In particular, she has been working on automata theory, synchronisation and random graphs, with techniques taken from Optimisation, Game Theory and Linear Algebra.
(239 KB)