The Taub Faculty of Computer Science Events and Talks

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 contest. ========================= 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.