Joint low power state assignment of sequential automata of a net implementing a parallel automaton

Abstract

Objectives. The problem of low power state assignment of partial states of a parallel automaton is considered. The objective of the paper is to investigate the possibilities of using the decomposition in state assignment of partial states in order to decrease the task dimension.Methods. Parallel automaton is decomposed into a net of sequential automata whose states are assigned then with ternary vectors. The method for assignment uses searching for a maximal cut in a weighted graph that represents pairs of states connected by transitions. The edge weights of the graph are the values related to the probabilities of transitions.Results. A method to construct a net of sequential automata that realizes the given parallel automaton is described. The probabilities of transitions between sets are calculated by means of solving a system of linear equations according to the Chapmann – Kolmogorov method. The values of inner variables assigned to the states of every component sequential automaton are obtained from two-block partitions of its set of states that are determined by the cuts of corresponding transition graph.Conclusion. Applying parallel automaton decomposition allows decreasing the dimension of the laborious problem of state assignment. The proposed method is intended for application in computer aided systems for design of discrete devices.

Keywords

• parallel automaton
• partial state
• decomposition of automata
• state assignment of automata
• transition graph
• probability of transition between states