Extensions of iterative congruences of free iterative algebras
type: Item
instance of: scholarly article
title: Extensions of iterative congruences of free iterative algebras
zbMATH Open document ID: 0537.68023
DOI: 10.1016/0022-0000(83)90039-9
author: Francesco Parisi-Presicce
published in: Journal of Computer and System Sciences
publication date: 1983-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 08A99
Mathematics Subject Classification ID: 68N01
Mathematics Subject Classification ID: 08C99
zbMATH DE Number: 3854396
zbMATH Keywords: fixpoint equations
zbMATH Keywords: iterative algebras
zbMATH Keywords: regular trees
MaRDI profile type: Publication
full work available at URL: 0022-0000(83)90039-9
OpenAlex ID: W2000958740
cites work: Initial Algebra Semantics and Continuous Algebras
cites work: Q4134935
cites work: Scalar and vector iteration
cites work: Q5526993
cites work: Q4079524
cites work: Q4091917
cites work: Regular trees and the free iterative theory
cites work: Q4185836
cites work: Q3877027
cites work: Unique fixed points vs. least fixed points
cites work: Q3938490
cites work: Q4362900
cites work: Q4005171
description: scientific article; zbMATH DE number 3854396