Reznykov I. The growth functions of two-state Mealy automata over a two-symbol alphabet and the semigroups, defined by them

Українська версія

Thesis for the degree of Candidate of Sciences (CSc)

State registration number

0402U002821

Applicant for

Specialization

  • 01.01.08 - Математична логіка, теорія алгоритмів і дискретна математика

16-09-2002

Specialized Academic Board

Д 26.001.18

Taras Shevchenko National University of Kyiv

Essay

The dissertation paper is devoted to research of the growth functions of two-state Mealy automata over a two-symbol alphabet and the semigroups of automatic transformations, defined by these automata. The growth functions of the specified Mealy automata are calculated, the semigroups defined by these automata are described in terms of generators and defining relations, their growth functions are computed and the main properties of these automatic transformation semigroups are researched. Let's denote by the symbol S the set of two-state Mealy automata over a two-symbol alphabet. An equivalence relation on S such, that the equivalent automata define isomorphic semigroups of transformations, is introduced. Using this equivalence relation and concept of degenerated automata, it is shown that it is enough to study just 52 non-degenerated pairwise non-equivalent automata instead of all 256 automata from S. The program complex for investigations of the growth functions of Mealy automata and automatic transformation semigroups was developed. Using this complex, initial values and finite differences of the growth functions, and some properties of the transformation semigroups, defined by automata from the set S, were calculated. The results of the computational experiments have allowed putting forward working hypotheses about the growth functions of these automata. The dissertation paper contains description of the structure of this program complex, its main modules, the principles of functioning, and supplementary mathematical constructions. The following results are obtained in the dissertation paper about the growth functions of two-state Mealy automata over a two-symbol alphabet and the automatic transformation semigroups, defined by them: Automata from S have 13 pairwise different growth functions. Five functions are almost constant, two are linear functions, one function has intermediate growth, and five are the functions of exponential growth. These automata define 27 pairwise nonisomorphic semigroups thatare not groups. Among them there are semigroups of finite, linear, square, intermediate and exponential orders of growth. The growth functions of all automata from S and the automatic transformation semigroups, defined by them, are calculated. The growth function of intermediate growth order is determined through a number of partitions of a natural number to the positive items, and all growth functions of exponential growth are described by linear recurrent relations. There was described the least possible Mealy automaton of intermediate growth. They define the monoid of intermediate growth that has infinite set of defining relations. All automata from the set S, that have linear growth, but define semigroups of square growth, are described. All non-invertible two-state automata over a two-symbol alphabet, that defining semigroups of exponential growth with nontrivial defining relations, and automata from the set S, that define free semigroup, are characterized.

Files

Similar theses