Previous Next Contents

5  Some perspectives

There are numerous perspectives in static analysis of concurrent programs, computability and complexity issues in fault-tolerant distributed systems as well as in concurrent database theory, as I have been trying to explain in the previous sections. The aim here is not to list the possible research that could be carried on in these directions (good references for this are [Fajstrup et al., 1999] and [Herlihy and Rajsbaum, 1999]), but to look at other possible use of these techniques. For instance, Squier's theorem in rewriting systems theory, which gives a necessary condition for the existence of a presentation of a given monoid by a finite canonical rewriting system in terms of its homology (must be of finite dimension), seems very much related to the techniques presented above. It is definitely a computability result, as we have in fault-tolerant distributed systems theory, but for something which looks sequential (rewriting). As hinted in [Goubault, 1995a], this can be understood as a problem of concurrency theory in that the study of the confluence of rewriting systems is related to parallel reduction techniques (as in [LÚvy, 1978] for instance). The resolutions used in most of the proofs of this theorem, like in [Kobayashi, 1990], [Groves, 1991], [Anick, 1986], [Farkas, 1992] and [Lafont and ProutÚ, 1990] are very much like a Knuth-Bendix completion procedure, where higher-dimensional objects are filling in possible defects of local confluence. This looks like building higher-dimensional transitions implementing the parallel (confluent) reductions (see in particular [Groves, 1991] where the resolution is a cubical complex and in dimension one it is generated by the transition system coming from the reduction relation). Some other proof techniques use something which is very much like some kind of directed homotopy, as in [Squier et al., 1994] for instance. Other interesting relations should be studied concerning ``higher-dimensional'' word problems, as in [Burroni, 1991]. A hope is that geometry can also give some insight in logics, especially modal logics as in [Goubault-Larrecq and Goubault, 1999]. Finally, there is some intuition from theoretical physics that seems relevant to semantics, in particular concerning time and dynamical systems. Some of the concepts of M. Raussen's and L. Fasjtrup's articles in this issue are based on similar notions as in [Penrose, 1972]: some areas of physics (not classical mechanics though) have to consider time as non-reversible, hence have to construct some kind of directed topology.


Previous Next Contents