On guarding nested fixpoints (Q4945246)

For every hierarchical system of equations \(S\) over some complete and distributive lattice we construct an equivalent system with the same set of variables which additionally is guarded. The price to be paid is that the resulting right-hand sides may grow exponentially. We therefore present methods how the exponential blow-up can be avoided. Especially, the loop structure of the variable dependence graph is taken into account. Also we prove that size \({\mathcal O}(m\cdot|S|)\) suffices whenever \(S\) originates from a fixpoint expression where the nesting-depth of fixpoints is at most \(m\). Finally, we sketch an application to regular tree pattern-matching. For the entire collection see [Zbl 0929.00039].