News Journal on Reasoning about Actions and Change

Dated: 3.5.1998

Several contributions have accumulated since the previous issue.

1. The article by Michael Thielscher, "A Theory of Dynamic Diagnosis", has been accepted to the ETAI following two positive referee reports. One of the referees has made a few suggestions for changes to the article; these suggestions follow below and have been posted on the article's interaction page.

2. Antonis Kakas and Rob Miller have answered to the questions and suggestions by the referees to their article, "Reasoning about Actions, Narratives and Ramification" which was recently accepted to the ETAI. Their answers follow below and have been posted as usual.

3. In the light of the refereeing of those two articles, the present Newsletter editor comments on (1) the open relationship between authors, referees, and readership in the ETAI, (2) how should the advent of electronic publication and communication change our expectations as to how scientific articles ought to be written.

4. The debate about ontologies of time continues with contributions by Sergio Brandano, Pat Hayes, and Jixin Ma.

Dated: 4.5.1998

Already today, we have two answers for the discussion about ETAI publication styles that was opened in yesterday's Newsletter. Also, a contribution by Sergio Brandano re ontologies of time.

Dated: 7.5.1998

Today's issue contains Michael Thielscher's answers to the referee's comments for his accepted article, and his comments on the ETAI reviewing and publication procedure. Also, Jixin Ma on the ontology of time.

Dated: 8.5.1998

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.

Dated: 12.5.1998

It appears that a number of our readers like to print the Newsletter issues and read them from paper, for example while travelling. Until now, Newsletters have only been produced in plaintext and HTML format. As a result of some additional hacking, we know offer past and forthcoming Newsletters in postscript format (via Latex) as well. At present, most Newsletters issues during 1998 exist in postscript (although still with minor bugs in some places), and the new software makes it possible to produce forthcoming Newsletter issues in postscript at once.

Another result of this software step is that the generation of the monthly News Journal issues in postscript goes more smoothly than before. The News Journal issues for January and February have been posted in the ENRAC web structure (go to the page for back issues!), and the following months are forthcoming. Participating authors, please check that your contributions have been rendered correctly. These News Journal issues will be published officially by the end of the month, allowing some time for corrections.

Since the News Journal in postscript issue is the official appearance of the discussions that evolves in this Newsletter, it is recommended to use it for any citations e.g. from regular articles. The News Journal is formally published, it has a journal "look and feel" with respect to e.g. page layout and page numbering.

The present Newsletter issue contains a contribution by Jixin Ma to the discussion about Ontologies for time.

Dated: 17.5.1998

Today's issue contains the summary (longer and more concrete than an ordinary abstract) of the article by Cervesato, Franceschet, and Montanari which was recently received by the ETAI. Also, we have an invited comment-and-question contribution by Paolo Liberatore for the same article.

We have been using summaries since the beginning of ETAI as a help for readers to orient themselves rapidly in recent results. The use of invited commentary is a more recent idea. One more invited comment for the same paper has been promised.

The present Newsletter issue also contains a contribution by Pat Hayes to the discussion about ontologies of time. After a quite long debate, it seems that the dust is beginning to settle there.

Michael Thielscher
A Theory of Dynamic Diagnosis

Antonis Kakas and Rob Miller
Reasoning about Actions, Narratives and Ramification

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

Dated: 8.5.1998

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.

Iliano Cervesato, Massimo Franceschet, and Angelo Montanari

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

Iliano Cervesato, Massimo Franceschet, and Angelo Montanari
The Complexity of Model Checking in Modal Event Calculi with Quantifiers.
[summary]
[Interactions]

Dated: 17.5.1998

Summary

The Event Calculus

The Event Calculus, abbreviated EC, is a simple temporal formalism designed to model and reason about scenarios characterized by a set of events, whose occurrences have the effect of starting or terminating the validity of determined properties. Given a possibly incomplete description of when these events take place and of the properties they affect, EC is able to determine the maximal validity intervals, or MVIs, over which a property holds uninterruptedly.

State-of-the-art

