PhD Position F/M Query-specific incremental maintenance algorithms on words and trees

The Inria University of Lille centre, created in 2008, employs 360 people including 305 scientists in 15 research teams. Recognised for its strong involvement in the socio-economic development of the Hauts-De-France region, the Inria University of Lille centre pursues a close relationship with large companies and SMEs. By promoting synergies between researchers and industrialists, Inria participates in the transfer of skills and expertise in digital technologies and provides access to the best European and international research for the benefit of innovation and companies, particularly in the region.

For more than 10 years, the Inria University of Lille centre has been located at the heart of Lille's university and scientific ecosystem, as well as at the heart of Frenchtech, with a technology showroom based on Avenue de Bretagne in Lille, on the EuraTechnologies site of economic excellence dedicated to information and communication technologies (ICT).

The task of incremental maintenance on dynamic data studies how we can efficiently
evaluate queries and then quickly update their results whenever the data is modified. This
PhD proposal focuses on settings where the queries are evaluated over data represented
as a tree or as a word: this covers many application settings, such as XML documents,
JSON records, parse trees for source code, text, event sequences, etc.

On data of this form, the simplest kind of queries to consider are Boolean queries that
ask whether the data belongs to a specified formal language L: for instance L can be a
regular languages on words. Then, if w is the input word, we can test in time O(|w|)
whether w ∈ L. When w is modified, e.g., by changing characters, we want to know
whether w ∈ L after each modification. The naive algorithm is to test membership to L
by reading the whole word after each update, with update complexity O(|w|); but in
many cases we can do better. For instance, consider the language b∗ (ab∗ ab∗ )∗ of words
on {a, b} with an even number of a’s. We can maintain membership to this language in
O(1) — simply by keeping a count of the number of a’s.

This concrete example illustrates a fundamental insight: for a given problem on trees
and words (e.g., dynamic membership to a regular language), the complexity of incre-
mental maintenance problems can differ depending on the specific query that we are
interested in maintaining. Further, they can also depend on the update language that
we use. For instance, in the streaming setting where the word w can only be modified by
appending new characters at the right, then it is trivial to maintain dynamic membership
to any language represented as a word automaton.
The goal of this PhD proposal is to achieve a deeper understanding of the complexity
of incremental maintenance problems on trees and words, with algorithms and lower
bounds that are tailored to the specific query that we want to evaluate.

The research of this PhD thesis will be mostly theoretical in nature. However, the
candidate may also explore some practical application settings in which the proposed
research is relevant and which we can also supervise. One application is the problem of
earliest query answering on words and trees, where we discover a tree in streaming and
must produce query answers as early as possible when they are certain, i.e., are true no
matter what comes next in the document. Another broad application domain to explore
is that of incremental parsing, as we expect that some of the algorithms proposed on
2trees can relate to the task of maintaining the parsing of context-free grammars on an
input word. One last potential application could be to implement some algorithms within
the Rsonpath project. This project aims at providing a very efficient query engine for
JsonPath. In particular some dedicated tasks make it necessary to
efficiently enumerate the solution of queries in streaming: this is well into the scope of
this thesis, and motivates the search for query classes admitting efficient algorithms.

This PhD will take place in the LINKS / D-DAL team at Inria Lille, it will be co-supervised by Antoine Amarilli (Advanced Research Position at Inria Lille) and Charles Paperman (Associate professor at Université de Lille).

Regular travel is expected when necessary to present articles at conferences and do research visits, and will be approved by the supervisors and funded by the team funds.

The person hired on this position will be in charge of accomplishing a PhD on the topic of "Query-specific incremental maintenance algorithms on words and trees"

The candidate will get acquainted with the state of the art on the PhD topic, perform original research in interaction with the thesis supervisors and other collaborators, write research articles describing the research results, and publish the research and present it at conferences and meetings where necessary.

• fluency in scientific English
• scientific reasoning and writing skills
• written and oral communication skills
• skills in mathematics and theoretical computer science
• ability to reflect on and document complex subjects and to choose one's own research questions
• ability to work in a team

• Subsidized meals
• Partial reimbursement of public transport costs
• Leave: 7 weeks of annual leave + 10 extra days off due to RTT (statutory reduction in working hours) + possibility of exceptional leave (sick children, moving home, etc.)
• Possibility of teleworking and flexible organization of working hours
• Professional equipment available (videoconferencing, loan of computer equipment, etc.)
• Social, cultural and sports events and activities
• Access to vocational training
• Social security coverage

2200€ gross monthly salary