Extensions of iterative congruences of free iterative algebras (Q792751)

An iterative \(\Sigma\)-algebra A is a \(\Sigma\)-algebra with a unique solution for every fixpoint equation of the form \(x=p(x,a)\), with \(a\in A^ k\) and p an n-tuple of polynomial terms in \(\Sigma\) and \((n+k)\) variables. The \(\Sigma\)-algebra \(\bar R_{\Sigma}(Y)\) of total regular trees on \(\Sigma\) and Y is the free iterative algebra generated by Y. Given an iterative congruence K on \(\bar R_{\Sigma}(Y)\), this paper investigates the effect of enlarging the signature by adding a new 0-ary operator \(\perp\) and extending the congruence to the enlarged set \(R_{\Sigma}(Y)\) (whose elments can be interpreted as partial regular trees). The main result is that if \(\bar R_{\Sigma}(y)/K\) is iterative, then \(R_{\Sigma}(Y)/K'\) is iterative, where (t,t')\(\in K'\) if and only if there exist \(q\in R_{\Sigma}(n)\) and r,\(s\in \bar R_{\Sigma}(Y)^ n\) such that \(t=q[r]\) and \(t'=q[s]\). The proof is constructive in that if \(| t|\) and \(| t'|\) are solutions in \(R_{\Sigma}(Y)/K'\) of the fixpoint equation \(x=p(x,| u|)\) for \(u\in R_{\Sigma}(Y)^ k\), then q, r and s are constructed to show that (t,t')\(\in K'\). This result is then used to show that if a regular algebra admits a faithful regular extension, then that extension is again iterative.