Dynamic membership for regular tree languages

The dynamic membership problem for a formal language L asks the following: given some input data D, check whether D belongs to the language L, and then receive updates to apply to D and maintain after every update the information of whether the current version of D belongs to L or not. Among other contexts, dynamic membership has been studied for regular languages over words (in the RAM model with logarithmic word size), for substitution updates that change one letter of the word each time. Specifically, our ICALP'21 article with Louis Jachiet and Charles Paperman has identified three main complexity regimes: languages for which dynamic membership can be solved in constant time per update; languages with a complexity of Theta(log n / log log n) on words of length n; and languages with an intermediate complexity of O(log log n) and (conditionally) no O(1) algorithm. However, this works leaves open the complexity of the dynamic membership problem over different kinds of data. One interesting setting is that of trees. In particular, dynamic membership for trees generalizes the existential marked ancestor problem that has already received some attention: we have a tree whose nodes can be marked or unmarked by updates, and we receive queries that ask whether a specific node has a marked ancestor. It is known that updates and queries must take time at least Omega(log n / log log n) for this problem, which gives a similar bound for dynamic membership for some specific languages. What is striking is that the word languages corresponding to existential marked ancestor are very tame: over words, the analogous language would be aperiodic and enjoy a O(log log n) algorithm. Hence, the complexity landscape for trees is different than for words: it cannot be understood simply by looking at the horizontal and vertical monoids in isolation, and requires new algebraic tools. In this work-in-progress talk, we will present our ongoing efforts to understand the complexity of the dynamic membership problem for fixed regular languages on trees (rooted, ordered, and unranked). We focus on the simple case of relabeling updates (the tree structure is fixed), and on languages featuring a neutral letter (corresponding to tree nodes that can be replaced by the ordered list of their children). In this setting, we aim at understanding, for each fixed regular tree language, what is the best achievable worst-case complexity to maintain membership to the language after each relabeling. We will present our current results giving a conditional characterization of languages maintainable in constant time, and our ongoing efforts to understand which languages can be maintained in sublogarithmic time. The talk will in particular present some of the tantalizing open problems and specific tree languages that prevent us from achieving a complete classification. This work is a collaboration which has involved (at various degrees and at various times) Corentin Barloy, Paweł Gawrychowski, Louis Jachiet, and Charles Paperman.

Authors

• Antoine Amarilli

Keywords

No keywords are indexed for this paper.