Summary: Linear-Delay\(_{\text{lin}}\) is the class of enumeration problems computable in two steps: the first step is a precomputation in linear time in the size of the input and the second step computes successively all the solutions with a delay between two consecutive solutions \(y_{1}\) and \(y_{2}\) that is linear in \(|y_{2}|\). We prove that evaluating a fixed monadic second-order (MSO) query \(\varphi(\bar{X})\) (i.e., computing all the tuples that satisfy the MSO formula) in a binary tree is a Linear-Delay\(_{\text{lin}}\) problem. More precisely, we show that given a binary tree \(T\) and a tree automaton \(\Gamma \) representing an MSO query \(\varphi(\bar{X})\), we can evaluate \(\Gamma \) on \(T\) with a preprocessing in time and space complexity \(O(|\Gamma |^{3}|T|)\) and an enumeration phase with a delay \(O(|S|)\) and space \(O(\max|S|)\) where \(|S|\) is the size of the next solution and \(\max|S|\) is the size of the largest solution. We introduce a new kind of algorithm with nice complexity properties for some algebraic operations on enumeration problems. In addition, we extend the precomputation (with the same complexity) such that the \(i^{\text{th}}\) (with respect to a certain order) solution \(S\) is produced directly in time \(O(|S|\log (|T|))\). Finally, we generalize these results to bounded treewidth structures.
For the entire collection see [Zbl 1130.68007].