March 29, 2013

The Tetherless World Constellation is proud to announce the successful completion of Ankesh Khandelwal's Thesis Defense. Ankesh is the fifth student to complete their Ph.D. within the Tetherless World Constellation.

Title: Furthering the Continuous-Change Event Calculus: Providing for Efficient Description of Additive Effects and an Automated Reasoner

Advisors: Peter Fox, James Hendler

Abstract: Semantic Web refers to a Web of interconnected data enriched with semantics. It subscribes to logic-based representations of knowledge through W3C standards such as the Resource Description Framework and the Web Ontology Language for encoding clear semantics. To date, knowledge representation however has been confined to descriptions of artifacts or data thus far. We began the research reported here in pursuit of the inclusion of knowledge about physical processes and natural laws, into the Semantic Web. Such knowledge could then be combined with experimental data, for example, in a largely automated fashion, for new inferences. In this pursuit we explored the extensive research in the field of reasoning about actions and changes, and deduced that the (circumscriptive) Event Calculus is the most expressive logic-based formalism available for logic-based description of continuous-changes.

In this thesis we extend the Event Calculus formalism with new predicates for descriptions of discrete and continuous additive effects whose semantics are given via aggregate formulas in first-order logic. To the best of our knowledge this is the first application of aggregate formulas in first-order logic, even though aggregates have been in use in other logics such as answer-set programming. The frame problem is one of representing the effects of actions without explicitly representing all their non-effects. Nonmonotonic reasoning via circumscription is used in the Event Calculus as a solution to the frame problem. We show, however, that circumscription which was defined for first-order logic without aggregates is inadequate for modeling the frame problem in the extended Event Calculus if used as it is for formulas with aggregates, as it selects anomalous models.

We extend the circumscription transformation to first-order logic with aggregates, named the CIRCA transformation. CIRCA transformation is a generic transformation that addresses a general problem of identifying and not selecting unintended models, classified formally as weak models, that circumscription normally selects in the presence of aggregates. We deploy CIRCA transformation for resolving the frame problem in the extended Event Calculus.

Finally, we devise a method for constructing models for given, numerical, and finite Event Calculus domain descriptions, given an initial state and narratives of external actions. An Event Calculus system evolves through altenating phases of continuous changes and instantaneous discontinuous changes. The devised method involves separation of logic and equations reasoning through syntactic derivations of new axioms from the given domain descriptions, such that discontinuous changes, equations for trajectories of continuous changes, and mathematical conditions for next discontinuous changes are determined from logic reasoning while trajectories of continuous changes and the time for next discontinuous change are determined from equations reasoning. With this separation, the state of the art logic reasoners and equation solvers can be combined to implement an automated model builder for the Event Calculus. We have implemented a prototypical reasoner using the DLVHEX logic reasoner and Mathematica libraries.

The results of this thesis may encourage the use of logic formalisms/systems for descriptions of dynamical systems with quantitative descriptions of continuous- changes. Additive effects are very common in concurrent systems, and the extended Event Calculus allows for general, concise and elaboration tolerant descriptions of them, which among other things makes the descriptions amicable to sharing, reuse, and modular development. The prototypical model-builder for the continuous-change Event Calculus formalism broadens its scope beyond theory, positioning it for use in practice. Finally, we hope that these are some crucial steps towards realizing a process modeling language for the Semantic Web alluded to in the beginning.

Title: Furthering the Continuous-Change Event Calculus: Providing for Efficient Description of Additive Effects and an Automated Reasoner

Advisors: Peter Fox, James Hendler

Abstract: Semantic Web refers to a Web of interconnected data enriched with semantics. It subscribes to logic-based representations of knowledge through W3C standards such as the Resource Description Framework and the Web Ontology Language for encoding clear semantics. To date, knowledge representation however has been confined to descriptions of artifacts or data thus far. We began the research reported here in pursuit of the inclusion of knowledge about physical processes and natural laws, into the Semantic Web. Such knowledge could then be combined with experimental data, for example, in a largely automated fashion, for new inferences. In this pursuit we explored the extensive research in the field of reasoning about actions and changes, and deduced that the (circumscriptive) Event Calculus is the most expressive logic-based formalism available for logic-based description of continuous-changes.

In this thesis we extend the Event Calculus formalism with new predicates for descriptions of discrete and continuous additive effects whose semantics are given via aggregate formulas in first-order logic. To the best of our knowledge this is the first application of aggregate formulas in first-order logic, even though aggregates have been in use in other logics such as answer-set programming. The frame problem is one of representing the effects of actions without explicitly representing all their non-effects. Nonmonotonic reasoning via circumscription is used in the Event Calculus as a solution to the frame problem. We show, however, that circumscription which was defined for first-order logic without aggregates is inadequate for modeling the frame problem in the extended Event Calculus if used as it is for formulas with aggregates, as it selects anomalous models.

We extend the circumscription transformation to first-order logic with aggregates, named the CIRCA transformation. CIRCA transformation is a generic transformation that addresses a general problem of identifying and not selecting unintended models, classified formally as weak models, that circumscription normally selects in the presence of aggregates. We deploy CIRCA transformation for resolving the frame problem in the extended Event Calculus.

Finally, we devise a method for constructing models for given, numerical, and finite Event Calculus domain descriptions, given an initial state and narratives of external actions. An Event Calculus system evolves through altenating phases of continuous changes and instantaneous discontinuous changes. The devised method involves separation of logic and equations reasoning through syntactic derivations of new axioms from the given domain descriptions, such that discontinuous changes, equations for trajectories of continuous changes, and mathematical conditions for next discontinuous changes are determined from logic reasoning while trajectories of continuous changes and the time for next discontinuous change are determined from equations reasoning. With this separation, the state of the art logic reasoners and equation solvers can be combined to implement an automated model builder for the Event Calculus. We have implemented a prototypical reasoner using the DLVHEX logic reasoner and Mathematica libraries.

The results of this thesis may encourage the use of logic formalisms/systems for descriptions of dynamical systems with quantitative descriptions of continuous- changes. Additive effects are very common in concurrent systems, and the extended Event Calculus allows for general, concise and elaboration tolerant descriptions of them, which among other things makes the descriptions amicable to sharing, reuse, and modular development. The prototypical model-builder for the continuous-change Event Calculus formalism broadens its scope beyond theory, positioning it for use in practice. Finally, we hope that these are some crucial steps towards realizing a process modeling language for the Semantic Web alluded to in the beginning.