| Links' Seminars and Public Events |   |
Fri, April 27, 2018 10:30 am 12:30 pm | Yann Strozecki in Links' Seminar: Methods in enumeration In 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, April 25, 2018 2:15 pm 3:45 pm | Nicolas Stage Jan's office |
Fri, April 20, 2018 2:15 pm 3:45 pm | Nicolas Stage Jan's office |
Fri, April 13, 2018 2:15 pm 3:45 pm | Nicolas Stage Jan's office |
Fri, April 13, 2018 10:00 am 12:00 pm | Iovka Boneva and Jérémie Dusart in Links' Seminar: Shape Expressions Schemas 2.0 : Semantics and Implementation We will present the semantics of the ShEx language, its implementation in java, and future directions of research. Salle B21 |
Fri, April 6, 2018 2:15 pm 3:45 pm | Nicolas Stage Jan's office |
Fri, March 30, 2018 2:15 pm 3:45 pm | Nicolas Stage Jan's office |
Fri, March 23, 2018 10:00 am 11:30 am | Paul Gallot: High-Order Tree Transducers Paul 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, March 21, 2018 2:00 pm 3:15 pm | répétition Delta |
Fri, March 16, 2018 10:00 am 11:30 am | Luc Dartois in Links' Seminar: A Logic for Word Transductions with Synthesis In 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 |
