Iterative algebras (Q789385): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(83)90014-2 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W4210428601 / rank | |||
Normal rank |
Latest revision as of 00:00, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Iterative algebras |
scientific article |
Statements
Iterative algebras (English)
0 references
1983
0 references
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.
0 references
loops in flow charts
0 references
formal grammars
0 references
iterative systems
0 references
algebras of languages
0 references