Formal systems in Artificial Intelligence: an illustration using semigroup, automata and language theory

摘要

As the field of Artificial Intelligence (AI) matures, methods relying less on ad hoc procedures and more on well defined operations in the context of formal structures are emerging. Evidence for this can be found, for example, in the increasingly sophisticated approaches to inexact reasoning in knowledge-based systems and in the mathematical framework developed for semantic net representation. This tutorial and brief survey presents a facet of formal language theory which provides a formalism for naturally representing and operating on strings of symbols and which also admits obvious means of handling issues such as specialization and generalization, pervasive in AI. The broad subject area covered is part of semigroup theory which has a natural relationship to both finite state automata theory and regular languages. This paper aims to introduce some of the underlying theory relevant to representation issues in AI in this context.