CogniGron Seminar - Dr. A. Pavlogiannis

Title:            
Algorithmic Analysis of Concurrent and Evolutionary Systems

Abstract:
The talk will consist of two discrete parts, one on the analysis of concurrent systems and one on the design and analysis of evolutionary systems.
The verification of concurrent systems remains an open challenge today, due to non-determinism in the communication of the interacting entities, resulting in an exponential explosion in the size of the underlying search space. In the first part of my talk, I will outline some foundational limitations of existing techniques for the rigorous analysis of concurrent systems. I will introduce a new abstraction of concurrent semantics, called the Observation Equivalence (OE), which overcomes some of these limitations in a fundamental way. I will demonstrate algorithmic applications of OE in two domains: (i) stateless model checking and (ii) dynamic race detection. In both domains, the new algorithms successfully analyze c concurrent programs that were beyond the reach of previous state-of-the-art methods.
Evolutionary dynamics model the evolution of populations by means of natural selection and random drift. The most fundamental quantity in these dynamics is the probability that a novel mutation will fixate in the population, as it characterizes the progress rate of the population towards fitness optima. In the second part of my talk, I will introduce Amplifiers of Natural Selection. These are spatial structures that amplify the selective advantage of novel mutations, thereby speeding-up evolution. I will discuss the existence and abundance of weak and strong amplifiers, and also show how such structures can be constructed algorithmically.

For more information please visit www.rug.nl/fse/cognigron