Time+Place: Sunday 14/07/2019 11:00 Room 301 Taub Bld.
Title: Enumeration for MSO Queries on Trees via Circuits
Speaker: Prof. Antoine Amarilli - SPECIAL GUEST LECTURE
Affiliation: Telecom Paris engineering school
Host: Prof. Benny Kimelfeld


This talk will present our approach for enumerating the
results of queries in monadic second-order (MSO) on trees. Our goal is
to first preprocess the input tree in linear time, and then enumerate
the answers with delay linear in the size of each answer, i.e.,
constant-delay for queries with free first-order variables. Our approach
is also tractable in the query when represented by a tree automaton (not
necessarily deterministic).

The approach works by computing a circuit that gives a factorized
representation of the accepting runs of the tree automaton on the input
tree. We then show that the circuit falls into a known tractable class
from knowledge compilation, and we use this to design an efficient
algorithm to enumerate the results that it captures.

The talk will also mention how these results apply to the specific case
of enumerating the matches of document spanners, i.e., regular
expressions with captures on an input text; and how the approach can
efficiently handle updates to the underlying data.

This talk is joint work with Pierre Bourhis, Louis Jachiet, Stefan
Mengel, and Matthias Niewerth, and covers results published at ICALP'17,
ICDT'18, LICS'18, ICDT'19, PODS'19.

Short Bio:

Antoine Amarilli is an associate professor at the Telecom Paris
engineering school. He studied at the Ecole normale superieure in Paris
and obtained his PhD in computer science in 2016 from Telecom Paris
under the supervision of Pierre Senellart. He was a joint winner of the
E. W. Beth Dissertation Prize in 2017. His research interests are in
database theory and in neighboring fields of theoretical computer
science, more specifically on efficient query evaluation, uncertainty
management, and logical reasoning. He has served on the program
committee of the ICDT and IJCAI conferences, and is the director of the
South-Western European selection of the ICPC competitive programming

Refreshments will be served from 10:45, lecture starts at 11:00.

Anyone interested in meeting with Antoine Amarilli in person can write 
to Benny Kimelfeld.