V. R. Pratt
ABSTRACT
We describe a model of net-connected processes that amounts to a reformulation of a model derived by Brock and Ackerman from the Kahn-McQueen model of processes as relations on streams of data. The reformulation leads directly to a straightforward definition of process composition. Our notion of processes and their composition constitutes a natural generalization of the notion of functions and their composition. We apply this definition of process composition to the development of an algebra of processes, which we propose as supplying a formal semantics for a language whose domain of discourse includes nets of interconnected processes. This in turn leads us to logics of such nets, about which we raise three open and fundamental problems: existence of a finite basis for the operations of the language, finite axiomatizability of the equational theory, and decidability of this theory. A natural generalization of the model deals with the time complexity of computations.
- Abrahamson, K., Modal Logic of Concurrent Nondeterministic Programs, Preprints of the International Symposium on Semantics of Concurrent Computation, Evian-les-Bains, July 1979.]] Google Scholar
Digital Library
- Ackerman, W.B. and J.B. Dennis, A Value-Oriented Algorithmic Language, MIT LCS TR-218, June 13, 1979.]] Google ScholarDigital Library
- Brock, J.D. and W.B. Ackerman, An Anomaly in the Specifications of Nondeterminate Packet Systems, Computations Structures Group Note CSG-33, MIT-LCS, Nov. 1977.]]Google Scholar
- {3a} Brock, J.D. and W.B. Ackerman, Scenarios: A Model of Non-Determinate Computation. In Lecture Notes in Computer Science,107: Formalization of Programming Concepts, J. Diaz and I. Ramos, Eds., Springer-Verlag, New York, 1981, 252--259.]] Google ScholarDigital Library
- Dijkstra, E., Guarded Commands, Nondeterminacy and Formal Derivation of Programs, CACM 18, 8, 1975.]] Google ScholarDigital Library
- Harel, D., Kozen, D., Parikh, R., Process Logic: Expressiveness, Decidability, Completeness, IBM Research Report, April 1980.]]Google Scholar
- Hewitt, C. and H.G. Baker, Laws for Communicating Parallel Processes, IFIP 77, 987--992, North-Holland, Amsterdam, 1977.]]Google Scholar
- Hoare, C.A.R., Communicating Sequential Processes, CACM, 21, 8, 666--672, August, 1978,]] Google ScholarDigital Library
- Kahn, G., The Semantics of a Simple Language for Parallel Programming, IFIP 74, North-Holland, Amsterdam, 1974.]]Google Scholar
- Kahn, G. and D.B. MacQueen, Coroutines and Networks of Parallel Processes, IFIP 77, 993--998, North-Holland, Amsterdam, 1977.]]Google Scholar
- Kleene, S.C., Representation of Events in Nerve Nets, in Automata Studies, (eds. Shannon, C.E. and J. McCarthy), 3--40, Princeton University Press, Princeton, NJ, 1956.]]Google Scholar
- {10a} Lynch, N.A. and M.H. Fischer, On Describing the Behavior and Implementation of Distributed Systems, Theoretical Computer Science,13, 17--43, 1981.]]Google ScholarCross Ref
- MacQueen, D.B., Models for Distributed Computing, Technical Report 351, INRIA, Paris, 1979.]]Google Scholar
- Milner, R., Synthesis of Communicating Behavior, 7th Symp. on Math. Found. of Computer Science, Zakopane, Poland, Sept. 1978.]]Google Scholar
- Milner, R., A Calculus of Communicating Behavior, Springer-Verlag Lecture Notes in Computer Science, 92, 1980.]] Google ScholarDigital Library
- Parikh, R., A Decidability Result for a Second Order Process Logic. Proc. 19th IEEE Symp. on Foundations of Computer Science, 177--183, Ann Arbor, Oct. 1978. Also M.I.T. Laboratory for Computer Science Technical Memorandum No. 112, September 1978.]]Google ScholarDigital Library
- {14a} Paterson, R. and J. Staples, An algebra of processes with a finite basis, Technical Report No. 29. Dept. of Comp. Sci., U. of QLD, St. Lucia, QLD., Australia, June 1981.]]Google Scholar
- Petri, C.A., Introduction to General Net Theory, Springer-Verlag Lecture Notes in Computer Science, to appear 1981.]] Google ScholarDigital Library
- Pnueli, A., The Temporal Logic of Programs, 18th IEEE Symposium on Foundations of Computer Science, 46--57. Oct. 1977.]]Google Scholar
- Pratt, V.R., Process Logic, Proc. 6th Ann. ACM Symp. on Principles of Programming Languages, 93--100, San Antonio, Texas, Jan. 1979.]] Google ScholarDigital Library
- Pratt, V.R., Dynamic Algebras and Nature of Induction, Proc. ACM Symposium on Theory of Computation, Los Angeles, May, 1980.]] Google ScholarDigital Library
- Redko, V.N., On Defining Relations for the Algebra of Regular Events, (Russian), Ukrain. Mat. Z., 16, 120--126, 1964.]]Google Scholar
- Segerberg, K., A Completeness Theorem in the Modal Logic of Programs, Preliminary report. Notices of the AMS, 24, 6, A-552. Oct. 1977.]]Google Scholar
- On the composition of processes
Recommendations
Composition and Independence of High-Level Net Processes
Mobile ad-hoc networks (manets) are networks of mobile devices that communicate with each other via wireless links without relying on an underlying infrastructure. To model workflows in manets adequately a formal technique is given by algebraic higher-...
Coalgebraic semantics for timed processes
Special issue: Seventh workshop on coalgebraic methods in computer science 2004We give a coalgebraic formulation of timed processes and their operational semantics. We model time by a monoid called a ''time domain'', and we model processes by ''timed transition systems'', which amount to partial monoid actions of the time domain ...
Comments