Algebra of automata versus Process algebra
The work I have been pursuing for some years with Nicoletta Sabadini and collaborators (Piergiulio Katis, Luisa de Francesco Albasini) has been the study of distributed and concurrent systems using algebras of automata, with the main operations being sequential and communicating-parallel composition.
This is in contrast with the mainstream of concurrency which studies process algebras.
Why our contrary attitude? I would like to explain the point of view.
In a nutshell our view is that semantics should come before syntax. Process algebra takes the opposite point of view, syntax before sematics.
Let's take an analogous development in mathematics, the study of numbers.
Numbers come first. Then, after a long time, operations on numbers. Then a language for talking about numbers and their operations - polynomials. Finally, equations between polynomials.
We believe the same sequence should occur in the theory of systems. Discrete systems have states and transitions, that is, are graphs. They have interfaces and sequential and (communicating) parallel operations (including feedbacks). The languages for describing systems are the free algebras. Finally equations in the algebra (recursion) may be used to specify systems.
Process algebras take the opposite point of view. Beginning with a vague intuition about systems, processes are defined to be solutions of equations of a free algebra. The danger of this sudden jump to the language before a careful mathematical analysis of systems and their operations is that the wrong algebra with the wrong operations may be taken. Milner's CCS does not have a sequential composite of systems (only that a process may be preceded by a transition). Union is used instead of disjoint union in the other sequential operation. The communicating parallel operation is based on a vague broadcast idea.
Of course, in the end of a development as proposed by us, free algebras and recursion arise, but only when the correct operations have been identified. At this stage also other semantics may be identified (in the example of numbers, real numbers, complex numbers, rings of functions, ...). If the algebra of systems has been developed correctly, at least a part should have continuous systems as models, thus allowing the confrontation between discrete and continuous.
Some years ago we produced a process algebra based on our idea of parallel. Recently Pawel Sobocinski is developing a process algebra based on our idea of communicating parallel (but not our view of sequential).
This is in contrast with the mainstream of concurrency which studies process algebras.
Why our contrary attitude? I would like to explain the point of view.
In a nutshell our view is that semantics should come before syntax. Process algebra takes the opposite point of view, syntax before sematics.
Let's take an analogous development in mathematics, the study of numbers.
Numbers come first. Then, after a long time, operations on numbers. Then a language for talking about numbers and their operations - polynomials. Finally, equations between polynomials.
We believe the same sequence should occur in the theory of systems. Discrete systems have states and transitions, that is, are graphs. They have interfaces and sequential and (communicating) parallel operations (including feedbacks). The languages for describing systems are the free algebras. Finally equations in the algebra (recursion) may be used to specify systems.
Process algebras take the opposite point of view. Beginning with a vague intuition about systems, processes are defined to be solutions of equations of a free algebra. The danger of this sudden jump to the language before a careful mathematical analysis of systems and their operations is that the wrong algebra with the wrong operations may be taken. Milner's CCS does not have a sequential composite of systems (only that a process may be preceded by a transition). Union is used instead of disjoint union in the other sequential operation. The communicating parallel operation is based on a vague broadcast idea.
Of course, in the end of a development as proposed by us, free algebras and recursion arise, but only when the correct operations have been identified. At this stage also other semantics may be identified (in the example of numbers, real numbers, complex numbers, rings of functions, ...). If the algebra of systems has been developed correctly, at least a part should have continuous systems as models, thus allowing the confrontation between discrete and continuous.
Some years ago we produced a process algebra based on our idea of parallel. Recently Pawel Sobocinski is developing a process algebra based on our idea of communicating parallel (but not our view of sequential).
Labels: category theory, computing, Optimistic
posted by Unknown at 8:21 AM
0 Comments:
Post a Comment
<< Home