Multi-Dimensional Logic Programming:

Theoretical Foundations

Mehmet A. Orgun Weichang Du

Department of Computing Department of Mathematics & Computer Science Macquarie University University of New Brunswick
Sydney, NSW 2109, Australia Saint John, N.B. E2L 4L5, Canada Tel: +61 2 850-9570 Tel: +1 506 648-5725
Fax: +61 2 850-9551 Fax: +1 506 648-5528
E-mail: [email protected] E-mail: [email protected]

ABSTRACT

This paper introduces an extension of logic programming based on multi-dimensional logics, called MLP. In a multi-dimensional logic the values of elements vary depending on more than one dimension, such as time and space. The resulting logic programming language is suitable for modelling objects which involve implicit and/or explicit temporal and spatial dependencies. The execution of programs of the language is based on a resolution-type proof procedure called MSLD-resolution (for Multi-dimensional SLD-resolution). MSLD- resolution is based on the axioms and rules of inference of the underlying multi-dimensional logic. The paper also establishes the declarative semantics of multi-dimensional logic programs, based on an extension of Herbrand models. In particular, it is shown that MLP programs satisfy the minimum model semantics. A novel multidimensional interface to MLP is also outlined; it can be used as a powerful development tool with the advantage non-determinism inherent in logic programming.

Keywords: Logic Programming, Multi-Dimensional Logic, Proof Procedures, Declarative Semantics, Spreadsheets, SLD-resolution.

1 Introduction

Extensions of classical logics such as temporal and modal logic have been successfully used as a formalism in many areas, including program specification and verification [22], temporal reasoning [33], and knowledge representation [34]. In temporal and modal logics, the meanings of formulas vary depending on an implicit context, and elements from different contexts can be combined through the use of contextual (temporal and modal) operators, not by explicit references to context (time, space or otherwise). Therefore these logics can model dynamic properties of certain problems in a natural and problem-oriented way.

More recently, several researchers have suggested that temporal and modal logics can be directly used as a programming language in applications involving the notion of dynamic change. There are a number of temporal and modal logic programming languages: Tempura [25] and Tokio [4] are based on interval logic, which is a form of temporal logic;