A systematic analysis of EC has recently been undertaken in order to gain a better understanding of this calculus and determine ways of augmenting its expressive power. The keystone of this endeavor has been the definition of an extendible formal specification of the functionalities of this formalism. This has had the effects of establishing a semantic reference against which to verify the correctness of implementations, of casting EC as a model checking problem, and of setting the ground for studying the complexity of this problem, which was proved polynomial. Extensions of this model have been designed to accommodate constructs intended to enhance the expressiveness of EC@. In particular, modal versions of EC, the interaction between modalities and connectives, and preconditions have all been investigated in this context.

Contributions

The main contributions of the present paper are the following:

• The extension of a family of modal event calculi with quantifiers. We enhance the expressive power of EC by considering the possibility of quantifying over events in queries, in conjunction with boolean connectives and modal operators. We also admit requests to check the relative order of two events. We thoroughly analyze the representational and computational features of the resulting formalism, that we call QCMEC@. We also consider two proper sublanguages of it, EQCMEC, in which modalities are applied to atomic formulas only, and CMEC, which is quantifier-free.

• The use of the proposed formalisms to encode diagnosis problems. We consider a case study taken from the domain of hardware fault diagnosis. We model it using EC and use the various extensions of EC to draw conclusions about it.

• The use of the higher-order features of modern logic programming languages in temporal reasoning. We provide an elegant implementation in the higher-order logic programming language  lambda Prolog and prove its soundness and completeness.

• Analyzing the complexity of model checking in the proposed extensions of EC@. We prove that model checking in CMEC, EQCMEC, and QCMEC is PSPACE-complete. However, while solving an EQCMEC problem is exponential in the size of the query, it has only polynomial cost in the number of events, thus making EQCMEC a viable formalism for MVI verification or computation. Since in most realistic applications the size of databases dominates by several orders of magnitude the size of the query, the former is asymptotically the parameter of interest.

From: Erik Sandewall on 3.5.1998

Two more articles have now been accepted to the ETAI after an extended period of open review discussion followed by confidential refereeing. At this point, I wish to raise some possibly controversial questions that relate to the referee reports, namely: Is it necessarily the case that articles that are published in this on-line and networked medium ought to be written in exactly the traditional style? Maybe the classical advise for How To Write A Scientific Article ought to be amended somewhat?

Note however that I am not going to propose using hypertext in extremis, or any other revolutionary new ideas. On the contrary, I believe it's important that articles continue to have their traditional look and feel from a typograhpic point of view, and that both authors and readers feel comfortable with our way of doing things. Reasonable changes to a moderate extent is the key. However, the present topic is revolutionary in another sense: you don't usually question the opinion of a referee. Only the transparency policy of ETAI makes it possible. Before I proceed on that topic, first a few words of introduction and background.

The rate of articles in ETAI is not yet very high, but this is not a problem. Since we are using a novel publication paradigm, it is in fact very useful that we get enough time for analysis and discussion with the peer communities before a larger flow of articles begins to come. We also don't have any quota where a certain number of hundred pages have to be filled each year: our publication scheme is completely elastic with respect to volume.

One of the characteristic and unique features of the ETAI is the egalitarian relationship between all actors, including between reviewers and authors. The reviewer/referee in a traditional journal habitually assumes the pose of ultimate authority, and review reports tend to use phrases such as "the article is lacking in the following respects", "the author should better explain how his (her) approach is able to deal with the following problem", and so on. Behind these phrases there is one of our colleagues, and if we met face to face she (he) would not of course use this way of talking.

In the ETAI, open discussion is the basic idea. Ideally, all feedback to the authors should occur in the open debate, and referees should only vote "accept" or "don't accept". In practice, it turns out that several of the referees get to think of possible improvements to the article as well, but even in this case their suggestions are written in the same collegial style as is used in the open discussion. Please take a look at the comments by "Anonymous Referees" for the articles by Thielscher and by Kakas and Miller for some examples of how reviewers and referees so-to-say look the authors in the eyes as they ask questions and make suggestions with respect to the article that's being considered.

It has been interesting and encouraging to see how the authors have reacted when the review comments for their articles were posted on the web, first the open discussion and then the comments by referees. Until now I have only heard positive reactions and no negative comment at all, and I do believe that the civil tone that we have adopted has contributed to that result. (Comments by the authors on this topic would be welcome!)

