Applied Theory of Automata

Decomposition of a parallel automaton into a net of sequential automata

Yu. V. Pottosin

United Institute of Informatics Problems, National Academy of Sciences of Belarus, Minsk, Belarus

Abstract: A method to construct a net of sequential automata that realizes the given parallel automaton is described. The parallelism relation of partial states is used to decompose a given parallel automaton. Each component automaton's set of states is based on mutually nonparallel partial states of the given parallel automaton. The state assignment of a component automaton provides decreasing power consumption of the designed device based on reducing the switching activity of memory elements. The joint low power assignment of states of component automata takes into consideration the conditional compatibility of states. The component automata exchange with binary signals. The communication between component automata is minimized.

Keywords: parallel automaton, partial state, state assignment, complete bipartite sub-graph, weighted cover problem.

UDC: 519.711

Language: English

DOI: 10.17223/20710410/70/2