Geodesic
Low power assignment of partial states of a parallel automaton
Prikladnaâ diskretnaâ matematika, no. 2 (2022), pp. 113-122.

Voir la notice de l'article provenant de la source Math-Net.Ru

The problem of a low-power assignment of the partial states of a parallel automaton is considered. A method to solve that problem is suggested that provides minimizing the number of memory elements in the implementing circuit of the automaton and minimization of their switching activity. The problem is reduced to finding a minimal weighted cover of a graph with its complete bipartite sub-graphs (bi-cliques).
Keywords: parallel automaton, partial state, state assignment, complete bipartite sub-graph, weighted cover problem. 
@article{PDM_2022_2_a6,
     author = {Yu. V. Pottosin},
     title = {Low power assignment of partial states of a parallel automaton},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {113--122},
     publisher = {mathdoc},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PDM_2022_2_a6/}
}
TY  - JOUR
AU  - Yu. V. Pottosin
TI  - Low power assignment of partial states of a parallel automaton
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2022
SP  - 113
EP  - 122
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2022_2_a6/
LA  - en
ID  - PDM_2022_2_a6
ER  - 
%0 Journal Article
%A Yu. V. Pottosin
%T Low power assignment of partial states of a parallel automaton
%J Prikladnaâ diskretnaâ matematika
%D 2022
%P 113-122
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2022_2_a6/
%G en
%F PDM_2022_2_a6
Yu. V. Pottosin. Low power assignment of partial states of a parallel automaton. Prikladnaâ diskretnaâ matematika, no. 2 (2022), pp. 113-122. http://geodesic.mathdoc.fr/item/PDM_2022_2_a6/

[1] S. Muroga, VLSI System Design. When and How to Design Very-Large-Scale Integrated Circuits, John Wiley Sons, N.Y., 1982 | MR

[2] M. Pedram, “Power minimization in IC design: Principles and applications”, ACM Trans. Design Automat. Electron. Syst., 6 (1996), 3–56 | DOI

[3] L. Kashirova, A. Keevallik, M. Meshkov, “State assignment of finite state machine for decrease of power dissipation”, Second Intern. Conf., CAD DD'97 (November 12-14, 1997, Minsk, Republic of Belarus), v. 1, NASB, Institute of Engineering Cybernetics, Minsk, 1997, 60–67

[4] A. Sudnitson, “Partition search for FSM low power synthesis”, Fourth Intern. Conf., Minsk, CAD DD'2001 (November 14-16, 2001), v. 1, NASB, Institute of Engineering Cybernetics, Minsk, 2001, 44–49

[5] A. D. Zakrevskiy, “Algorithms for low power state assignment of an automaton”, Informatika, 2011, no. 1 (29), 68–78 (in Russian) | MR

[6] Yu. V. Pottosin, “State assignment in a discrete automaton targeting an implementing low power circuit”, Prikladnaya Diskretnaya Matematika, 2011, no. 4 (14), 62–71 (in Russian) | DOI | Zbl

[7] Yu. V. Pottosin, “Low power race-free state assignment of an asynchronous automaton”, Informatika, 2015, no. 2 (46), 94–101 (in Russian)

[8] Yu. Pottosin, “Race-free state assignment for low power asynchronous automaton”, Further Improvements in the Boolean Domain, ed. B. Steinbach, Cambridge Scholars Publ, 2018, 253–267

[9] Yu. Pottosin, “Optimal state assignment of synchronous parallel automata”, Design of Embedded Control Systems, eds. M. A. Adamski, A. Karatkevich, M. Wegrzyn, Springer, N.Y., 2005, 111–124 | DOI

[10] A. D. Zakrevskiy, Parallel Algorithms for Logical Control, URSS, M., 2003, 304 pp. (in Russian) | MR

[11] J. L. Peterson, Petri Net Theory and the Modeling of Systems, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1981 | MR

[12] A. D. Zakrevskiy, Yu. V. Pottosin, L. D. Cheremisinova, Design of Logical Control Devices, TUT Press, Tallinn, 2009

[13] A. D. Zakrevskiy, Yu. V. Pottosin, L. D. Cheremisinova, Combinatorial Algorithms of Discrete Mathematics, TUT Press, Tallinn, 2008

[14] Yu. V. Pottosin, Combinatorial Problems in Logical Design of Discrete Devices, Belaruskaja Navuka, Minsk, 2021, 175 pp. (in Russian)

[15] A. D. Zakrevskiy, “Optimization of set covering”, Logical Language for Representation of Algorithms for Relay Devices Synthesis, ed. M. A. Gavrilov, Nauka, M., 1966, 136–148 (in Russian) | MR