Today

Today, we announce that Iliano Cervesato, Massimo Franceschet, and Angelo Montanari have submitted their KR accepted article to the ETAI. This submission uses the alternate ETAI submission procedure for conference published articles, which goes as follows. The version of the article that has appeared or is about to appear in a major conference proceedings, is submitted without any changes to the ETAI discussion process. In order to be instantly accessible to the readership, an electronic copy of the article that identically reproduces the one printed in the proceedings, is posted on-line. (It's the authors' responsibility that there is no discrepancy between the proceedings and on-line versions). This means that discussion can start without needing to convert the article to electronic-press format. This reformatting can wait until a bit later in the reviewing process. The bottom line is that it's now much easier to submit articles to the ETAI.

Today's issue also contains an editorial policy statement about new measures for getting discussions started about articles.

Finally, the discussion about ontologies of time continues with Sergio Brandano's answer to Jixin Ma.

ETAI Publications

In two recent issues of this Newsletter, several authors of earlier ETAI accepted articles have commented on their experience of the ETAI publication process, namely Rob Miller, Tony Kakas, and Michael Thielscher. Their joint suggestion to organize articles and tables of contents in the ETAI in such a way that readers are encouraged to download and read comments together with articles, can be realized right away.

A common observation from these authors was that they wanted their articles to be discussed: having many contributions were seen as an advantage, few contributions as a disappointment. Similar reactions have been voiced by other readers of this Newsletter which I have talked to: as an author, it doesn't matter if I encounter critique, since after all I have a chance to respond to it, but I do hope for some feedback.

It is interesting, therefore, to observe the dynamics of discussions in the Newsletter: what is it that causes the discussions to start and to pursue? It appears that many contributions are written in response to earlier discussion contributions, rather than to an article in itself. As an editorial experiment, I will therefore sometimes start discussions about submitted articles by asking one or a few peers to ask some initial questions or give some initial comments. These initiators will be asked to be somewhat critical, if at all possible, and not just to say that everything is fine. Let it be known in advance, therefore, that this is the role they have been asked to play, and that it's part of the game.

The following article has been received by the present ETAI area, which means that it will be open for a three-month discussion period, followed by the closed peer-review decision on whether it will be accepted by the ETAI. All readers of this Newsletter are invited to participate in the discussion.

Please don't be shy to ask questions; it is actually in the author's interest to receive tough questions. Just like at an internal seminar, they give him or her a chance to show that he/she is able to answer well, and they give valuable feedback. Also, since the article has already been published (but not yet refereed to journal standards), it is citable anyway, so tough questions do not deprive the author of being "on record" with the article.

The open reviewing discussion of this article will be based on the paper as published in the conference proceedings mentioned below, together with the electronic copy of the article that has been posted on-line by the author(s). The electronic copy can be accessed by clicking the title of the article. Clicking "[interactions]" leads to the on-going question-answer debate about the article, with options for submitting a question or comment to the present Newsletter editor.

Iliano Cervesato, Massimo Franceschet, and Angelo Montanari

The Complexity of Model Checking in Modal Event Calculi with Quantifiers.

Abstract: Kowalski and Sergot's Event Calculus (EC) is a simple temporal formalism that, given a set of event occurrences, derives the maximual validity intervals (MVIs) over which properties initiated or terminated by these events hold. It does so in polynomial time with respect to the number of events. Extensions of its query language with Boolean connectives and operators from modal logic have been shown to improve substantially its scarce expressiveness, although at the cost of an increase in computational complexity. However, significant sublanguages are still tractable.

In this paper, we further extend EC queries by admitting arbitrary event quantification. We demonstrate the added expressive power by encoding hardware diagnosis problems in the resulting calculus. We conduct a detailed complexity analysis of this formalism and several sublanguages that restrict the way modalities, connectives, and quantifiers can be interleaved. We also describe an implementation in the higher-order logic programming language lambda-Prolog.

Debates

Sergio Brandano:

In reply to Jixin Ma (ENRAC 7.5.1998)

Pat's example becomes invalid only after you made the "minor adjustment" that replaces the relation   <   in your hypothesis  <s1,t1> < <s2,t2>  by   <  , that is  <s1,t1> < <s2,t2> . (Is this an alternative?)

Ex falso sequitur quodlibet!

The only one "minor adjustment" I made consists in the first four lines of my contribution to ENRAC 3.5.1998, where no inequality appears at all. Concerning the hypothesis, I remind you what I wrote in ENRAC 24.4.1998:

Suppose now that  <s1,t1> < <s2,t2> . The axiom of completeness states the existence of  xi in S  such that  <s1,t1> < xi < <s2,t2> .

I observe Pat quoted me correctly in ENRAC 3.5.1998.

So, you do need alternation, don't? (And this is just for the case ...

The axiom of completeness imposes   <  , so no "alternation" is needed at all. The reason why I wrote   <   instead of   <   is simply due to my need to stress the example, since the case  <s1,t1> = <s2,t2>  is trivial. If you like to check, the reference is ENRAC 24.4.1998.

...when you construct intervals out of points. In the case where intervals are taken as primitive, the need of such alternative is indeed more conceptually necessary). However, your adjustment is not enough, or you haven't reached the proper form for general treatments. In fact, you need address the issue regarding different cases. To see this, you may just consider the difference between the case where at least one of  <s1,t1>  and  <s2,t2>  is "closed" at  t1  (  = s2 ), and the case where both  <s1,t1>  and  <s2,t2>  are "open" at  t1  (  = s2 ). In the former case, you need use   <   in the hypothesis; otherwise, Pat's example will be a valid counterexample. In the latter case, you need

... at least one is closed. So we have, since  s2 = t1 :

1.   [s1, t1]  <  [t1, t2]  
2.   [s1, t1]  <  (t1, t2]  
3.   [s1, t1)  <  [t1, t2]  

where  xi =  [t1, t1] in S  in all cases.

Note I used   <  , as required by the axiom of completeness. If I use   <  , as you recommend, then all cases trivially fail.

Pat's example:

• trivially fails when using   <  ,
• trivially succeeds ( xi =  [q, q]  ) when using   <  .

use   <   in the hypothesis; otherwise, your axiom cannot not prevent a "gap" between   <s1, t1)   and   (s2, t2>  , that is, there is no guarantee that the singleton   [t1, t1]   is contained in  S  (Do you think this is consistent with the "classical" concept of contiunity?).

... the latter case. So we have, since  s2 = t1 :

4.   <s1, t1)  <  (t1, t2>  

where  xi =  [t1, t1] in S . I used   <   here too.

So, the axiom of completeness has no problems with your examples.

Concerning the first part of your message, as you wrote in it, it was entirely based on the DIP problem and the above argument-examples.

while I (and many others) have seen the convenience of using intervals, I can also see the need of them. In fact, there have been quite a lot of examples (MANY) in the literature that demonstrated the need of time-intervals (or time-periods). Haven't you ever encountered any one of them? Or you simply cannot see anyone of them is convincing?

The problem about intervals is whether one needs to introduce them into the temporal domain, and the few argument-examples I encountered are far from being convincing. Furthermore, in this debate, you and Hayes proposed the DIP, and I refuted it.

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

The other problem is:

There exists at least one problem (within R.A.C.) that can not be solved with a continuous temporal domain, so that to justify a temporal domain with non-uniform continuity?

This debate aims at generality, surely does not aim at completeness of case examples. If many examples do exist, then this is the proper debate where at least the most representative of them should appear "naked" under the spotlight, for general benefit. On the other hand, I note that more than two weeks are now passed from my criticism, and no such representative example appeared.

Sergio