Temporal Granularity

From: Jerry Hobbs (hobbs@ai.sri.com)
Date: 08/29/02

  • Next message: Mike Dean: "Hours of Operation ontology"
    Below is a description of a treatment of temporal granularity that 
    emerged from a discussion I had with Rich Fikes and Richard Waldinger.
    It is intended to be an element of a DAML ontology of time.  I would 
    value any feedback anyone feels moved to provide.
    -- Jerry Hobbs
    			 Temporal Granularity
    Useful background reading for this note includes
       Richard Fikes and Qing Zhou, "A Reusable Time Ontology"
       Jerry Hobbs, "Granularity", IJCAI-85, or 
       Jerry Hobbs et al., "A DAML Ontology of Time", 
    Very often in reasoning about the world, we would like to treat an
    event that has extent as instantaneous, and we would like to express
    its time only down to a certain level of granularity.  For example, we
    might want to say that the election occurs on November 5, 2002,
    without specifying the hours, minutes, or seconds.  We might want to
    say that the Thirty Years' War ended in 1648, without specifying the
    month and day.
    For the most part, this can be done simply by being silent about the
    more detailed temporal properties.  Suppose we have the function
    "time-span-of(e)=t" relating events to temporal entities, the relation
    "temporal-description-of(d,t)" relating a temporal entity to a
    description of the clock and calendar intervals it is included in, and
    the functions "second-of(d)", "minute-of(d)", "hour-of(d)",
    "day-of(d)", "month-of(d)", and "year-of(d)".  Suppose we know that an
    event occurs on a specific day, but we don't know the hour, or it is
    inappropriate to specify the hour.  Then we can specify the day-of,
    month-of, and year-of properties, but not the hour-of, minute-of, or
    second-of properties.  For example, for the election e, we can say
       time-span-of(e) = t, temporal-description-of(d,t), day-of(d) = 5,
          month-of(d) = 11, year-of(d) = 2002
    and no more.  We can even remain silent about whether t is an instant 
    or an interval.
    Sometimes it may be necessary to talk explicitly about the granularity
    at which we are viewing the world.  For that we need to become clear
    about what a granularity is, and how it functions in a reasoning
    A granularity G on a set of entities S is defined by an
    indistinguishability relation, or equivalently, a cover of S, i.e. a
    set of sets of elements of S such that every element of S is an
    element of at least one element of the cover.  We will identify the
    granularity G with the cover.  
       (A G,S)[cover(G,S) <--> (A x)[x in S <--> (E s)[s in G & x in s]]]
    Two elements of S are indistinguishable with respect to G if they are
    in the same element of G.
       (A x1,x2,G)[indisting(x1,x2,G) <--> (E s)[s in G & x1 in s & x2 in s]]
    A granularity can be a partition of S, in which case every element of
    G is an equivalence class.  The indistinguishability relation is
    transitive in this case.  A common case of this is where the classes
    are defined by the values of some given function f.
       (A G,S)[G = f-gran(S,f) 
                  <--> [cover(G,S) & (A x1,x2)[indisting(x1,x2,G) 
                                                 <--> f(x1) = f(x2)]]]
    For example, if S is the set of descriptions of instants and f is the
    function "year-of", then G will be a granularity on the time line that
    does not distinguish between two instants within the same calendar
    A granularity can also consist of overlapping sets, in which case the
    indistinguishability relation is not transitive.  A common example of
    this is in domains where there is some distance function d, and any
    two elements that are closer than a given distance a to each other are
    indistinguishable.  We will suppose d takes two entities and a unit u
    as its arguments and returns a real number.
       (A G,S)[G = d-gran(S,a) 
                  <--> [cover(G,S) & (A x1,x2)[indisting(x1,x2,G) 
                                                 <--> d(x1,x2,u) < a]]]
    For example, suppose S is the set of instants, d is duration of the
    interval between the two instants, the unit u is *Minute*, and a is 1.
    Then G will be the granularity on the time line that does not
    distinguish between instants that are less than a minute apart.  Note
    that this is not transitive, because 9:34:10 is indistinguishable from
    9:34:50, which is indistinguishable from 9:35:30, but the first and
    last are more than a minute apart.
    Both of these granularities are uniform over the set, but we can
    imagine wanting variable granularities.  Suppose we are planning a
    robbery.  Before the week preceeding the robbery, we may not care what
    time any events occur.  All times are indistinguishable.  The week
    preceeding the robbery we may care only what day events take place on.
    On the day of the robbery we may care about the hour in which an event
    occurs, and during the robbery itself we may want to time the events
    down to ten-second intervals.  Such a granularity could be defined as
    above; the formula would only be more complex.
    The utility of viewing the world under some granularity is that the
    task at hand becomes easier to reason about, because distinctions that
    are possible in the world at large can be ignored in the task.  One
    way of cashing this out in a theorem-proving framework is to treat the
    relevant indistinguishability relation as equality.  This in effect
    reduces the number of entities in the universe of discourse and makes
    available rapid theorem-proving techniques for equality such as
    We can express this assumption with the axiom
    (1)   (A x1,x2)[indisting(x1,x2,G) --> x1 = x2]
    for the relevant G.  For a temporal ontology, if 0-length intervals
    are instants, this axiom has the effect of collapsing some intervals
    into instants.
    There are several nearly equivalent ways of viewing the addition of
    such an axiom -- as a context shift, as a theory mapping, or an an
    extra antecedent condition.
    Context shift: In some formalisms, contexts are explicitly
    represented.  A context can be viewed as a set of sentences that are
    true in that context.  Adding axiom (1) to that set of sentences
    shifts us to a new context.
    Theory mapping: We can view each granularity as coinciding with a
    theory.  Within each theory, entities that are indistinguishable with
    respect to that granularity are viewed as equal, so that, for example,
    paramodulation can replace equals with equals.  To reason about
    different granularities, there would be a "mediator theory" in which
    all the constant, function and predicate symbols of the granular
    theories are subscripted with their granularities.  So equality in a
    granular theory G would appear as the predicate "=_G" in the mediator
    theory.  In the mediator theory paramodulation is allowed with "true"
    equality, but not with the granular equality relations =_G.  However,
    invariances such as
       if x =_G y, then [p_G(x) implies p_G(y)]
    hold in the mediator theory.
    Extra antecedent condition: Suppose we have a predicate
    "under-granularity" that takes a granularity as its one argument and
    is defined as follows:
       (A g)[under-granularity(g) 
               <--> (A x1,x2)[indisting(x1,x2,g) --> x1 = x2]]
    Then we can remain in the theory of the world at large, rather than
    moving to a subtheory.  If we are using a granularity G, rather than
    proving a theorem P, we prove the theorem
         under-granularity(G) --> P
    If the granularity G is is transitive, and thus partitions S, adding
    axiom (1) should not get us into any trouble.  However, if G is not
    transitive and consists of overlapping sets, such as the episilon
    neighborhood granularity, then contradictions can result.  When we use
    (1) with such a granularity, we are risking contradiction in the hopes
    of efficiency gains.  Such a tradeoff must be judged on a case by case
    basis, depending on the task and on the reasoning engine used.

    This archive was generated by hypermail 2.1.4 : 08/29/02 EDT