V. V. Sapozhnikov, Vl. V. Sapozhnokov, “Structural Simplification of the Logic Unit of a Finite Automaton Whose States Are Assigned by the Columns of the Transition Table”, Probl. Peredachi Inf., 1975, Volume 11, Issue 4,Pages <nobr>77

Automata Theory

Structural Simplification of the Logic Unit of a Finite Automaton Whose States Are Assigned by the Columns of the Transition Table

V. V. Sapozhnikov, Vl. V. Sapozhnokov

Abstract: The authors propose state assignment algorithms for an asynchronous finite automaton (AFA) that represent an extension of the Liu–Sagalovich method [C. N. Liu, J. Assoc. Comp. Mach., 1963, vol. 10, no. 2, pp. 209–216; Yu. L. Sagalovich, Probl. Inf. Trans., 1967, vol. 3, no. 2, pp. 56–64], the purpose being to simplify the structure of the logic unit. A necessary and sufficient existence condition for complete parallel decomposition of AFA is obtained.

UDC: 621.391.1:62-507

Received: 21.01.1974
Revised: 21.05.1975