×

The equational logic of fixed points. (English) Zbl 0920.03067

This is a well-written and extensive survey of the universal algebraic approach to the study of fixed points in mathematics generally, and theoretical computer science more particularly. While no proofs of theorems are presented, there are many references to the current literature (175 bibliographic entries), and many examples are given in detail. The remainder of this review is quoted from the authors’ Introduction:
“Most computer scientists realize that just about every aspect of their subject involves fixed points. To list but a few familiar examples, context-free grammars are nothing but a system of fixed-point equations over the semiring of languages; circular data type specifications and recursive program schemes are also explicit fixed-point equations; the semantics of flowchart and higher type languages require the existence of certain fixed points; indeed, a “recursive solution” is a special kind of “fixed point”. An entire industry has developed in order to answer questions such as: In what settings can one find solutions of this or that particular fixed-point equation? (The equation \(D=[D \to D]\) comes to mind.)
“This paper is not concerned with questions of the existence or the construction of fixed points. We are concerned with the properties of fixed-point solutions, especially equational properties. We want to emphasize the fact that there is a complete axiomatization of the valid fixed-point identities, namely the axioms for iteration theories. Knowledge of these identities is useful in deriving properties of fixed points. In fact, we think it is just as useful to computer scientists as the knowledge of rings is for students pondering such equations as \((x+a)(x-a)= x^2-a^2\). The fixed-point calculus, consisting of the axioms for fixed points and standard (many-sorted) equational logic ought to be a part of the standard toolkit of theoreticians. The point of this tutorial is to describe several kinds of models for fixed points, discuss some alternative sets of axioms, and give a pointer to the literature for proofs and related results.
“The study of the fixed-point operation in computer science has been greatly influenced by the pioneering work of Calvin Elgot and the ADJ group (Joe Goguen, Jim Thatcher, Eric Wagner, and Jess Wright) at IBM Yorktown Heights, and that of the French school of Theoretical Informatics led by Maurice Nivat. It is an interesting fact that despite the existence of many fixed-point theorems, there has been no axiomatic treatment of the fixed-point operation in classical mathematics”.

MSC:

03G30 Categorical logic, topoi
18C10 Theories (e.g., algebraic theories), structure, and semantics
08A70 Applications of universal algebra in computer science
03D75 Abstract and axiomatic computability and recursion theory
08B05 Equational logic, Mal’tsev conditions
06B35 Continuous lattices and posets, applications
68Q55 Semantics in the theory of computing

Software:

