Muchnikova L. Checking experiments for group automata

The thesis is dedicated to investigating structural, metric and algorithmic characteristics of checking experiments in relation to the infinite class of group automata. A new type of experiments with automata is introduced, the so-called labeled checking experiments and their investigation is reduced to investigation of cyclic experiments. A new way of specifying an automaton as a defining pair of its cyclic words sets is offered and the links between defining pairs and algebraic properties of automata are established. The cyclic checking experiments characterization theorems are proved that establish links with defining pairs, special group closures of behavior fragments and fragments of automata informational trees. The attainable length and multiplicity estimations are obtained, the description of length function behavior for such type of estimations is given. The algorithms for constructing optimal cyclic checking experiments and defining pairs are designed and their complexity estimations are discovered; algorithms of automata synthesis based on its defining pair and algorithm of construction of defining relationships of supporting groups of automaton are designed.