Iterative algebras
type: Item
instance of: scholarly article
title: Iterative algebras
zbMATH Open document ID: 0533.03014
DOI: 10.1016/0304-3975(83)90014-2
author: Evelyn Nelson
published in: Theoretical Computer Science
publication date: 1983-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03C05
Mathematics Subject Classification ID: 18C10
Mathematics Subject Classification ID: 08C05
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68N01
zbMATH DE Number: 3845558
zbMATH Keywords: loops in flow charts
zbMATH Keywords: formal grammars
zbMATH Keywords: iterative systems
zbMATH Keywords: algebras of languages
Wikidata QID: Q64357043
MaRDI profile type: Publication
full work available at URL: 0304-3975(83)90014-2
OpenAlex ID: W4210428601
DBLP publication ID: journals/tcs/Nelson83
description: scientific article; zbMATH DE number 3845558