×

Fixed point equations with parameters in the projective model. (English) Zbl 0626.68029

Existence and uniqueness theorems are given for solving infinite and finite systems of fixed point equations with parameters in the projective model (a natural model in the calculus of communicating processes). The results obtained are derived by exploiting the special topological and combinatorial properties of the projective model and the polynomial operators defined on it. The topological methods employed in the proofs of the existence and uniqueness theorems use a combination of the following three ideas: compactness argument, density argument, and Banach’s contraction principle. As a converse to the uniqueness theorem it is also shown, using combinatorial methods, that in certain signatures guarded equations are the only ones that have unique fixed points.

MSC:

68N25 Theory of operating systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arnold, A.; Nivat, M., The metric space of infinite trees: Algebraic and topological properties, Fund. Inform., 3, No. 4, 445-476 (1980) · Zbl 0453.68021
[2] Baeten, J.; Bergstra, J. A.; Klop, J. W., Theoret. Computer Science, 51, Nos. 1/2 (1987) · Zbl 0621.68010
[3] de Bakker, J. W.; Zucker, J. I., Denotational semantics of concurrency, (Proceedings, 14th Sympos. Theory of Comput. (1982)), 153-158 · Zbl 0508.68010
[4] de Bakker, J. W.; Zucker, J. I., Processes and the operational semantics of concurrency, Inform. and Control, Vol. 54, Nos. 1/2, 70-120 (1982) · Zbl 0508.68011
[5] Bergstra, J. A.; Klop, J. W., Algebra of communicating processes, (de Bakker, J. W.; Hazenwinkel, M.; Lenstra, J. K., Proceedings, CWI Sympos. on Math. and Comput. Sci. (1986)) · Zbl 0605.68013
[6] Bergstra, J. A.; Klop, J. W., Fixed Point Semantics in Process Algebras, (Department of Computer Science Technical Report IW 206/82 (1982), Math. Centrum: Math. Centrum Amsterdam), Nov. · Zbl 0625.68023
[7] Bessaga, C., On the converse of the Banach fixed point principle, (Colloq. Math., 7 (1959)), 41-43 · Zbl 0089.31501
[8] Chang, C. C.; Keisler, H. J., (Model Theory (1973), North-Holland: North-Holland Amsterdam) · Zbl 0276.02032
[9] Dugundji, J., Topology (1966), Allyn & Bacon: Allyn & Bacon Rockledge, N.J · Zbl 0144.21501
[10] Dugundji, J.; Granas, A., (Fixed Point Theory, Vol. I (1982), PWN: PWN Warszaw) · Zbl 0483.47038
[11] Dieudonné, J., (Élements d’Analyse, Tom 1 (1968), Gauthier-Villars: Gauthier-Villars Paris)
[12] Van Glabbeek, R. J., Bounded nondeterminism and the approximation principle in process algebra, (Brandenburg, F. J.; Vidal-Naquet, G.; Wirsing, M., Proceedings, 4th Annual Symposium on Theoretical Aspects of Computer Science. Proceedings, 4th Annual Symposium on Theoretical Aspects of Computer Science, Passau, W. Germany, Feb. 1987 (1987), Springer-Verlag: Springer-Verlag Berlin/New York) · Zbl 0612.68025
[13] Hoare, C. A.R., (Communicating Sequential Process (1985), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ) · Zbl 0637.68007
[14] Janos, L., A converse of Banach’s contraction theorem, (Proc. Amer. Math., 18 (1967)), 287-289 · Zbl 0148.43001
[15] Lloyd, J., (Foundations of Logic Programming (1984), Springer-Verlag: Springer-Verlag New York/Berlin) · Zbl 0547.68005
[16] Milner, R., A Calculus of Communicating Systems, (Lecture Notes in Computer Science, Vol. 92 (1980), Springer-Verlag: Springer-Verlag Berlin/New York) · Zbl 0452.68027
[17] Rinow, W., Topologie (1975), VEB Deutscher Verlag der Wissenschaften: VEB Deutscher Verlag der Wissenschaften Berlin · Zbl 0317.54001
[18] Rounds, W. C., Applications of topology to semantics of communicating processes, (Seminar in Concurrency. Seminar in Concurrency, Lecture Notes in Computer Science, Vol. 197 (1985), Springer-Verlag: Springer-Verlag Berlin/New York), 360-372
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.