The intrinsic transparency of the review process gives the authors a chance to answer to the referees. It also gives the rest of us a chance to listen in to the discussion between authors and referees, and this may be very useful for understanding the contribution as well as for evaluating it. An additional advantage is that this provides an entry point to a common discussion about the topic that I mentioned in the introduction: what style ought to be used in the articles in our field. Referees are, after all, the guardians of our quality criteria, so they must be involved in any changes of practice. Thus, the following questions are posed both to the present referees, and to the whole readership.

When a referee feels that additional clarification is needed, should this automatically translate into a suggestion to amend the article? The alternative would be that the referee just asks the question, the author gets to answer it, and the question and the answer are posted in ETAI's article interaction page where they are just as easily available as the article itself. Consider, for example, the suggestions of the third referee of the Kakas and Miller article: would you rather have the answers to those questions integrated with the article, or represented separately?

I don't imagine that all reviewers' comments for all articles can best be dealt with separately, but maybe for many of them this would be appropriate. After all, dialogue tends to be more lively than monologue, and seeing what questions others have asked may be more interesting than just reading passages of an article that provide answers to untold questions.

Do networked articles need to be as self-contained as articles in the classical medium? If an article in a conventional journal forces the reader to refer to another article for essential material (such as background, motivation, or definitions) then it may be very inconvenient for the reader to find the cited material. In the on-line context this is not so: a hot link in an ENRAC-style footnote (as used in the version of ENRAC that uses frames) allows the reader to click her way instantly to the cited material. In this light, what stand do we wish to take on the third referee's suggestions for additional background material in the Kakas and Miller paper?

Naturally, my references to the referee reports is for examplification only: the refereeing for these articles has been concluded, and it's not my intention to submit the recommendations of the referees to a referendum each time an article is up for acceptance. It is also clear that the recommendations of the present referees are perfectly consistent with traditional criteria for high-quality journals in our field. It's exactly for this reason that these referee reports may also be useful as a starting point for an important discussion: can we improve the quality of form without sacrificing (and hopefully also improving) the quality of content in research articles that are published in the electronic medium, such as the ETAI?

Comments from the readership are welcome on both of these questions, as well as on the general issue of how we can make the best use of electronic communication and publication in our area of research.

From: Rob Miller on 4.5.1998

Dear Erik,

First of all, I know I speak for many people when thanking you for the enormous effort you've put into the ETAI and the newsletter over the last year or so. People are clearly enjoying the newsletter a great deal, and it's really become part of the culture of the 'reasoning about actions' community.

