In the review debate about the recent submitted article by Cervesato, Franceschet, and Montanari, we have today the answer of Montanari to the questions asked by Liberatore (invited discussant). A number of fine points in the article are covered.

We also have contributions by Brandano and by myself in the discussion about ontologies of time. Recently, one part of that discussion has concerned some examples of uses of a less-than relation on intervals. It seems to me (in a moderator's role) that this problem does not require the attention of the full ENRAC readership. I have therefore asked those immediately concerned to resolve the disagreement in the way proposed by Leibniz (that is, by checking out carefully what are the consequences of the chosen axioms), and to report jointly when the question has been resolved.

That issue aside, the debate still seems to address several questions in parallel, including:

• What are examples of concrete problems that cannot (conveniently) be represented using a "standard" view of the time axis as e.g. timepoints = the real numbers; time-intervals = sets of points each defined by a lower bound  a  and an upper bound  b .
• Given that both timepoints and time-intervals are needed to have sufficient expressivity, what is the best way of defining those concepts and their relation?

Postscript versions of News Journals are now available from the ETAI/ ENRAC web site for all months up to and including March. The November, December, and March issues will be printed two weeks from now - please check for correctness if you have contributed.

These editions of the News Journals are the result of fairly extensive postediting of the original contributions, including a brushup of formulas (to make use of the expressiveness offered by latex compared to plain text) and of references. Incomplete references to published articles have been replaced by correct references drawing on the ACRES database. This has facilitated uniformly correct and complete citations. For the future it also paves the way for making direct electronic links available in an incremental fashion in the HTML version of the News Journals, within the restrictions, of course, that may be imposed by the respective copyright holders.

In your future contributions to our debates, please note that references may be cited simply as e.g. c-ecai-94-266, meaning conference - ECAI - 1994 - article starting on page 266. The full corresponding bibliographic information will be fetched automatically from the database and added to your contribution, at least for the main conferences and journals in our area. Journals are coded like e.g. j-jlc-4-26, meaning Journal of Logic and Computation, volume 4, page 26 ff. Conventions for additional cases (tech reports, etc) are available on request.

Don't forget that postscript versions of Newsletters (the daily issues) continue to be produced at the same time as the plaintext and html versions. If you prefer to read the present Newsletter off-line, you may wish to try the postscript variant. It's available from the web site like everything else.

Additional debate contributions have been received for the following article(s). Please click the title of the article to link to the interaction page, containing both new and old contributions to the discussion.

Iliano Cervesato, Massimo Franceschet, and Angelo Montanari
The Complexity of Model Checking in Modal Event Calculi with Quantifiers

Sergio Brandano:

In reply to Pat Hayes [ENRAC 17.5]

Sergios point seems to be that one can describe the line in terms of conventional open and closed intervals in such a way that no 'gaps' appear, so that the 'interval' between the open intervals   (a, b)   and   (b, c)   is the closed interval   [b]   containing a single point.

In my example, the temporal domain $S$ consists exclusively of intervals from the real-line and no total order relation was imposed, so that the interpretation for which one can describe the line with that domain is surely not correct. If one restricts  S  to the case of intervals from the positive real-line, for example, then  S  is a tree with a continuum of branches.

The question is whether this standard mathematical view of the line is the most suitable for capturing linguistic intuition or for action reasoning. For example, we want to be able to assert that a light is off before time  t  and on after time  t

In your approach the switching action takes place at time  t , while the process of turning on the light does not necessarily require a single time-point. Anyway, according to the classical approach (linear point-based temporal-domain) one may easily capture the proper intuition with a simple function of time:

 \[ to\_switch(s,\tau,t) = 
	\cases{ {\rm off}               & if $\tau = s$       \cr 
                {\rm on} \vee {\rm off} & if $\tau \in (s,t)$ \cr
                {\rm on}                & if $\tau = t$}
 \]

where the interval   [s, t]   is the switching interval, which may also be point-like, of course. The switching interval is properly that time-interval where the action of switching on the light is performed. Please note that  s  and  t  may also be variables.

Now, assume the light is initially "off". Then it will remain "off" until  s , because of the assumption of inertia. From  s  to  t  the value will change according to the definition of the switching action, while at  t  the light will be surely "on". The light will be "on" at  t  and at every timepoint after  t  until another action will occur to change it's state. As simple as this...

In any case, many users of temporal ontologies do not wish to assume continuity or even density, for reasons of their own, and so a general-purpose temporal ontology should therefore not make such unnecessarily strong assumptions as Sergio's 'completeness' axiom. Temporal database technology usually assumes times are discrete, for example.

(a) When implementing whatever formalism on a resource-bounded machine, compromises are never enough, otherwise we shall bound ourselves when designing them. On the other hand, I like to observe that humans formulated the notion of continuity in their mind, although humans too are resource-bounded. It is also true that not every human knows about continuity, but some of them does it. In any case the notion of continuity does exists, at least on paper.

(b) The problem that comes when aiming at generality (as in this debate?), is one shall include all possible cases, instead of excluding those which are of no interest for someone. Personally, I like to consider problems within Newtonian physics as being an important part of Reasoning about Actions and Changes, where continuity plays an fundamental role when idealizing the physical world. Furthermore a continuous temporal-domain subsumes the case of integer time, as well as the case of rational time, so that it is general enough to embrace all possible cases.

Therefore, in my opinion, the axiom of completeness is a good assumption, at least within the classical point-based approach. The purpose of my example with  S , was an ad-hoc example to show the axiom of completeness adequate as well for an interval-based temporal domain. As an immediate consequence of that result, the dividing instant problem is then solved for those interval-based formalisms where this axiom will be properly adopted. Still remains the question whether at least one problem exists that needs to introduce intervals into the temporal domain. Personally, I think this problem does not really exists.

Finally, I would like to resume Jixin's original statements in ENRAC 13.3:

(1) For general treatment, both intervals and points are needed. (2) To overcome the so-called Dividing Instant Problem, that is the problem in specifying whether intervals is "open" or "closed" at their ending-points, both intervals and points should be treated as primitive on the same footing.

My reply to (1) was: [ENRAC 8.5]

Does there exist at least one problem (within R.A.C) that needs to introduce intervals into the temporal domain?

My reply to (2) was the example with  S , where just intervals are needed.

Best Regards Sergio

Erik Sandewall:

Pat,

You wrote (ENRAC 17.5]:

The question is whether this standard mathematical view of the line is the most suitable for capturing linguistic intuition or for action reasoning. For example, we want to be able to assert that a light is off before time  t  and on after time  t  without having to commit ourselves to its being either on or off at that time, but also without sacrificing the assumption that it is always either on or off.

The most natural way of dealing with such a situation, it seems to me, is to admit that one's axioms allow two kinds of models: those where the light is on at time  t , and those where it is off. The assumption that light is either on or off holds in each of the models, but the axioms don't imply one or the other.

The alternative that has occurred in the present discussion, and proposed as a way of dealing with the "dividing instant problem" is the use of a punctuated timeline where the domain of timepoints is chosen e.g. as  Re - B  where  Re  is the real numbers and  B  is a finite set of "breakpoints", typically chosen as the times where actions start or end. If we ignore questions of how this domain is specified in terms of axioms or how intervals are formally defined, this seems to be the essence of how one would deal with the DIP without going to very unconventional concepts of time.

Given that the standard view already exists, it seems worthwhile to understand what the concrete reasons would be for replacing it with the punctuated timeline ontology. Apart from the purely subjective reasons (that is, some people prefer to do it that way) I wonder what results have been obtained using punctuated or other nonstandard ontologies, and which are not trivially translatable back to the standard view. The following would seem to be interesting results for this purpose:

• Expressiveness in a concrete scenario. This ought to be a scenario that can't be properly expressed in the standard ontology, but which can be expressed in the nonstandard one.
• Algorithms or other implementation techniques. Is there some algorithm that works with a punctuated timeline and that outperforms those that don't?
• Validation and range of applicability results. These are results stating that or when a certain entailment method is correct, that is, it obtains exactly the intended models viz conclusions. Have some such results been obtained using nonstandard ontologies?

Please feel free to add more categories to the list. (In the methodology discussion at the NRAC workshop at IJCAI last year we got to more than ten such categories).

I realize of course the purely philosophical and/or logical interest in analyzing different possible concepts of time, but from an AI point of view there is no point in pursuing an approach if it doesn't deliver any results. I haven't been able to see any indications of such concrete results from the present discussion or from the articles that have been referenced in it. (That most work in temporal databases uses discrete time doesn't say anything about the choice between a standard or a punctuated real timeline, does it?)

Although I'd prefer to see algorithmic results or range of applicability results, a few words about expressiveness since after all that's also a relevant type of achievement. One nice scenario for hybrid change (that is, continuous and discrete) is the impact problem that Persson and Staflin used in their ECAI 1990 paper [c-ecai-90-497]. It goes like this: two solid spheres B and C are lying side by side on a horizontal surface, B to the left of C. A third sphere, A, comes rolling from the left and hits B. As we know from physics, the result of the impact is that A stops, B stays, and C starts moving towards the right. This particular exercise has been solved in 1990, but is there now some harder one that makes essential use of punctuated time ontology?

Erik