Seminars

you must be logged-in to have full access to seminar attachments

Towards computing the maximum bisimulation with Spiking Neural P Systems

Date: 
19 April, 2011 - 14:30 - 15:00
Location: 
Sala Riunioni
Description
Abstract: 

We show how to use Spiking Neural P Systems to produce in linear time a partition of the nodes of a graph, which is coarser than the maximum bisimulation.

The Ultimate Undecidability Result for the Halpern-Shoham Logic

Date: 
1 April, 2011 - 16:00 - 17:00
Location: 
Sala Riunioni del DIMI
Description
Abstract: 

The Halpern-Shoham logic is a modal logic of time intervals.
Some effort has been put in last ten years to classify fragments of this beautiful logic with respect to decidability of its satisfiability problem. We complete this classification by showing -- what we believe is quite an unexpected result -- that the logic of subintervals,
the fragment of the Halpern-Shoham where only the operator "during'", or D, is allowed, is undecidable over discrete structures. This is surprising as this, apparently very simple, logic is decidable over dense orders and its reflexive variant is known to be decidable over discrete structures . Our result subsumes a lot of previous negative results for the discrete case, like the undecidability for ABE , BD , ADB, AAbarD, and so on.
The talk I am going to give will be an informal, technical, blackboard talk.
I will explain how the proof of the main result works. I will also tell something about the fun I had discovering it -- and this part is clearly not going to be too technical.
I will assume that the audience has some experience with some modal logic.

Boolean network robotics

Date: 
1 April, 2011 - 15:00 - 16:00
Location: 
Sala convegni del DIEGM
Description
Abstract: 

Dynamical systems theory and complexity science provide powerful tools for analysing artificial agents and robots. Furthermore, they have been recently proposed also as a source of design principles and guidelines. Boolean networks are a prominent example of complex dynamical systems and they have been shown to effectively capture important phenomena in gene regulation. From an engineering perspective, these models are very compelling, because they can exhibit rich and complex behaviours, in spite of the compactness of their description. Boolean network robotics concerns the use of Boolean networks, and other models from complex systems science, as robot programs. The network that controls the robot is designed by means of an automatic procedure based on stochastic local search techniques. In this talk, the main concepts of this recent research line will be presented and the latest results achieved will be illustrated.

The Robertson-Seymour Theorem

Date: 
24 March, 2011 - 14:30 - 15:30
Location: 
Sala Riunioni
Description
Abstract: 

The Robertson-Seymour theorem states that in any infinite sequence of finite graphs, there must exist one that is a minor of a later one (i.e. the class of finite graphs is well-quasi-ordered by the minor relation). In this talk I will give an overview of the main concepts and of some of the techniques used in the proof of this important theorem in graph theory.

This talk is part of the PhD program in Computer Science and is based on a course attended at the First Montreal Spring School in Graph Theory, May 2010.

Syndicate content