Links' Seminars and Public Events |

2018 | |
---|---|

Fri 28th Sep 10:15 am 11:45 am | José Lozano Links seminar |

Fri 21st Sep 10:30 am 12:00 pm | Fabian Reiter in Links' Seminar: Descriptive distributed complexityThis talk connects two classical areas of theoretical computer science: descriptive complexity and distributed computing. The former is a branch of computational complexity theory that characterizes complexity classes in terms of equivalent logical formalisms. The latter studies algorithms that run in networks of interconnected processors. Although an active field of research since the late 1970s, distributed computing is still lacking the analogue of a complexity theory. One reason for this may be the large number of distinct models of distributed computation, which make it rather difficult to develop a unified formal framework. In my talk, I will outline how the descriptive approach, i.e., connections to logic, could be helpful in this regard. Salle B21 |

Fri 7th Sep 11:00 am 12:30 pm | Rustam Azimov in Links Seminar: "Context-Free Path Querying by Matrix Multiplication" |

Fri 25th May 10:00 am 11:30 am | Nicolas Crosetti in Links' Seminar: Dependency weighted aggregationLille B21 |

Fri 27th Apr 10:30 am 12:30 pm | Yann Strozecki in Links' Seminar: Methods in enumerationIn enumeration we are interested in generating a set of solutions, while bounding the time needed to generate one solution. We will first present the complexity measures used in this context, simple theoritical results and a few open questions. We then introduce classical problems in this area such as the enumeration of: trees, models of a DNF, model of a FO or MSO formula, the maximal cliques of a graph, circuits of a matroid ... We use them to illustrate the algorithmic toolbox of enumeration (Gray Code, backtrack search, reverse search, saturation...). Lille B21 |

Wed 25th Apr 2:15 pm 3:45 pm | Nicolas StageJan's office |

Fri 20th Apr 2:15 pm 3:45 pm | Nicolas StageJan's office |

Fri 13th Apr 2:15 pm 3:45 pm | Nicolas StageJan's office |

Fri 13th Apr 10:00 am 12:00 pm | Iovka Boneva and Jérémie Dusart in Links' Seminar: Shape Expressions Schemas 2.0 : Semantics and ImplementationWe will present the semantics of the ShEx language, its implementation in java, and future directions of research. Salle B21 |

Fri 6th Apr 2:15 pm 3:45 pm | Nicolas StageJan's office |

Fri 30th Mar 2:15 pm 3:45 pm | Nicolas StageJan's office |

Fri 23rd Mar 10:00 am 11:30 am | Paul Gallot: High-Order Tree TransducersPaul présentera le papier de Sylvain, Aurélien et Paul, soumis à LICS 2018, sur le sujet des transducteurs d'arbres d'ordre supérieur. |

Wed 21st Mar 2:00 pm 3:15 pm | répétition Delta |

Fri 16th Mar 10:00 am 11:30 am | Luc Dartois in Links' Seminar: A Logic for Word Transductions with SynthesisIn this talk I present a logic, called LT, to express properties of transductions, i.e. binary relations from input to output (finite) words. I argue that LT is a suitable candidate as a specification language for verification of non reactive systems, extending the successful approach of verifying synchronous systems via Mealy Machines and MSO. In LT, the input/output dependencies are modelled via an origin function which associates to any position of the output word, the input position from which it originates. LT is well-suited to express relations (which are not necessarily functional), and can express all regular functional transductions, i.e. transductions definable for instance by deterministic two-way transducers. Despite its high expressive power, LT has decidable satisfiability problems. The main contribution is a synthesis result: it is always possible to synthesis a regular function which satisfies the specification. Finally, I explicit a correspondence between transductions and data words. As a side-result, we obtain a new decidable logic for data words. Inria Lille |

Fri 9th Mar 10:00 am 11:00 am | Benjamin Bergougnoux : Counting minimal transversals of hypergraphsA transversal of a hypergraph H is a subset of vertices that intersects all the hyper-edges H. The enumeration and the counting of the minimal transversals have a lot of applications in many domains (graph theory, AI, datamining, etc). Counting problems are generally harder than theirs associated decision problems. For example, finding a minimal transversal is doable in polynomial time but counting them is #P-complet (the equivalent of NP-complet for counting problems). We have proved that we can count the minimal transversals of any beta-acyclique hypergraph in polynomial time. Our result is based on a recursive decomposition of the beta-acyclique hypergraph founded by Florent Capelli and by the introduction of a new notion that generalize the minimal transversals. A lot of exciting open questions live in the neighborhood of our result. In particular, our algorithm is able to count the minimum dominating set of a strong-chordal graph. But counting the minimum dominating set is #P-complete on split graphs. Is it the beginning of a complete characterization of the complexity of counting minimal dominating sets in dense graphs ? Salle B21 |

Fri 16th Feb 10:30 am 11:30 am | Victor Marsault : Formal semantics of the query-language CypherCypher is a query-language for property-graphs. It was originally designed and implemented as part of the Neo4j graph database, and it is currently used by several commercial database products and researchers. The semantics of Cypher queries is currently described using natural language and, as a result, it is often not well defined. This work is part of a project to define a full denotational semantics of Cypher queries. The talk will first present the main features of Cypher through examples, including the core mecanism: graph pattern-matching, and then will describe the formal semantics in its current state. Salle B21 - INRIA Institut National Recherche Informatique Automatique; 40 Avenue Halley, 59650 Villeneuve d'Ascq, France |