Finite Algebras and AI: From Matrix Semantics to Stochastic Local Search - Artificial Intelligence and Symbolic Computation - page 8

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.