Artificial Intelligence Systems Based on NTA

Introduction

Modern computer technologies often need methods of logical analysis of systems. These methods play an important role in artificial intelligence (AI) as well. In the development of software for AI systems, big costs in time and resources arise due to the fact that logical methods of modeling and analysis are based on the declarative approach hardly compatible with the procedural approach, which is natural for programming. That is why AI languages built within the declarative approach become more sophisticated because of their supplementing with procedural means.

Algebraic approach to logical analysis of systems is often used in modern programming. In practice, this is revealing in usage techniques of Boolean algebra and algebra of sets instead of axiomatic formalization of propositional calculus. However, in cases where the capabilities of propositional calculus are not sufficient, and it is necessary to use predicate calculus, theoretical foundations for implementing the algebraic approach occur to be absent.

In theoretical studies and books on AI, the algebraic approach is not very popular. Traditionally, the declarative approach is considered more corresponding to analysis of reasoning, and modern intelligent systems are built on its basis. Difficulties and problems typical for such tasks are considered inevitable during computer implementation of AI systems. In our opinion, the formal approach itself yields many of these problems. Here are some of them.

• 1.

  The variety of formal languages gave rise to the diversity of logics, many of which are difficult to interpret or not interpretable at all, i.e., they are essentially meaningless. Along with appearance of this variety of logics, new obstacles are encountered in choosing the “proper” logic. Thus, logical correctness criteria for systems and reasoning became blurred.

• 2.

  Fundamental differences in theoretical approaches to building of databases and knowledge bases in intelligence systems resulted in poor compatibility of DBs and KBs within a single information system.

• 3.

  In fields of management, information processing and programming, professionals perceive data presentation in the form of algebraic structures naturally, but modern methods of logical analysis of systems are currently taught mainly in terms of the formal approach whose complexity and detachment from usual algebraic structures does not allow many students truly appreciate all the features of logical analysis and its applications. Development of the algebraic approach as an instrument of logical analysis would make it possible to avoid many of these difficulties in teaching.

This chapter presents features and capabilities of the NTA-based algebraic approach to modeling of some AI structures and techniques.

Discrete Automata

With the help of discrete automata, it is possible to represent a dynamic system that changes its state in each step (cycle). This state affects the system response to input signals or control impacts. A dynamic system can be represented by a finite automaton, if the state of the system in each cycle is uniquely determined by: a) the state of the system in the previous cycle, and b) the input signal in the previous or the current cycle.

There are two options to describe automata (Brauer, 1984): 1) by using two tables: the transition and output ones, and 2) via transition graphs. This section provides a description of a new version of the automaton descriptions with the help of NTA structures. Let us consider two definitions of automata (Brauer, 1984).

• Definition 1: (Finite) Mealy automaton (Mealy machine) is a 5-tuple A = (Z, X, Y, f, g). Here, Z, X and Y are finite, non-empty set of symbols: the set of states, inputs and outputs respectively. f: Z × X → Z and g: Z × X → Y are mappings representing the state-transition function and the output function respectively; g is a surjection.

• Definition 2: (Finite) Moore automaton (Moore machine) is a 5-tuple A = (Z, X, Y, f, h). Here Z, X, Y and f are the same as in Definition 1, and h is a surjective mapping from Z to Y called the output function.