ALGOL 60
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Aarts, C.; Backhouse, R.; Boiten, E.; Doornbos, H.; van Gasteren, N.; van Geldrop, R.; Hoogendijk, P.; Voermans, E.; van der Woude, J., Fixed-point calculus, Inform. Process. Lett., 53, 131-136 (1995)
[2] Abian, S.; Brown, A. B., A theorem on partially ordered sets with applications to fixed-point theorems, Canad. J. Math., 13, 78-83 (1961) · Zbl 0098.25502
[3] Aceto, L.; Fokkink, W.; Ingolfsdottir, A., A menagerie of non-finitely based process semantics over \(BPA^∗\), (draft paper (1996)) · Zbl 0917.68138
[4] Adámek, J., Free algebras and automata realizations in the language of category theory, Comm. Math. Unive. Carolinae, 15, 589-602 (1974) · Zbl 0293.18006
[5] Adámek, J.; Koubek, V., Least fixed-point of a functor, J. Comput. System Sci., 19, 163-178 (1979) · Zbl 0423.18007
[6] Adámek, J.; Trnkova, V., Automata and Algebras in Categories (1990), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0698.18001
[7] Alessi, F.; Baldan, P.; Belle, G.; Rutten, J. J.M. M., Solutions of functorial and non-functorial metric domain equations, Electronic Notes Theoret. Comput. Sci., 1 (1995) · Zbl 0910.68130
[8] America, P.; Rutten, J. J.M. M., Solving reflexive domain equations in a category of complete metric spaces, J. Comput. System Sci., 35, 343-375 (1989) · Zbl 0717.18002
[9] Andréka, H., On the representation of distributive semilattice-ordered semigroups, Tech. Report, Math. Inst., Hungarian Academy of Science (September 1988)
[10] Andréka, H., Representations of distributive semilattice-ordered semigroups with binary relations, Algebra Universalis, 28, 12-25 (1991) · Zbl 0725.06007
[11] Arbib, M. A., Free dynamics and algebraic semantics, (Mathematical Foundations of Computer Science’76. Mathematical Foundations of Computer Science’76, Lecture Notes in Computer Science, Vol. 56 (1977), Springer: Springer Berlin), 212-227
[12] Arbib, M. A.; Manes, E., Partially additive categories and flow-diagram semantics, J. Algebra, 62, 203-227 (1980) · Zbl 0429.68021
[13] Archangelsky, K. V., A new finite complete solvable quasi-equational calculus for the algebra of regular events, (Thesis (1990), University of Kiev)
[14] Archangelsky, K. V.; Gorshkov, P. V., Implicational axioms for the algebra of regular languages, Dokl. Akad. Nauk USSR Ser. A, 10, 67-69 (1987), (in Russian). · Zbl 0626.68059
[15] Arnold, A.; Nivat, M., The metric space of infinite trees, Fundam. Inform., 4, 445-476 (1980) · Zbl 0453.68021
[16] Arnold, A.; Nivat, M., Metric interpretations of infinite trees and semantics of non deterministic recursive programs, Theoret. Comput. Sci., 11, 181-205 (1980) · Zbl 0427.68022
[17] Backhouse, R.; Birjsterveld, M.; van Geldrop, R.; van der Woude, J., Categorical fixed-point calculus, (Category Theory and Computer Science’95. Category Theory and Computer Science’95, Lecture Notes in Computer Science, Vol. 953 (1995), Springer: Springer Berlin), 159-179
[18] Backhouse, R. C.; Carre, B. A., Regular algebra applied to path-finding problems, J. Inst. Math. Appl., 15, 161-186 (1975) · Zbl 0304.68082
[19] Baeten, J. C.M.; Weijland, W. P., Process Algebra, (Cambridge Tracts in Theoretical Computer Science, Vol. 18 (1990), Cambridge Univ. Press: Cambridge Univ. Press Cambridge) · Zbl 0716.68002
[20] Bainbridge, E. E.; Freyd, P. J.; Scedrov, A.; Scott, P. J., Functorial polymorphism, (Proc. Inst. on the Logical Foundations of Functional Programming. Proc. Inst. on the Logical Foundations of Functional Programming, Austin, TX (1987)) · Zbl 0717.18005
[21] de Bakker, J. W.; Meyer, J.-J. Ch., Order and metric in the stream semantics of elemental concurrency, Acta Inform., 24, 87-112 (1987) · Zbl 0607.68014
[22] de Bakker, J. W.; Zucker, J. I., Processes and the denotational semantics of concurrency, Inform. and Control, 54, 70-120 (1982) · Zbl 0508.68011
[23] Banach, S., Sur les operations dans les ensembles abstraits et leur applications aux équations intégrales, Fundam. Math., 22, 133-181 (1922) · JFM 48.0201.01
[24] Barr, M., Fixed points in cartesian closed categories, Theoret. Comput. Sci., 70, 65-72 (1990) · Zbl 0717.18004
[25] Bekic̆, H., Definable operations in general algebras, and the theory of automata and flowcharts, Tech. Report, IBM Laboratory (1969), Vienna
[26] Benson, D.; Tiuryn, J., Fixed points in free process algebras, Theoret. Comput. Sci., 63, 275-294 (1989) · Zbl 0679.68046
[27] Bergstra, J. A.; Stefanescu, Gh., Processes with multiple entries and exits modulo isomorphism and modulo bisimulation (1994), preprint · Zbl 0854.68031
[28] Bernátsky, L.; Bloom, S. L.; Ésik, Z.; Stefanescu, Gh., Equational theories of relations and regular sets, (Words, Combinatorics and Semigroups (1994), World Scientific: World Scientific Singapore), 40-48, Kyoto, 1992 · Zbl 0874.08002
[30] Berstra, J. A.; Klop, J. W., A complete inference system for regular processes with silent moves, (Drake, F. R.; Truss, J. K., Logic Colloquium’86 (1988), Elsevier: Elsevier Amsterdam), 21-88
[31] Bloom, S. L., Iterative and metric algebraic theories, Banach Center Publications, 9, 209-224 (1982)
[32] Bloom, S. L.; Elgot, C. C.; Wright, J. B., Solutions of the iteration equation and extension of the scalar iteration operation, SIAM J. Comput., 9, 26-45 (1980) · Zbl 0454.18011
[33] Bloom, S. L.; Elgot, C. C.; Wright, J. B., Vector iteration of pointed iterative theories, SIAM J. Comput., 9, 525-540 (1980) · Zbl 0461.68047
[34] Bloom, S. L.; Ésik, Z., Axiomatizing schemes and their behaviors, J. Comput. System Sci., 31, 375-393 (1985) · Zbl 0613.68013
[35] Bloom, S. L.; Ésik, Z., Varieties of iteration theories, SIAM J. Comput., 17, 939-966 (1988) · Zbl 0676.68020
[36] Bloom, S. L.; Ésik, Z., Equational logic of circular data type specification, Theoret. Comput. Sci., 63, 303-331 (1989) · Zbl 0683.68018
[37] Bloom, S. L.; Ésik, Z., Equational axioms for regular sets, Math. Struct. Comput. Sci., 3, 1-24 (1993) · Zbl 0796.68153
[38] Bloom, S. L.; Ésik, Z., Iteration Theories: The Equational Logic of Iterative Processes, (EATCS Monographs on Theoretical Computer Science (1993), Springer: Springer Berlin) · Zbl 0796.68153
[39] Bloom, S. L.; Ésik, Z., Matrix and matricial iteration theories, J. Comput. System Sci., 46, 381-408 (1993), Part I · Zbl 0791.08006
[40] Bloom, S. L.; Ésik, Z., Matrix and matricial iteration theories, J. Comput. System Sci., 46, 409-439 (1993), Part II · Zbl 0791.08007
[41] Bloom, S. L.; Ésik, Z., Some quasi-varieties of iteration theories, (Melton, A.; Mislove, M.; Schmidt, D.; Brookes, S.; Main, M., Mathematical Foundations of Programming Semantics. Mathematical Foundations of Programming Semantics, Lecture Notes in Computer Science, Vol. 802 (1993), Springer: Springer Berlin), 378-409
[42] Bloom, S. L.; Ésik, Z., Iteration algebras of finite state process behaviors (January 1994), Available by anonymous ftp to menger.eecs.stevens-tech.edu in the directory/pub/bloom/papers/processes.
[43] Bloom, S. L.; Ésik, Z., Solving polynomial fixed-point equations, (Mathematical Foundations of Computer Science’94. Mathematical Foundations of Computer Science’94, Lecture Notes in Computer Science, Vol. 841 (1994), Springer: Springer Berlin), 52-67 · Zbl 1496.08005
[44] Bloom, S. L.; Ésik, Z., Some equational laws of initiality in 2CCC’s, Internat. J. Found. Comput. Sci., 6, 95-118 (1995) · Zbl 0834.68078
[45] Bloom, S. L.; Ésik, Z., Equational properties of fixed-points in ccc’s, Theoret. Comput. Sci., 155, 1-38 (1996), Part 1
[46] Bloom, S. L.; Ésik, Z.; Stefanescu, Gh., Notes on equational theories of relations, Algebra Universalis, 33, 98-106 (1995) · Zbl 0834.08004
[47] Bloom, S. L.; Ésik, Z.; Taubner, D., Iteration theories of synchronization trees, Inform. Comput., 102, 1-55 (1993) · Zbl 0780.68088
[48] Bloom, S. L.; Ginali, S.; Rutledge, J., Scalar and vector iteration, J. Comput. System Sci., 14, 251-256 (1977) · Zbl 0358.68072
[49] Bloom, S. L.; Thatcher, J. W.; Wagner, E. G.; Wright, J. B., Recursion and iteration in continuous theories, the M-construction, J. Comput. System Sci., 27, 148-164 (1983) · Zbl 0534.18003
[50] Boffa, M., Une remarque sur les systemes complets d’identites rationelles, Theoret. Inform. Appl., 24, 419-423 (1990) · Zbl 0701.68059
[51] Boffa, M., Une condition impliquant toutes les identites rationelles, Theoret. Inform. Appl., 29, 515-518 (1995) · Zbl 0881.68071
[52] Bounier-Rigny, A.; Krob, D., A complete system of identities for one-letter rational expressions with multiplicities in the tropical semiring, Theoret. Comput. Sci., 134, 27-50 (1994) · Zbl 0823.68051
[53] Cazanescu, V. E.; Stefanescu, Gh., Feedback, iteration and repetition, (Report No. 42 (1988), Mathematical Institute, Romanian Academy of Science)
[54] Cazanescu, V. E.; Stefanescu, Gh., Towards a new algebraic foundation of flowchart scheme theory, Fundam. Inform., 13, 171-210 (1990) · Zbl 0705.68071
[55] Cazanescu, V. E.; Stefanescu, Gh., A general result on abstract flowchart schemes with applications to the study of accessibility, reduction and minimization, Theoret. Comput. Sci., 99, 1-63 (1992) · Zbl 0770.68037
[56] Cohn, P., Universal Algebra (1965), Harper and Row: Harper and Row New York · Zbl 0141.01002
[57] Conway, J. C., Regular Algebra and Finite Machines (1971), Chapman & Hall: Chapman & Hall London · Zbl 0231.94041
[58] Corradini, F.; De Nicola, R.; Labella, A., Models of nondeterministic regular expressions, Draft Paper (1996)
[59] Courcelle, B., Fundamental properties of infinite trees, Theoret. Comput. Sci., 25, 95-169 (1983) · Zbl 0521.68013
[60] Courcelle, B.; Guessarian, I., On some classes of interpretations, J. Comput. Systems Sci., 17, 388-413 (1978) · Zbl 0392.68009
[61] Courcelle, B.; Kahn, G.; Vuillemin, J., Algorithmes d’equivalence at de reduction a des expressions minimales dans une classe d’equations recursives simples, (Proc. Automata, Languages and Programming’74. Proc. Automata, Languages and Programming’74, Lecture Notes in Computer Science, Vol. 14 (1974), Springer: Springer Berlin), 200-213 · Zbl 0285.68022
[62] Courcelle, B.; Nivat, M., Algebraic families of interpretations, (Proc. IEEE Symp. on Foundations of Computer Science (1976)), 137-146
[63] Crvenkovic̆, S.; Madarász, R. Sz., On Kleene algebras, Theoret. Comput. Sci., 108, 17-24 (1993) · Zbl 0778.03006
[64] Dorondeau, P.; Kott, L., A formal proof system for infinitary rational expressions, (Automata and Infinite Words. Automata and Infinite Words, Lecture Notes in Computer Science, Vol. 192 (1984), Springer: Springer Berlin), 68-80
[65] Eilenberg, S., (Automata, Languages and Machines, Vols. A and B (1974), Academic Press: Academic Press New York) · Zbl 0317.94045
[67] Elgot, C. C., Monadic computation and iterative algebraic theories, (Shepherdson, J. C., Logic Coll. 1973, Studies in Logic, Vol. 80 (1975), North-Holland: North-Holland Amsterdam), 175-230 · Zbl 0327.02040
[68] Elgot, C. C., Matricial theories, J. Algebra, 42, 391-421 (1976) · Zbl 0361.18004
[69] Elgot, C. C., Structured programming with and without goto statements, IEEE Trans Software Eng., SE-2, 41-53 (1976), (Corrigendum, p. 232). · Zbl 0348.68008
[70] Elgot, C. C., Some geometrical categories associated with flowchart schemes, (Fundamentals of Computation Theory. Fundamentals of Computation Theory, Lecture Notes in Computer Science, Vol. 56 (1977), Springer: Springer Berlin), 256-259 · Zbl 0385.18003
[71] Elgot, C. C.; Bloom, S. L.; Tindell, R., On the algebraic structure of rooted trees, J. Comput. System Sci., 16, 362-399 (1978) · Zbl 0389.68007
[72] Ésik, Z., Identities in iterative algebraic theories, Comput. Linguistics Comput. Languages, 14, 183-207 (1980) · Zbl 0466.68010
[73] Ésik, Z., On generalized iterative algebraic theories, Comput. Linguistics Comput. Languages, 15, 95-110 (1982) · Zbl 0494.68009
[74] Ésik, Z., Algebras of iteration theories, J. Comput. System Sci., 27, 291-303 (1983) · Zbl 0532.68011
[75] Ésik, Z., On the weak equivalence of Bigot’s flowchart schemes, Acta Cybernet., 7, 147-154 (1985) · Zbl 0579.68035
[76] Ésik, Z., Independence of the equational axioms of iteration theories, J. Comput. System Sci., 36, 66-76 (1988) · Zbl 0649.68010
[77] Ésik, Z., A note on the axiomatization of iteration theories, Acta Cybernet., 9, 375-384 (1990) · Zbl 0725.68068
[81] Ésik, Z.; Bernátsky, L., Equational properties of Kleene algebras of relations with conversion, Theoret. Comput. Sci., 137, 237-251 (1995) · Zbl 0872.08004
[82] Ésik, Z.; Bernátsky, L., Scott induction and equational proofs, (Mathematical Foundations of Programming Semantics’95. Mathematical Foundations of Programming Semantics’95, ENTCS, Vol. 1 (1995)) · Zbl 0910.68129
[83] Ésik, Z.; Bernátsky, L., Independence of the group axioms for iteration, (Talk Presented at MFPS ’12. Talk Presented at MFPS ’12, Boulder, Colorado (1996)) · Zbl 0872.08004
[84] Ésik, Z.; Labella, A., Equational properties of iteration in algebraically complete categories, (Mathematical Foundations of Computer Science’96. Mathematical Foundations of Computer Science’96, Lecture Notes in Computer Science, Vol. 1113 (1996), Springer: Springer Berlin), 336-347 · Zbl 0885.18002
[85] Fokkink, W.; Zantema, H., Basic process algebra with iteration: completeness of its equational axioms, Comput. J., 37, 259-267 (1994)
[86] Freyd, P., Algebraically complete categories, (Category Theory. Category Theory, Lecture Notes in Math., Vol. 1488 (1991), Springer: Springer Berlin), 95-104, Como, 1990 · Zbl 0815.18005
[87] Freyd, P., Remarks on algebraically compact categories, (Applications of Categories in Computer Science. Applications of Categories in Computer Science, London Math. Society Lecture Notes Series, Vol. 77 (1992), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 95-106 · Zbl 0803.18002
[88] Gallier, J., Recursion-closed algebraic theories, J. Comput. System Sci., 23, 69-105 (1981) · Zbl 0472.68006
[89] Gallier, J., The semantics of recursive programs with function parameters of finite types: \(n\)-rational algebras and logic of inequalities, (Algebraic Methods in Semantics (1985), Cambridge University Press: Cambridge University Press Cambridge), 313-362
[90] Ginali, S., Regular trees and the free iterative theory, J. Comput. System Sci., 18, 228-242 (1979) · Zbl 0495.68042
[91] Ginsburg, S.; Rice, H. G., Two families of languages related to ALGOL, J. ACM, 9, 350-371 (1962) · Zbl 0196.01803
[92] Goguen, J.; Thatcher, J.; Wagner, E.; Wright, J., Initial algebra semantics and continuous algebras, J. ACM, 24, 68-95 (1977) · Zbl 0359.68018
[93] Golan, J. S., The Theory of Semirings with Applications in Computer Science (1993), Longman: Longman New York
[94] Guessarian, I., Algebraic Semantics, (Lecture Notes in Computer Science, Vol. 99 (1981), Springer: Springer Berlin) · Zbl 0602.68017
[95] Hebisch, U., The Kleene theorem in countably complete semirings, Bayruether Math. Schriften, 31, 55-66 (1990) · Zbl 0715.68060
[96] Hoare, C. A.R., Communicating Sequential Processes (1985), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0637.68007
[97] Hoogeboom, H. J.; Rozenberg, G., Infinitary languages: basic theory and applications to concurrent systems, (de Bakker, J. W.; de Roever, W.-P.; Gozenberg, G., Current Trends in Concurrency. Current Trends in Concurrency, Lecture Notes in Computer Science, Vol. 224 (1986), Springer: Springer Berlin) · Zbl 0607.68059
[98] Hurkens, A. J.C.; McArthur, M.; Moschovakis, Y. N.; Moss, L. S.; Whitney, G., The logic of recursive equations, Draft Paper (April 1996)
[99] Ianov, Y. I., The logical schemes of algorithms, (Problems of Cybernetics, Vol. 1 (1960), Pergamon Press: Pergamon Press New York), 82-140
[100] Izumi, H.; Inagaki, Y.; Honda, N., A complete axiom system for algebra of closed-regular expressions, (Proc. ICALP’84. Proc. ICALP’84, Lecture Notes in Computer Science, Vol. 172 (1984), Springer: Springer Berlin), 260-269
[101] Kozen, D., Results on the propositional μ-calculus, Theoret. Comput. Sci., 27, 333-354 (1983) · Zbl 0553.03007
[102] Kozen, D., On Kleene algebras and closed semirings, (Proc. MFCS ’90. Proc. MFCS ’90, Lecture Notes in Computer Science, Vol. 452 (1990), Springer: Springer Berlin), 26-47
[103] Kozen, D., A completeness theorem for Kleene algebras and the algebra of regular events, Inform. Comput., 110, 366-390 (1994) · Zbl 0806.68082
[104] Krob, D., Monoides et semi-anneaux complets, (Semigroup Forum, 36 (1987)), 323-339 · Zbl 0636.16019
[105] Krob, D., On aperiodic semigroups, LITP Report Series, 89-76 (1989)
[106] Krob, D., Matrix versions of aperiodic \(K\)-rational identities, Theoret. Inform. Appl., 25, 423-444 (1991) · Zbl 0768.68077
[107] Krob, D., Complete systems of \(B\)-rational identities, Theoret. Comput. Sci., 89, 207-343 (1991) · Zbl 0737.68053
[108] Krob, D., Models of a \(K\)-rational identity system, J. Comput. System Sci., 45, 396-434 (1992) · Zbl 0762.68047
[109] Kuich, W., The Kleene and Parikh theorem in complete semirings, (Proc. ICALP’87. Proc. ICALP’87, Lecture Notes in Computer Science (1987), Springer: Springer Berlin), 212-225
[110] Kuich, W., ω-continuous semirings, algebraic systems and pushdown automata, (Proc. ICALP ’90. Proc. ICALP ’90, Lecture Notes in Computer Science, Vol. 443 (1990), Springer: Springer Berlin), 103-110 · Zbl 0765.68073
[111] Kuich, W., Automata and languages generalized to ω-continuous semirings, Theoret. Comput. Sci., 79, 137-150 (1991) · Zbl 0719.68034
[112] Kuich, W.; Salomaa, A., Semirings, Automata and Languages, (EATCS Monographs on Theoretical Computer Science (1986), Springer: Springer Berlin) · Zbl 0582.68002
[113] Lallement, G., Semigroups and Combinatorial Applications (1979), Wiley-Interscience: Wiley-Interscience New York · Zbl 0421.20025
[114] Lambek, J., A fixpoint theorem for complete categories, Math. Z., 103, 151-161 (1968) · Zbl 0149.26105
[115] Lawvere, F. W., Functorial semantics of algebraic theories, (Proc. Natl. Academy Sci. USA, 50 (1963)), 869-873 · Zbl 0119.25901
[116] Lawvere, F. W., Diagonal arguments and cartesian closed categories, (Lecture Notes in Math., Vol. 92 (1969), Springer: Springer Berlin), 134-145 · Zbl 0218.18002
[117] Lehmann, D. J., Algebraic structures for transitive closure, Theoret. Comput. Sci., 4, 59-76 (1977) · Zbl 0358.68061
[118] Lehmann, D.; Smyth, M. B., Algebraic specification of data types: a synthetic approach, Math. Systems Theory, 14, 97-139 (1981) · Zbl 0457.68035
[119] Majster-Cederbaum, M. E.; Zetzsche, F., Towards a foundation for semantics in complete metric spaces, Inform. Comput., 90, 97-139 (1991) · Zbl 0773.68050
[120] Manes, E. G., Predicate Transformer Semantics (1992), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0784.68003
[121] Manes, E. G.; Arbib, M., Algebraic Approaches to Program Semantics, (Texts and Monographs in Computer Science (1986), Springer: Springer Berlin) · Zbl 0599.68008
[122] Manna, Z., Mathematical Theory of Computation (1974), McGraw-Hill: McGraw-Hill New York · Zbl 0353.68066
[123] Markowsky, G., Chain-complete posets and directed sets with applications, Algebra Universalis, 6, 53-68 (1976) · Zbl 0332.06001
[124] Milner, R., A Calculus for Communicating Systems, (Lecture Notes in Computer Science, Vol. 92 (1980), Springer: Springer Berlin) · Zbl 0609.68021
[125] Milner, R., A complete inference system for a class of regular behaviours, J. Comput. System Sci., 28, 439-466 (1984) · Zbl 0562.68065
[126] Milner, R., A complete axiomatization for observational congruence of finite state behaviours, Inform. Comput., 81, 227-247 (1989) · Zbl 0688.68050
[127] Moschovakis, Y. N., Abstract recursion as a foundation for the theory of algorithms, (Proc. Logic Coll.. Proc. Logic Coll., Aachen, 1983. Proc. Logic Coll.. Proc. Logic Coll., Aachen, 1983, Lecture Notes in Math., Vol. 1104 (1983), Springer: Springer Berlin), 289-364
[128] Moschovakis, Y. N., The logic of functional recursion, (Proc. Internat. Congr. for Logic. Methodology and Philosophy of Science (1995)), to appear. · Zbl 0209.01502
[129] Mulry, P. S., Categorical fixed-point semantics, Theoret. Comput. Sci., 70, 85-97 (1990) · Zbl 0751.18007
[130] Ng, K. C.; Tarski, A., Relation algebras with transitive closure, (Abstract 742-02-09. Abstract 742-02-09, Notices Amer. Math. Soc., 24 (1977)), A29-A30
[131] De Nicola, R.; Labella, A., A completeness theorem for nondeterministic Kleene algebras, (Proc. Conf. MFCS’94. Proc. Conf. MFCS’94, Lecture Notes in Computer Science, Vol. 841 (1994), Springer: Springer Berlin), 536-545 · Zbl 1493.68196
[132] Nivat, M., On the interpretation of recursive polyadic program schemes, (Istituto Nazionale di Alta Matematica Symposia Mathematica, XV (1975)), 255-261
[133] Niwinski, D., On fixed-point clones, (Proc. ICALP’86. Proc. ICALP’86, Lecture Notes in Computer Science, Vol. 226 (1986), Springer: Springer Berlin), 464-473
[134] Park, D. M.R., Fixpoint induction and proofs of program properties, (Michie, D.; Meltzer, B., Machine Intelligence, Vol. 5 (1970), Edinburgh Univ. Press: Edinburgh Univ. Press Edinburgh), 59-78 · Zbl 0219.68007
[135] Park, D. M.R., Concurrency and automata on infinite sequences, (Deussen, P., Proc. GI Conf.. Proc. GI Conf., Lecture Notes in Computer Science, Vol. 104 (1981), Springer: Springer Berlin), 167-183
[136] Pasztor, A.; Statman, R., Scott induction and closure under ω-sups, Theoret. Comput. Sci., 45, 251-263 (1986) · Zbl 0611.68008
[137] Plotkin, G. D., Domains, (Lecture Notes (1983), Department of Computer Science, University of Edinburgh) · Zbl 0467.68011
[138] Pratt, V. R., Action logic and pure induction, (Logics in AI: European Workshop JELIA’90. Logics in AI: European Workshop JELIA’90, Lecture Notes in Computer Science, Vol. 478 (1991), Springer: Springer Berlin), 97-120 · Zbl 0814.03024
[139] Rabinovitch, A., A complete axiomatization for trace congruence of finite state behaviors, (Proc. Mathematical Foundations of Programming Semantics’93. Proc. Mathematical Foundations of Programming Semantics’93, Lecture Notes in Computer Science, Vol. 802 (1994), Springer: Springer Berlin), 530-543
[140] Redko, V. N., On the determining totality of relations of an algebra of regular events, Ukrain. Mat. Z., 16, 120-126 (1964), (in Russian).
[141] Redko, V. N., On the algebra of commutative events, Ukrain. Mat. Z., 16, 185-195 (1964), (in Russian).
[142] Rosenberg, I. G., Maltsev algebras for universal algebra terms, (Algebraic Logic and Universal Algebra in Computer Science. Algebraic Logic and Universal Algebra in Computer Science, Lecture Notes in Computer Science, Vol. 425 (1990), Springer: Springer Berlin), 195-208 · Zbl 0789.08004
[143] Sakarovitch, J., Kleene’s theorem revisited, (Trends, Techniques and Problems in Theoretical Computer Science. Trends, Techniques and Problems in Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 281 (1987), Springer: Springer Berlin), 39-50 · Zbl 0637.68096
[144] Salomaa, A., Two complete axioms systems for the algebra of regular events, J. ACM, 13, 158-169 (1966) · Zbl 0149.24902
[145] Salomaa, A., On regular expressions and regular canonical systems, Math. Systems Theory, 2, 341-355 (1968) · Zbl 0177.01904
[146] Salomaa, A.; Soittola, M., Automata Theoretic Aspects of Formal Power Series (1978), Springer: Springer Berlin · Zbl 0377.68039
[147] Scott, D., The lattice of flow diagrams, (Engeler, E., Semantics of Algorithmic Languages. Semantics of Algorithmic Languages, Lecture Notes in Math., Vol. 182 (1971), Springer: Springer Berlin), 311-366
[148] Scott, D., Data types as lattices, SIAM J. Comput., 5, 522-587 (1976) · Zbl 0337.02018
[149] Scott, D.; De Bakker, J. W., A theory of programs (1969), IBM: IBM Vienna, unpublished manuscript
[150] Schützenberger, M. P., On a theorem of R. Jungen, (Proc. Amer. Math. Soc., 13 (1962)), 885-890 · Zbl 0107.03102
[151] Sewell, P., Bisimulation is not finitely (first order) equationally axiomatisable, (Proc. LICS’94 (1994)), 62-70
[152] Sewell, P., Nonaxiomatisability of equivalences over finite state processes, Draft Paper (1996) · Zbl 0898.03012
[153] Simpson, A. K., A characterisation of the least fixed-point operator by dinaturality, Theoret. Comput. Sci., 118, 301-314 (1993) · Zbl 0788.18007
[154] Smyth, M. B.; Plotkin, G. D., The category theoretic solution of recursive domain equations, SIAM J. Comput., 11, 761-783 (1982) · Zbl 0493.68022
[155] Stefanescu, Gh., On flowchart theories: Part I. The deterministic case, J. Comput. System Sci., 35, 163-191 (1987) · Zbl 0628.68018
[156] Stefanescu, Gh., On flowchart theories, Theoret. Comput. Sci., 52, 307-340 (1987), Part II · Zbl 0642.68020
[157] Stefanescu, Gh., Feedback theories, Rev. Roumaine Math. Pures Appl., 35, 73-79 (1990) · Zbl 0719.68040
[158] Szendrei, Á., Clones in Universal Algebra (1986), Les Presses de l’Université Montreal · Zbl 0603.08004
[159] Tarski, A., A lattice theoretical fixpoint theorem and its applications, Pacific J. Math., 5, 285-309 (1955) · Zbl 0064.26004
[160] Tiuryn, J., Fixed-points and algebras with infinitely long expressions. Part I: regular algebras, Fundam. Inform., 2, 103-128 (1978) · Zbl 0401.68062
[161] Tiuryn, J., Fixed-points and algebras with infinitely long expressions. Part II: μ-clones of regular algebras, Fundam. Inform., 2, 317-335 (1979) · Zbl 0436.68015
[162] Tiuryn, J., Unique fixed-points vs. least fixed-points, Theoret. Comput. Sci., 12, 229-254 (1980) · Zbl 0439.68026
[163] Troeger, D. R., Metric iteration theories, Fundam. Inform., 2, 187-216 (1982) · Zbl 0504.68020
[164] Troeger, D. R., Step bisimulation is pomset equivalence on a parallel language without explicit internal choice, Math. Struct. Comput. Sci., 3, 25-62 (1993) · Zbl 0806.68044
[165] Wand, M., A concrete approach to abstract recursive definitions, (Proc. Automata, Languages and Programming’72 (1973), North-Holland: North-Holland Amsterdam), 331-334
[166] Wand, M., Fixed-point constructions in order enriched categories, Theoret. Comput. Sci., 8, 13-30 (1979) · Zbl 0401.18005
[167] Weinert, H.-J., Generalized semialgebras over semirings, (Lecture Notes in Math., Vol. 1320 (1988), Springer: Springer Berlin), 380-416 · Zbl 0649.16033
[168] Winskel, G., Synchronization trees, Theoret. Comput. Sci., 34, 33-82 (1984) · Zbl 0985.68514
[169] Winskel, G., The Formal Semantics of Programming Languages, (The MIT Press Foundations of Computing Series (1993), MIT Press: MIT Press Cambridge, MA) · Zbl 0919.68082
[170] Wagner, E. G., Algebraic semantics, (Gabbay, D. M.; Maibaum, T. S.E.; Abramsky, S., The Handbook of Logic in Computer Science, Vol. 2 (1994), Oxford Univ. Press: Oxford Univ. Press Oxford) · Zbl 0361.68041
[171] Wagner, K., Solving recursive domain equations with enriched categories, (Ph.D. Thesis (1994), Carnegie Mellon University)
[172] Wright, J. B.; Thatcher, J. W.; Wagner, E. G.; Goguen, J., Rational algebraic theories and fixed-point solutions, (17th IEEE Symp. Foundations of Computing. 17th IEEE Symp. Foundations of Computing, Houston, TX (1976)), 147-158
[173] Wright, J. B.; Thatcher, J. W.; Wagner, E. G.; Goguen, J., Some fundamentals of order-algebraic semantics, (Proc. Symp. Mathematical Foundations of Computer Science. Proc. Symp. Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 45 (1976), Springer: Springer Berlin), 153-168 · Zbl 0361.68041
[174] Xie, Y., ω-complete semirings and matrix iteration theories, (Ph.D. Thesis (1991), Department of EECS, Stevens Institute of Technology)
[175] Zhang, G. Q., Logic of Domains (1991), Birkhäuser: Birkhäuser Bagal
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.