Reconstruction of automata by fragments of behaviour

V. B. Kudryavtsev ; I. S. Grunskii ; V. A. Kozlovskii

Diskretnaya Matematika, Tome 21 (2009) no. 2, pp. 3-42

Résumé

This survey contains results concerning behavioural and abstract theory of finite automata. Finite automata and related constructions are cornerstone concepts of discrete mathematics and mathematical cybernetics. Automata theory finds multiple applications in programming, technical cybernetics, the theory of dynamic systems, etc. Classical problems of this theory are the direct problems: analysis of processes of information transformation carried out by automata and properties of automata, and the inverse problems: synthesis of automata of prescribed properties and identification (restoring, recognition, deciphering, control and diagnosis) of an automaton by means of experiments with it. The fundamental notion which underlies the study of the above problems is the notion of a fragment which is a natural extension of a great number of known fragments of particular forms possessing their characteristic properties. Another key notion is the notion of an identifier of unobservable components of functioning of an automaton, that is, of a fragment which allows for unambiguous determination of these components. The subject matter reflected in this survey is being developed intensively, both in the direction of solving mathematical problems and in applied studies related to synthesis, testing and verification of complex software and hardware systems. This survey contains a series of final results, but they can be treated as a regular step in studying problems of analysis and synthesis of automata by their behaviour, which are continuously filled with new content and require additional resources to solve them.