Information Technology Reference

In-Depth Information

Finite Algebras and AI: From Matrix Semantics

to Stochastic Local Search

Zbigniew Stachniak

Department of Computer Science, York University

Toronto, Canada

1

Introduction

Universal algebra has underpinned the modern research in formal logic since Gar-

rett Birkoff's pioneering work in the 1930's and 1940's. Since the early 1970's,

the entanglement of logic and algebra has been successfully exploited in many ar-

eas of computer science from the theory of computation to Artificial Intelligence

(AI).

The scientific outcome of the interplay between logic and universal algebra

in computer science is rich and vast (cf. [2]). In this presentation I shall discuss

some applications of universal algebra in AI with an emphasis on Knowledge

Representation and Reasoning (KRR).

A brief survey, such as this, of possible ways in which the universal algebra

theory could be employed in research on KRR systems, has to be necessarily in-

complete. It is primarily for this reason that I shall concentrate almost exclusively

on propositional KRR systems. But there are other reasons too. The outburst of

research activities on stochastic local search for propositional satisfiability that

followed the seminal paper
A New Method for Solving Hard Satisfiability Prob-

lems
by Selman, Levesque, and Mitchel (cf. [11]), provides some evidence that

propositional techniques could be surprisingly effective in finding solutions to

'realistic' instances of hard problems.

2

Propositional KRR Systems

One of the main objectives of Knowledge Representation is the development

of adequate and, preferably, tractable formal representational frameworks for

modeling intelligent behaviors of AI agents.

In symbolic approach to knowledge representation, a KRR system consists of

at least a formal knowledge representational language

L

and of an inference op-

eration

on

L

. Such a system may involve additional operations and relations

besides

(such as plan generation and evaluation, belief revision, or diagno-

sis); for some domains, some of these additional operations can be defined or

implemented in terms of 'basic' logical operations: logical inference, consistency

verification, and satisfiability checking. Representing reasoning tasks as instances

of logical inference, consistency, and satisfiability problems is discussed below.

Search WWH ::

Custom Search