×

Independence of the equational axioms for iteration theories. (English) Zbl 0649.68010

The author’s characterization of iteration theories by five equational axiom schemes [Comput. Linguist. Comput. Lang. 14, 183-207 (1980; Zbl 0466.68010)] contained one redundant identity [J. Comput. Syst. Sci. 27, 291-303 (1983; Zbl 0532.68011)]; in the present paper, four models are constructed to demonstrate the independence of the remaining four identities.
Reviewer: M.Armbrust

MSC:

68N01 General topics in the theory of software
18C10 Theories (e.g., algebraic theories), structure, and semantics
18B20 Categories of machines, automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arbib, M. A.; Manes, E. G., Partially additive categories and flow-diagram semantics, J. Algebra, 62, 203-227 (1980) · Zbl 0429.68021
[2] Bloom, S. L.; Elgot, C. C., The existence and construction of free iterative theories, J. Comput. System Sci., 12, 305-318 (1976) · Zbl 0333.68017
[3] Bloom, S. L.; Elgot, C. C.; Wright, J. B., Solutions of the iteration equations and extensions of the scalar iteration operation, SIAM J. Comput., 9, 25-45 (1980) · Zbl 0454.18011
[4] Bloom, S. L.; Elgot, C. C.; Wright, J. B., Vector iteration in pointed iterative theories, SIAM J. Comput., 9, 525-540 (1980) · Zbl 0461.68047
[5] Elgot, C. C.; Bloom, S. L.; Tindell, R., On the algebraic structure of rooted trees, J. Comput. System Sci., 16, 228-242 (1978) · Zbl 0389.68007
[6] Ésik, Z., Identities in iterative and rational algebraic theories, Comput. Linguist. Comput. Lang., 14, 183-207 (1980) · Zbl 0466.68010
[7] Ésik, Z., On generalized iterative theories, Comput. Linguist. Comput. Lang., 15, 95-110 (1982) · Zbl 0494.68009
[8] Ésik, Z., Algebras of iteration theories, J. Comput. System Sci., 27, 291-303 (1983) · Zbl 0532.68011
[9] Ésik, Z., On the weak equivalence of Elgot’s flowchart schemata, Acta Cybernet., 7, 147-154 (1985) · Zbl 0579.68035
[10] Troeger, D. R., Metric iteration theories, Fund. Inform., 5, 187-216 (1982) · Zbl 0504.68020
[11] Wright, J. B.; Thatcher, J. W.; Wagner, E. G.; Goguen, J. A., Rational algebraic theories and fixed point solutions, (17th IEEE Symp. Foundations of Comp. Sci.. 17th IEEE Symp. Foundations of Comp. Sci., Houston, Texas (1976)) · Zbl 0361.68041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.