Project 1633

Theory of automata and applications

Leader: dr Goran Kilibarda


Subject of research

The project envisages the continuation of long-term research of the behavior of automata in geometric spaces and enumeration of certain classes of automata, and in this connection, of certain classes of graphs, digraphs and Boolean functions in respect of transformation groups. Another direction of investigation is the use of automata as a data base model which possesses the optimum characteristics both in terms of the volume of information and its accessibility, as well as the application of automata in solving problems of artificial intelligence.

Description of the work

The content of research is supposed to include the study of the behaviour of automata as their basic characteristic. In this connection there will be considered the behaviour of automata in abstract surroundings such as free input semi-groups with the interpretation of geometrical character. Examples of such interpretation are plain and three-dimensional labyrinths, textual graphics, pictures and so on. The problem of automation of the process of investigation of characteristics of large labyrinths and informationally-capacious graphics will also be considered. The investigation of the problem of automaton analysis and the problem of traversing a labyrinth will be continued, with the view of discovering their characteristics and searching definite objects in them. The problem of the synthesis of automata in labyrinths and the problem of modelling automata behaviour in some classes of labyrinths will be considered. These investigations will be extended to include the study of graphics and picture properties, above all, in terms of pattern recognition problem. The problem of enumeration of certain classes of automata, and in connection with this - of certain classes of graphs, digraphs and Boolean functions in respect of transformation groups, as well as problems of their set realizations will also be considered.

Another direction of research, with a more expressed applied aspect is the development of a new approach to solving the problem of data representation, which in terms of the theory of data bases is referred to as information-graph representation. In general, this model is a graph with input and output poles, in the points of which there are automata. At the graph input requests are handed in and transported along the graph's arcs to automata-machines, which by working iteratively find the necessary answer and hand it at the graph output. The problem searching and storing information in such data bases is considered here and the respective optimum algorithms are elaborated. In addition the problem of using automata and discrete structures for solving the task of machine reasoning and machine text processing for the Serbian language will also be considered.

Originality of research

The originality of the research consists in obtaining new theorems and algorithms to solve the problems of the research. The advantage of the project lies in its applied character.

Research Goal

The aim of the research is to improve the existing and to obtain new applied results with the help of which the following problems can be solved: the behaviour of automata in labyrinths (analysis, synthesis and modelling); automation of the process of investigating properties of informationally-capacious graphics as a problem of pattern recognition, enumeration of some classes of automata and in connection with this of some classes of discrete structures, the search and storage information.

State of the Art in Scientific Field

World-wide Situation

The theory of automata was established as a separate branch of mathematics in the middle of the twentieth century. In the past twenty years the attention of scientists has been focused on such problems in the field of discrete mathematics, and particularly, the theory of automata, as automata analysis of pictures, graphs, formal languages and other discrete systems. A large number of scientific articles dealing with automata behaviour in labyrinths has been published, more than 120. The first paper concerning this problem was published in 1951 by Cl.E.Shannon. A considerable contribution to formulating and solving the outlined problems was made by K.Dopp, H.Muler, L.Budach, H.Antelmann, A.S.Podkolzin, M.Blum, V.B.Kudryavtsev, and others.

Domestic Situation

Scientific research in this field in our country is implemented first and foremost in Belgrade, Novi Sad and Niš. The problems that have been formulated and that are going to be considered within the framework of the project have already been investigated by a group of scientists in Belgrade at the Department of Mathematics of the Faculty of Technology and Metallurgy, headed by professor Šćepan Ušćumlić. The research that has so far been implemented resulted in the publication of a considerable number of works in world famous scientific magazines and journals. In addition, a monograph was published in cooperation with a group of scientists from Moscow. The participants of the research team of this project are members of International scientific committee of the journal "Intelligent systems" which is published by Moscow State University named after M.V.Lomonosov, Academy of technological sciences of Russia and Russian academy of natural science.

Planned Project Results

The results of the research will expand fundamental knowledge in the field of discrete mathematics in general and, in particular, in the field of the theory of automata, the theory of pattern recognition, combinatorial analysis, the theory of information-graph data base, etc. The expected results may find application in solving problems of artificial intelligence and engineering problems concerning the construction of machine-robots, intended for implementing jobs that can hardly or can not be performed by man, such as detecting and extinguishing fire, or discovering contaminated areas and their decontamination, recognition of unclear texts or objects.

The results of the suggested project will contribute to the development of robotization technology of certain technological operations in factories for the production of various goods and in industrial enterprises, plants, and service industry. Essentially we deal with a robot moving in a labyrinth and searching an object, that is, determining the properties of environment and implementing certain operations aimed at changing the environment. The results will be especially applied in solving the problems of robotization of human intellectual activity and the problem of robotization of information space.