Seminars

Links' Seminars and Public Events Add to google calendar
2021
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

Permanent link to this article: https://team.inria.fr/links/seminars/