Iterative algebras (Q789385)

The problem (which arises for example when modelling loops in flow charts or when studying formal grammars) are equations of the form \(y_ j=t_ j(x_ 1,...,x_ k,y_ 1,...,y_ n)\) (1\(\leq j\leq n)\) for terms \(t_ j\) and ''fixed'' \(x_ i\). These systems are called ''iterative systems''. The author considers classes of algebras where certain classes of iterative systems or all non-trivial iterative systems are solvable. For any type \(\Sigma\) and any set V, \(T_{\Sigma}V\), the algebra of V- labelled \(\Sigma\)-trees, is defined as a generalization of \(F_{\Sigma}V\subseteq T_{\Sigma}V\), the algebra of \(\Sigma\)-terms over V. A further subset of \(T_{\Sigma}V\) is \(R_{\Sigma}V\), the algebra of regular V-labelled \(\Sigma\)-trees - \(F_{\Sigma}V\subseteq R_{\Sigma}V\subseteq T_{\Sigma}V\). Whereas \(F_{\Sigma}V\) is the free \(\Sigma\)-algebra over V in the class of all \(\Sigma\)-algebras, \(R_{\Sigma}V\) is the free \(\Sigma\)-algebra in the class of all \(\Sigma\)-algebras where all non-trivial iterative systems are uniquely solvable. These considerations are specialized and carried further for the algebras of languages, where the context free languages are unique solutions of iterative systems. Finally this approach is compared with an approach of \textit{C. C. Elgot} [Logic Colloq. '73, Proc., Bristol 1973, 175-230 (1975; Zbl 0327.02040)] which uses algebraic theories in the sense of Lawvere.