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
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
Fri 4th Jun
10:00 am
12:30 pm
Add event to google
Séminaire Pierre Ohlmann
Zoom link: univ-lille-fr.zoom.us/j/95419000064



Titre: Lower bound for arithmetic circuits via the Hankel matrix

Abstract: We study the complexity of representing polynomials by arithmetic
circuits in both the commutative and the non-commutative settings. To
analyse circuits we count their number of parse trees, which describe the
non-associative computations realised by the circuit. In the non-commutative
setting a circuit computing a polynomial of degree d has at most 2^{O(d)}
parse trees. Previous superpolynomial lower bounds were known for circuits
with up to 2^{d^{1/3-ε}} parse trees, for any ε>0. Our main result is to
reduce the gap by showing a superpolynomial lower bound for circuits with
just a small defect in the exponent for the total number of parse trees,
that is 2^{d^{1-ε}}, for any ε>0. In the commutative setting a circuit
computing a polynomial of degree d has at most 2^{O(d \\log d)} parse trees.
We show a superpolynomial lower bound for circuits with up to 2^{d^{1/3-ε}}
parse trees, for any ε>0. When d is polylogarithmic in n, we push this
further to up to 2^{d^{1-ε}} parse trees. While these two main results hold
in the associative setting, our approach goes through a precise
understanding of the more restricted setting where multiplication is not
associative, meaning that we distinguish the polynomials (xy)z and yz).
Our first and main conceptual result is a characterization result: we show
that the size of the smallest circuit computing a given non-associative
polynomial is exactly the rank of a matrix constructed from the polynomial
and called the Hankel matrix. This result applies to the class of all
circuits in both commutative and non-commutative settings, and can be seen
as an extension of the seminal result of Nisan giving a similar
characterization for non-commutative algebraic branching programs. Our key
technical contribution is to provide generic lower bound theorems based on
analyzing and decomposing the Hankel matrix, from which we derive the
results mentioned above. The study of the Hankel matrix also provides a
unifying approach for proving lower bounds for polynomials in the
(classical) associative setting. We demonstrate this by giving alternative
proofs of recent lower bounds as corollaries of our generic lower bound
results.

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