Friday, May 11, 2007

What is Time?

When studying process algebras for the description of timed behaviours, one of the early choices that have to be made has to do with the nature of "time". Is time discrete or dense? Is it represented by the natural numbers, by the non-negative rationals, by the non-negative reals or by some other structure?

In order to achieve a higher degree of generality, in the technical report

A. Jeffrey, S. Schneider, and F.W. Vaandrager. A comparison of additivity axioms in timed transition systems. Report CS-R9366, CWI, Amsterdam, 1993

the authors proposed to consider an algebraic definition of time domain. Since I like that definition, and I have it used it myself in a couple of papers, allow me to use this post to publicize it.

Define a monoid (X,+, 0) to be:
  • left-cancellative iff (x + y = x + z) implies (y = z), and
  • anti-symmetric iff (x + y = 0) implies (x = y = 0).
We define a partial order on X as x <= y iff x+z = y for some z in X. A time domain is a left-cancellative anti-symmetric monoid (D,+, 0) such that <= is a total order. Note that one can define a nation of subtraction over a time domain in the obvious way: if x <= y then y-x is the unique z such that x+z=y.

All of the structures mentioned above are, of course, time domains, but so is the set {0}. A time domain is non-trivial if D contains at least two elements. Note that every non-trivial time domain does not have a largest element, and is therefore infinite. Note moreover that + is not required to be commutative, so, for instance, suitable sets of ordinals with ordinal addition form a time domain.

I often find it worthwhile to work with time domains specified with the above degree of generality, and to use properties of specific "concrete" time domains only when they are really needed to obtain certain results. However, maybe this is the axiomatic devil in me talking :-)

Why hasn't the above definition become more popular in the literature on timed process algebras?

No comments: