Seminars

Links' Seminars and Public Events Add to google calendar
2022
Fri 25th Feb
11:00 am
12:00 pm
Add event to google
Séminaire Nico

Fri 28th Jan
11:00 am
12:00 pm
Add event to google
Alexandre Vigny (visio)
Title:
Separator logic, expressive power and algorithmic applications
Abstract:
First-order logic (FO) can express many algorithmic problems on graphs,
but fails to express whether two vertices are connected. We define a
new logic (separator logic) by enriching FO with connectivity
predicates connk(x, y, z1, . . . , zk) that hold true in a graph if
there exists a path between x and y after deletion of z1, . . . , zk.
In this talk I will first present a study of the expressive power of
this new logic.
I will then present algorithmic results for this logic on graph classes
that exclude a topological minor.
These results were obtained in collaboration with Michał Pilipczuk,
Nicole Schirrmacher, Sebastian Siebertz, and Szymon Toruńczyk.

Fri 21st Jan
11:00 am
12:00 pm
Add event to google
Aurélien Lemay in Seminar

2021
Fri 10th Dec
11:00 am
12:00 pm
Add event to google
Séminaire Sebastien Tavenas

Title: Bornes inférieures superpolynomiales pour les circuits de profondeur constante

Abstract:
Tout polynôme multivarié P(X_1,...,X_n) peut être écrit comme une somme de
monômes, i.e., une somme de produits de variables et de constantes du corps.
La taille naturelle d'une telle expression est le nombre de monômes. Mais,
que se passe-t-il si on rajoute un nouveau niveau de complexité en
considérant les expressions de la forme : somme de produits de sommes (de
variables et de constantes) ? Maintenant, il devient moins clair comment
montrer qu'un polynôme donné n'a pas de petite expression. Dans cet exposé
nous résoudrons exactement ce problème. Plus précisément, nous prouvons que
certains polynômes explicites n'ont pas de représentations "somme de
produits de sommes'' (SPS) de taille polynomiale. Nous pouvons aussi obtenir
des résultats similaires pour les SPSP, SPSPS, etc... pour toutes les
expressions de profondeur constante.
"
Thu 25th Nov
2:00 pm
3:00 pm
Add event to google
Nofar Carmeli in Links' Seminar
Fri 29th Oct
11:00 am
12:00 pm
Add event to google
Séminaire Antoine Amarilli

Fri 22nd Oct
11:00 am
12:00 pm
Add event to google
Mikaël Monet in Links' Seminar
Fri 15th Oct
11:00 am
12:00 pm
Add event to google
Claire Soyez-Martin in Links' seminar
Fri 17th Sep
11:00 am
12:00 pm
Add event to google
Séminaire Corentin Barloy
Title: Stackless Processing of Streamed Trees
Abstract:
Processing tree-structured data in the streaming model is a chal-lenge: capturing regular properties of streamed trees by means of astack is costly in memory, but falling back to finite-state automata drastically limits the computational power. We propose an intermediate stackless model based on register automata equipped with a single counter, used to maintain the current depth in the tree. We explore the power of this model to validate and query streamed trees. Our main result is an effective characterization of regular path queries (RPQs) that can be evaluated stacklessly—with and without registers. In particular, we confirm the conjectured characterization of tree languages defined by DTDs that are recognizable without registers, by Segoufin and Vianu (2002), in the special case of tree languages defined by means of an RPQ.

Link: paperman.name/data/pub.....0.pdf

Show in Google map
lille-Salle
Fri 10th Sep
10:00 am
11:00 am
Add event to google
Séminaire de Patrick Baillot
titre: Type-based complexity analysis in a parallel process calculus

Abstract:
Some type systems have been designed to analyse statically the time
coplexity of functional languages. A natural question is whether this approach
can be extended to parallel languages. We address this problem for the
Pi-calculus, a paradigmatic calculus for parallel and concurrent computation.
In Pi-calculus, processes communicate through channels that can carry values
and channel names. We will define notions of sequential and parallel complexity
for Pi-calculus, and present a type system that provides an upper bound on the
time complexity of processes.
This is based on joint work with Alexis Ghyselen (ESOP 2021).

Based on: link.springer.com/chap.....9-3_3
Show in Google map
Fri 9th Jul
 all day
Add event to google
Seminar - Antonio AL SERHALI
Title: Integrating Schema-Based Cleaning into Automata Determinization

Abstract : Schema-based cleaning for automata on trees or nested words
was proposed recently to compute smaller deterministic automata for
regular path queries on data trees. The idea is to remove all rules and
states, from an automaton for the query, that are not needed to recognize
any tree recognized by a given schema automaton. Unfortunately, how-
ever, deterministic automata for nested words may still grow large for au-
tomata for XPath queries, so that the much smaller schema-cleaned ver-
sion cannot always be computed in practice. We therefore propose a new
schema-based determinization algorithm that integrates schema-based
cleaning directly. We prove that schema-based determinization always
produces the same deterministic automaton as schema-based cleaning
after standard determinization. Nevertheless, the worst-case complex-
ity is considerably lower for schema-based determinization. Experiments
confirm the relevance of this result in practice.
Show in Google map

Lien Permanent pour cet article : https://team.inria.fr/links/fr/seminars/