A Metalogic Programming Approach to Reasoning about Time in Knowledge Bases

Suryanarayana M. Sripada

Abstract

Reasoning about time in knowledge bases (KBs) often requires distinguishing between when an event occurred in reality and when the system recorded that event. This paper presents a metalogic programming framework that separates "historical time" from "belief time." By transforming formal temporal axioms into executable logic clauses, the approach enables efficient reasoning about retrospective updates and nested agent beliefs.

Introduction

In standard knowledge representation, time is frequently treated as a single linear dimension. However, real-world applications—particularly in legal and multi-agent domains—demand a more sophisticated treatment. For instance, a retrospective law might change the tax status of an individual for a period that has already passed. To handle such cases, a KB must track two distinct temporal axes: historical time (when an event happened) and belief time (when the KB became aware of it).

Problem Statement: The Need for Dual Time Dimensions

Existing temporal logics often struggle with the computational complexity of interacting time dimensions. A system needs to answer queries like: "Based on what we knew on October 20th, was John a taxpayer in June?" versus "Based on what we know now, was John a taxpayer in June?" Traditional approaches often require specialized theorem provers that are difficult to integrate into standard programming environments.

Methodology: Metalogic Programming

The author proposes a Metalogic Programming approach to bridge abstract temporal theory with practical implementation.

Two-Tiered Representation

The system utilizes meta-predicates, such as holds(rule, period), to denote that a specific rule or fact is valid during a given interval. This allows the system to reason about the validity of its own knowledge over time.

Interval-Based Axiomatization

Rather than checking discrete time points, the framework defines a formal theory (Axioms S1–S8) based on intervals. This significantly improves computational efficiency by reducing the search space to start and end ranges.

Executable Logic Clauses

Using fold/unfold transformations, the abstract axioms are converted into eleven executable logic clauses (P1–P11). This "meta-interpreter" can be implemented in standard Prolog, making it highly portable.

The Running Example

To demonstrate the framework, the paper uses a synthetic benchmark involving a taxpayer, John, and changing regulations.

Timeline of events and rules in the taxpayer running example.

As shown in Figure 1, various events (e.g., ic(john, 6000)) and rules (e.g., tp(X) <- ...) are introduced at different points in time, some with retrospective effects.

Formal Representation of Beliefs

The core of the system's reasoning lies in its ability to nest beliefs and time intervals.

Nested 'holds' predicates representing historical and belief time intervals.

Figure 3 illustrates how the system encodes these complex relationships. Each holds predicate contains a nested holds or a fact, paired with two intervals: the historical interval (when it was true) and the belief interval (when the system held that belief).

Key Results and Implementation

The system was successfully implemented in CProlog on a VAX 11/750. The author proved that the derived logic program (P1–P11) is mathematically equivalent to the formal specifications. The implementation correctly handled complex queries involving retrospective policy changes, such as determining a student's taxpayer status across different KB states.

Limitations and Future Work

While powerful, the metalogic approach introduces computational overhead. The author suggests partial evaluation as a potential optimization. Additionally, while the framework supports nested beliefs, further work is needed to fully formalize the interactions between different agents' beliefs and the "frame problem" of persistence.

Summary updated

BibTeX
@inproceedings{sripada1993metalogic,
  author = {Suryanarayana M. Sripada},
  title = {{A Metalogic Programming Approach to Reasoning about Time in Knowledge Bases}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1993},
}
Figure