| Links' Seminars and Public Events |   |
Wed, February 13, 2019 1:30 pm 2:30 pm | 30mn de science : Florent Capelli on Knowledge Compilation  Inria salle Plénière (Bâtiment A) |
Fri, February 1, 2019 11:00 am 12:30 pm | Bruno Guillon in Links' seminar Title: Finding paths in large graphs Abstract: When dealing with large graphs, classical algorithms for finding paths such as Dijkstra's Algorithm are unsuitable, because they require to perform too many disk accesses. To avoid this while keeping a data structure of size quasi-linear in the size of the graph, we propose to guide the path search with a distance oracle, obtained from a topological embedding of the graph. I will present fresh experimental research on this topic, in which we obtain graph embeddings using learning algorithms from natural language processing. On some graphs, such as the graph of publications from DBLP, our topologically-guided path search allows us to visit a small portion of the graph only, in average. This is joint work with Charles Paperman. B21 Room |
Fri, November 23, 2018 11:00 am 12:30 pm | Filip Mazowiecki in Links' seminar Title: Containment for Probabilistic automata. Abstract: This is an ICALP 2018 paper. We analyze when the model of probabilistic automata has decidable properties, when restricting the ambiguity. The notion of ambiguity is usually used in weighted automata or transducers, but we follow a recent paper by Fijalkow, Riveros and Worrell, which introduced this approach. We do not solve everything but our decidability results rely unexpectedly on Schanuel's conjecture and we provide some geometric intuition behind the hardness of the problem. |
Fri, November 16, 2018 11:00 am 12:30 pm | Aurelien Lemay's Habilitation defense IRCICA |
Thu, November 15, 2018 4:30 pm 5:30 pm | Andreas Maletti in Aurélien Lemay's prehabilitation seminar Lille-Salle B21 |
Thu, November 15, 2018 3:30 pm 4:30 pm | Henning Fernau in Aurélien Lemay's prehabilitation seminar: Lille-Salle B21 |
Fri, November 9, 2018 11:00 am 12:30 pm | Talk of Bruno Guillon Abstract: The time complexity of 1-limited automata is investigated from a descriptional complexity view point. Though the model recognizes regular languages only, it may use quadratic time in the input length. We show that, with a polynomial increase in size and preserving determinism, each 1-limited automaton can be transformed into a linear-time equivalent one. We also obtain polynomial transformations into related models, including weight-reducing Hennie machines (i.e., one-tape Turing machines syntactically forced to operate in linear-time), and we show exponential gaps for converse transformations in the deterministic case. |
