V. V. Dubarenko, V. G. Kurbanov
A new method called the «space expansion of logical systems conditions», is observed in this article. This method allows bringing together initial systems in the form of finite automats (FА) to the linear systems of algebraic equations in the form which is known as linear sequential machines (LSM). It allows passing from the imitational methods of analysis to the analytical methods of linear algebra according to mod2. The experiments are not carried out in this case. Numeral estimations are determined by means of non-search methods and the results are presented in analytical form.
Presentation of the models in the form of LSM is a matter of principle since it allows the tasks, for which the solution is unknown for the polynomial time, to be brought to the tasks, for which the effective algorithms of solution are known.
Algorithm of the reduction of the logical equations’ system to the form of LPM includes the following steps:
1. The task is presented by the system of linear equations (SLE) in polynomial form (Reed – Muller – Zhegalkin form) related to some initial step of the algorithm and to the initial state vector which corresponds to it.
2. The consequent line of the algorithm steps, where state vectors are represented by means of the components of the initial state vector and the components of non-recurrent conjunctions (terms) from these components, is observed.
3. The inner language of the task L in the alphabet (0,1), determined within the first step by the total initial state vector and terms’ vector from the components of this vector is expanded owing to the terms composed from the new combinations of the components of the initial state vector, which are referred to the various beats of the algorithm.
4. The expansion of the initial language L ends at the beat T after which the new combinations of the terms from the initial state vector are not generated within every new beat. In consequence, the initial SLE, describing the task is transformed into the expanded SLE which coincides with the system, typical for SLE, in the form:
where x(t) – is the expanded (in comparison with the first dictionary) binary state vector; u(t) – is the input vector; y(t) – is the output vector; g, h – are the 0, 1 vectors; A, B, C, D – are the 0, 1 matrices