Descendants of a recognizable tree language for prefix constrained linear monadic term rewriting with position cutting strategy (Q1637228)

A term-rewrite rule \(\ell \rightarrow r\) over a ranked alphabet \(\Sigma\) is linear if the terms \(\ell\) and \(r\) are linear, and it is monadic if the right-hand side \(r\) is either a variable or of the form \(\sigma(x_{i_1},\ldots,x_{i_m})\), where \(\sigma\) is an \(m\)-ary symbol in \(\Sigma\) (\(m\geq 0\)) and \(x_{i_1},\ldots,x_{i_m}\) are pairwise different variables. \textit{K. Salomaa} [J. Comput. Syst. Sci. 37, No. 3, 367--394 (1988; Zbl 0668.68084)] has shown that for any (possibly infinite) linear monadic term-rewriting system (TRS) \(S\), the descendant set \(S^*(L)\) of any recognizable tree language \(L \subseteq T_{\Sigma}\) is also recognizable. He also proved that if \(S\) is finite, one can construct a recognizer for \(S^*(L)\) if a recognizer for \(L\) is given. \textit{S. Vágvölgyi} [Inf. Process. Lett. 99, No. 3, 111--118 (2006; Zbl 1184.68302)] proved then that for any fixed recognizable \(L\), the number of such descendant sets \(S^*(L)\) is finite, and that if a recognizer for \(L\) is given, we can find a finite set of linear monadic TRSs that yield these sets. In the present paper the author extends these results to prefix-constrained linear monadic TRSs with position-cutting rewriting. A prefix-constrained rewrite rule may be applied at a position in a given tree only in case the path from the root of the tree to that position is described by a word belonging to the regular path language associated with the rule. This notion has been introduced by \textit{F. Jacquemard} et al. [Lect. Notes Comput. Sci. 9195, 137--151 (2015; Zbl 1465.68121)]. In the paper at hand, the constraint languages are taken from any given finite set of regular path languages. The position-cutting rule means that rewriting is not allowed at any proper extension of a position where rewriting has already taken place.