Publishing an article in the ETAI has been a very positive experience for Tony and me. We had a great deal of useful feedback, and my initial worries about the subsequent status of our paper, i.e. whether it would be generally accepted as a respectable 'journal' paper, have proved unfounded. (I'm in a good position to judge this, because I recently changed jobs, and subsequently asked my new employers what their attitude had been towards this publication when evaluating my CV.) The question-and-answer sessions in the newsletter and in the online interactions page, aside from being useful and good fun, have provided good publicity for our work. So, in short, the reviewing and debating mechanisms you've set up have worked very well for us.

I therefore have only minor suggestions for changes and additions to the ETAI publication and reviewing process:

1. Encourage authors to include a statement in each ETAI article along the lines of:

   This article is best read in conjunction with the online interaction at http://......

2. Encourage the anonymous referees to post questions on the the interactions page during the 3 month period in which they're reviewing the article. In conventional journal reviewing, it's not unusual for referees to ask the authors (through the journal's editor) for clarification on various points, before making a final decision about the paper. I see this as a very healthy process which can easily be mirrored on the ETAI web pages.

3. At present, after the initial 3 month public interaction period, authors are invited to revise their paper if they wish before it is sent for anonymous review. But perhaps it would be better if the anonymous reviewers simply referee the original paper, in conjunction with the answers given to the questions posted online.

   Perhaps the anomymous reviewers could then have 3 options (similar to the options for many conventional journals):

   1. reject the paper,
   2. accept the paper but with 'compulsory' revision (and perhaps re-reviewing), or
   3. accept the paper with 'voluntary' revision.
   In this way, there would be a maximum of 2 versions of the paper online (the second appearing after 6 months rather than 3 months), so that version control wouldn't be too much of a problem. (We felt reluctant to post 3 versions of our paper in such a short time period, even though our 3rd referee felt that this might have given a better final product.)

As regards the two questions that you posed in the last newsletter, my guess is that different authors will have different attitudes; some will still like to make their articles as self-contained as possible, others will be happy to leave them as starting points for an online discussion. My view is that the ETAI can and should accomodate this range of preferences - hence suggestion (3) above.

Regards, Rob

From: Leora Morgenstern on 4.5.1998

Erik,

I guess I've been lurking long enough, and I should finally just get out there and contribute to the Newsletter in particular on the question of novel publication styles. I may be a bit of a traditionalist with respect both to the issue of background material and to clarifications, and I'd vote for having these incorporated into the actual article. There is still a lot to be said for being able to print out an article and having a clear statement of the background problem in that article. I also believe that the way the author summarizes and presents background work is important; it sheds light on the author's perspective on the work. In the same way, I think it's important for the author to encapsulate the essentials of the dialogues in this forum, and to incorporate them into his article.

As a related point, I think the exercise of writing in a succinct way the background material and the main point of the dialogues serves to clarify the author's thoughts and is not something we want to give up.

Leora

From: Michael Thielscher on 7.5.1998

First of all I can only side with Rob in saying that the experience of publishing an article in the novel way was both exciting and instructive. It took some time for the discussion on my paper to get going, but in the end it proved very useful and led to important improvements. It was, however, never as lively as, say, the discussion on Tony Kakas and Rob Miller's submission. I recently told Rob that I envied the two of them for their paper receiving so much attention. Although his impulsive remark was that there are two sides to everything, I guess that in the end the authors of articles much debated upon can be most happy about the public attention. Thus a lesson that might be learned from the experience with ETAI so far is that the more controversial a paper is, the more is gained by submitting it to the new publication scheme. And of course this holds vice versa: ETAI seems to profit most from controversial papers.

The editor of the Newsletter raised the question whether networked articles should be as self-contained as articles in the classical medium. Indeed the new medium offers new possibilities. If there is a good general introduction to the topic of one's paper, then adding a link might often be a better idea than just copying the contents in one's own words. In this way an article could be made accessible for a readership with truly different background. For classical journal papers, authors always have to struggle with the problem of how much background they should provide. Some papers even include choicepoints of the form "The reader who is familiar with topics x, y, z,... may skip sections a, b, c, ..." The new medium offers the exciting possibility of instead writing "The reader who is not familiar with x, y, z, ... should first follow the links l, m, n, ..." This is of course much less time-consuming and can thus be used with virtually no effort to make a paper suitable for almost everyone. Although I doubt that today too many useful electronic links exist which may serve this purpose, maybe sometime in the future there will be.

One suitable supplement to any ETAI paper is readily available already today, namely, the electronic public discussion. I support Rob's suggestion that everyone who downloads an accepted ETAI paper should be strongly encouraged to also print out and append the discussion page. My feeling is that this truly new feature is among the greatest advantages of the novel publication style.

From: Pat Hayes on 3.5.1998

A comment on Sergio's reply to Jixin:

An interval from the real-line is an ordered set of real numbers limited by its end-points, which are not necessarily included in the set.

It seems from this that the set of intervals is supposed to include open, half-open and closed intervals; is that right? (Or do you mean to say that there may be some doubt about whether a particular interval does or does not include its endpoints? If the latter, this is not the usual notion of 'interval' as used in real analysis, and you need to explain further.)

Suppose  S  consists of intervals from the real line. Assume  <s1,t1> in A  and  <s2,t2> in B , intervals in  S . We say that  <s1,t1> < <s2,t2>  iff  t1 < s2 . The strict order relation   <   is an abbreviation for   < logical-and =/  .

It follows then that for intervals,   <   implies   <   except for pointlike intervals (single-point closed intervals) since if  t1 < s2 , the intervals  <s1,t1>  and  <s2,t2>  cannot be equal unless  s1 = t1 = s2 = t2 .

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> .

Consider the closed intervals   [p, q]   and   [q, r]   with  p < q < r . These satisfy   <   and hence satisfy   <  , but there is no interval between them. Hence, your axiom is false for intervals on the real line.

Pat Hayes

From: Jixin Ma on 3.5.1998

To Sergio, who wrote:

The (temporal) domain  S , as I meant, may consist either of time-points xor of time-intervals (exclusive "or"). An interval from the real-line is an ordered set of real numbers limited by its end-points, which are not necessarily included in the set. Suppose  S  consists of intervals from the real line. Assume  <s1,t1> in A  and  <s2,t2> in B , intervals in  S . We say that  <s1,t1> < <s2,t2>  iff  t1 < s2 . The strict order relation   <   is an abbreviation for   < logical-and =/  . 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 reply in advance to your next question: "Why did you write   <   instead of   <   ?". The reply is that   <   means "less or equal", that is  xi  may not be equal to  t1  or  s2 , but it can do so. Note that since  xi  belongs to  S , then  xi  is an interval. This is also meant as a reply to your question about the dividing instant problem. I could not penetrate the rest of your message.

First of all, what you wrote in the above didn't solve the Dividing Instant Problem at all!

Anyway, you have claimed that "The (temporal) domain S may consist either of time-points or (exclusive-or) of time-intervals", and "an interval from the real-line is an ordered set of real numbers limited by its end-points, which are not necessarily included in the set." In this case, can your intervals be "pointlike"? That is, for an interval  <s,t> , is  s  allowed to be equal to  t ? In other words, can a set representing an interval be a singleton? As I suggested in my former response, the anwser has to be yes (see below). That is, if your domain  S  contains non-pointlike intervals, then, to satisfy the so-called completeness property, the domain  S  must contains singletons (or namely points!) as well. Therefore, all my former questions for you still apply.

I have shown in my former message that if your domain  S  contains intervals, it must contain points as well. However, you claimed that  S  does not consist both of time-points and intervals since you specially claimed that your "or" is exclusive-or). I would like to use your notation to show this again.

In fact, you define the (partial) relation "  <  " as follows:  <s1,t1> < <s2,t2>  iff  t1 < s2 . Consider the case that interval  <s1,t1>  in  A  and interval  <s2,t2>  in  B , satisfying  <s1,t1> < <s2,t2> , and  t1 = s2  (this is a valid case according to your definition). To fulfil the completeness property, there exists a  xi  in domain  S  such that  <s1,t1> < xi < <s2,t2> . Let  xi = <s,t> . Again, by the definition of "  <  " between intervals, we have  t1 < s  and  t < s2 . However, remember  t1 = s2 , we infer that it is impossible for  s < t . Therefore, we reach that  s = t . That is  xi  must be a point (pointlike)!

By the way, it seems that your description of the axiom of completeness is not a first-order one.

Jixin

From: Sergio Brandano on 3.5.1998

In ENRAC 24.4.1998 I made a typing mistake. I wrote: " xi  may not be equal to  t1  or  s2 , but it can do so", while it should obviously be: "assuming  xi =  <xi₁, xi₂>  , then  xi₁  may not be equal to  t1  and  xi₂  may not be equal to  s2 , but they can do so".

In reply to Jixin Ma (ENRAC 23.4 and 24.4 1998) -- completion:

So, you think intervals are not needed? Anyway, our arguments...

I am actually skeptic about the need of a temporal domain which includes time-intervals. There are many convincing arguments that a temporal domain consisting of time-points is good enough in many different situations (Newtonian mechanics and Thermodynamics, for instance, as well as Sandewall's underlying semantics for  K-IA ), and I see no reason why I should pursue a different path.

... about the convenience of using intervals are based on the belief of the need of them.

This is why I originally asked for some convincing argument(s) for the plausibility of this approach. According to the standard scientific methodology, in fact, we shall build on top of already existent solutions, and be consistent. Just to make an example, suppose one refuses a classical notion (continuity?), and encounters the problems that this notion was used to solve (the dividing instant?); it is surely not consistent to justify the need for a novel approach via the claim that the problems he encountered can not be solved by the notion he just refused. The notion of semi-continuity, for instance, has dignity, and its plausibility is far to be based on the belief that continuity is not needed... The case of time-intervals is clearly safer; one may simply give a preliminary example and show some objective advantages when using time-intervals instead of time-points.

Premise: It is evident that if you assume the axiom of completeness, the domain  S  can just be continuous, while if you do not assume the axiom of completeness then  S  is necessarily discrete.

Wrong! Even if you do not asssume the axiom of completeness, it is still not nessarily discrete.

Yes, I agree. I realize I wrote that sentence having in mind the basic time structure on my paper. The question holds properly if you do not assume any axiom of density other than the one I stated.

Concerning the dividing instant problem, which seems to summarize what is left from your objections, please read below.

In reply to Pat Hayes (ENRAC 24.4.1998):

As posted in my original message, I have not yet seen any explanation why an alternative notion of continuous structure is needed at all?

Probably, in order to prevent any misunderstanding, I should have included an additional sentence like "... is needed at all, within the search of those non-monotonic logics which purpose is to formalize common sense reasoning when reasoning about actions and change", but I thought it was evident, as the title of this Newsletter reminds.

In particular, in the same message, I asked to give at least one convincing argument on the need of a notion which is an alternative to the classical one, along the lines: "the problem P of temporal reasoning about actions and change can not be solved adopting the axiom of completeness", or "the axiom of completeness is too strong an assumption for our purposes; axiom A is better suited, because..." ( >>>>star )

You and Jixin Ma proposed the "dividing instant problem", apropos of the problem of switching on the light, and argued the axiom of completeness inadequate for solving that problem. The formulation I gave in ENRAC 24.4.1998, with today's minor adjustment, gives the evidence on how the axiom of completeness is, instead, safe with respect to the dividing instant problem. You and Jixin based your argument on the fact that I do not allow the domain  S  to hold points "and" intervals, so that if  S  admits just intervals then the dividing point  p  can not exist. I refuted that argument by simply observing an interval from the real line may have equal end-points.

You also gave other examples, but you did not explain how they relate to the world of "Reasoning about Actions and Change". In particular, and I somehow repeat myself, it is not evident that one needs a temporal domain with non-homogeneous continuity (let me say it is even less evident the need of the imaginary number  i  in our temporal structure). Does there exist at least one representative problem of reasoning about actions and change that can not be solved adopting the axiom of completeness, so that to justify a temporal domain with non-homogeneous continuity? (and I repeated ( >>>>star ))

You also gave an informal argument on the plausibility of a temporal structure which formalizes the perceived smooth flux and perceived fast flux of time (ENRAC 21.4.1998). I refuted that plausibility with my contribution to ENRAC 23.4.1998.

(Is it really ``free of context'' to you ?)

Best Regards
Sergio

From: Sergio Brandano on 4.5.1998

In reply to Pat Hayes (ENRAC 3.5.1998)

An interval from the real-line is an ordered set of real numbers limited by its end-points, which are not necessarily included in the set.

It seems from this that the set of intervals is supposed to include open, half-open and closed intervals; is that right? (Or do you mean to say that there may be some doubt about whether a particular interval does or does not include its endpoints? If the latter, this is not the usual notion of 'interval' as used in real analysis, and you need to explain further.)

The former case is the one I meant.

You posed a good question, which may call into the present debate the possible relations between epistemological and ontological assumptions, at least within the "Features and Fluents" framework.

If we assume the epistemological assumption  K  (accurate and complete information about actions), then occurrences of actions are also supposed to give no doubtful information whether the scheduled time interval where they are supposed to be performed does or does not include its endpoints, so that the latter case from the quoted text must not hold. Probably the case may hold within "Mo".

Suppose  S  consists of intervals from the real line. Assume  <s1,t1> in A  and  <s2,t2> in B , intervals in  S . We say that  <s1,t1> < <s2,t2>  iff  t1 < s2 . The strict order relation

<   is an abbreviation for   < logical-and =/  . It follows then that for intervals,   <   implies   <   except for pointlike intervals (single-point closed intervals) since if  t1 < s2 , the intervals  <s1,t1>  and  <s2,t2>  cannot be equal unless  s1 = t1 = s2 = t2 .

  <   does not necessarily imply   <  , as in the case of  <2,5> < <5,9> , which is a valid case with respect to   <  .

You are right concerning the case whether  <s1,t1>  may be equal to  <s2,t2> , but this does not really affects the axiom of completeness and, into the slightest question, it may be easily fixed.

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> .

Consider the closed intervals   [p, q]   and   [q, r]   with  p < q < r . These satisfy   <   and hence satisfy   <  , but there is no interval between them. Hence, your axiom is false for intervals on the real line.

The closed intervals   [p, q]   and   [q, r]  , with  p < q < r , do not fulfill the relation  <p,q> < <q,r> , hence they do not make a valid counterexample.

Best regards
Sergio

From: Jixin Ma on 7.5.1998

In ENRAC 3.5 (980521), Sergio wrote:

I am actually skeptic about the need of a temporal domain which includes time-intervals. There are many convincing arguments that a temporal domain consisting of time-points is good enough in many different situations (Newtonian mechanics and Thermodynamics, for instance, as well as Sandewall's underlying semantics for  K-IA ), and I see no reason why I should pursue a different path.

You said here "a temporal domain consisting of time-points is good enough in many different situations". Is this ("manyu") a convincing argument for general treatments? Anyway, the fact that "you see no reason why you should pursue a different path" does not mean others don't see/have the reason (see below).

... about the convenience of using intervals are based on the belief of the need of them.

... According to the standard scientific methodology, in fact, we shall build on top of already existent solutions, and be consistent. Just to make an example, suppose one refuses a classical notion (continuity?), and encounters the problems that this notion was used to solve (the dividing instant?); it is surely not consistent to justify the need for a novel approach via the claim that the problems he encountered can not be solved by the notion he just refused.

Have you applied the above arguments to that one proposed by youself? Sorry, I am here again using your question to ask you.

Anyway, 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?

All right, let's just have a look at the example of throwing a ball up into the air. As I showed in ENRAC 1.4 (98033) (one may disagree with this), the motion of the ball can be modelled by a quantity space of three elements: going-up, stationary, and going-down. Firstly, or at least, we can see here the convenience of using intervals. In fact, we can conveniently associate the property that "the ball changes its position" with some time-intervals. Secondly, let's see if we indeed need time-intervals. Without the notion of time-intervals (neither primitive nor derived from time-points), can you just associate such a property with time-points? Yes, we may associate it with a pair of points. However, this doesn't mean that the property holds at these points. What it really means is that the property holds for the time periods denoted by the pair of points. Aren't these time periods in fact time intervals?

It is important to note, up to now in the above, I just talked about the need of the notion of intervals. As for how to characterise intervals (e.g., are intervals taken as primitvie or derived structures from time-points?) is another important issue, and this issue, again, has been addressed in the literature for a long time.

The Point Is: while we were/are discussing/arguing about some broader issues on temporal ontology, you just jumped in and asked "why an alternative notion of continuous structure is needed at all?" First of all, the "continuity" (or more truly, density) is not the main issue we are talking about. The fundamental question is if we need to address and how to addess time intervals. Based on such a discussion, in the case that intervals are taken as temporal primitive, then, we are talking about how to characterise some corresponding issues including dense/discrete structures. But your questions and arguments/replies do not seem to follow this. As stated in the former replies from both Pat and myself, first of all, the dense structure does not have to be characterised in terms of the only form of the so-called "axiom of completeness". Also, in the case where time-intervals are involved (even they are still point-based, let alone in the case they are taken as primitive), such an axiom doesn't simply apply. In fact, I have shown this twice with different notations in this discussion. I will point out more problems in detail below in my response to your reply to Pat.

Concerning the dividing instant problem, which seems to summarize what is left from your objections, please read below.

As I already stated, your approach does not solve the DIP at all. In fact, it seems that you don't realise the DIP in the way as we are talking about (see below).

In reply to Pat Hayes (ENRAC 24.4.1998):

As posted in my original message, I have not yet seen any explanation why an alternative notion of continuous structure is needed at all?

Still not yet?

You and Jixin Ma proposed the "dividing instant problem", apropos of the problem of switching on the light, and argued the axiom of completeness inadequate for solving that problem. The formulation I gave in ENRAC 24.4.1998, with today's minor adjustment, gives the evidence on how the axiom of completeness is, instead, safe with respect to the dividing instant problem. You and Jixin based your argument on the fact that I do not allow the domain  S  to hold points "and" intervals, so that if  S  admits just intervals then the dividing point  p  can not exist. I refuted that argument by simply observing an interval from the real line may have equal end-points.

You claimed already that your domain  S  contains points or (exclusive-or) intervals? To fulfill the axiom of completeness, you must allow your intervals to be possibly some singletons (i.e., a set of single point). In other words, if your  S  contains intervals, it should also contain singletons (points). The real problem is that even if you allow your intervals to be singletons, the Dividing Instant Problem is still there, and in fact more obviously. Do you agree with this?

The closed intervals   [p, q]   and   [q, r]  , with  p < q < r , do not fulfill the relation  <p,q> < <q,r> , hence they do not make a valid counterexample.

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?)

It follows that you do need alternation, doesn't it? (Note that this is just for the case 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 to 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 use   <   in the hypothesis; otherwise, your axiom cannot 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?).

Jixin

From: Sergio Brandano on 8.5.1998

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

From: Jixin Ma on 12.5.1998

Reply to Sergio Brandano (ENRAC 8.5.1998)

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:

When you presented the (classical) axiom of completeness (ENRAC 23.4.1998), you used   <   in the hypothesis (You are now still using it, see below). But for the case where elements in domain S are just intervals, you used   <   instead (otherwise, Pat's example is valid, see below).

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.

Again, if you re-claim that the axiom of completeness imposes   <  , then Pat's example is valid (see below).

...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 :   [s1, t1]  <  [t1, t2]     [s1, t1]  <  (t1, t2]     [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 $lt$, as you recommend, then all cases trivially fail. Pat's example: trivially fails when using   <  , trivially succeeds ( xi =  [q, q]  ) when using   <  .

This is exactly what I wanted to show and have shown a few times now. That is, in the case there your domain S contains intervals, to fulfill the axiom of completeness, S has to contains singletons (single points) as well, not as you specially claimed that S contains points or (exclusive-or) intervals. My observation that Pat's example would be valid is under your assumption that the domain S refuses to take both intervals and singletons (points). I think when Pat gave the example, he also followed this assumption of yours. (Actually, Pat did specially claim that "unless you allow intervals consisting of a single point" when he gave the example in ENRAC 24.4.1998).

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.

This is exactly what I have suggested in my message to you (see above).

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.

The DIP was proposed much earlier in the literature. What you have done, is just a re-Writing of a model where the DIP arises. Could you please check carefully what exactly is the problem and if it can be solved by your formulation?

Jixin

From: Pat Hayes on 17.5.1998

[S.B.]

Suppose  S  consists of intervals from the real line. Assume  <s1,t1> in A  and  <s2,t2> in B , intervals in  S . We say that  <s1,t1> < <s2,t2>  iff  t1 < s2 . The strict order relation   <   is an abbreviation for   <  ^  =/  .

[P.H.]

It follows then that for intervals,   <   implies   <   except for pointlike intervals (single-point closed intervals) since if  t1 < s2 , the intervals  <s1,t1>  and  <s2,t2>  cannot be equal unless  s1 = t1 = s2 = t2 .

[S.B.]

<   does not necessarily imply   <  , as in the case of  <2,5> < <5,9> , which is a valid case with respect to   <  .

Clearly,  <2,5>  is not equal to  <5,9> , ie  <2,5> =/ <5,9> . That is, both   <   and   =/   hold between those intervals. According to Sergio's definition (in italics above) it follows that the relation   <   must hold between them. In general, if  p  is not equal to  q , then the intervals  <p,q>  and  <q,r>  cannot be equal, so must be   =/  , but are also   <  , and therefore must be   <  . The rest of his message in ENRAC 4.5 (98042) makes the same error, and the subsequent confusion has been noted by Jixin in the later discussion.

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. Yes, of course: that is not at issue. We are not claiming to have found some basic flaw in conventional real analysis. 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. Of course we could just decide that periods of off-ness, say, shall be left-open-right-closed, or some other convention: but this is arbitrary, ad-hoc and theoretically unsatisfactory, since the intuition we would like to capture is that the question (of the light being on or off at b) simply doesnt arise: it just goes on then, that's all. That is the intuition which Allens interval calculus, where intervals can simply meet, is intended to capture. The fact that this calculus violates Sergios pet axiom doesnt seem to be a very important matter for further discussion.

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.

Pat Hayes