State minimization by means of incompatibility graph coloring

• Autorzy: Czerwiński R. , Kania D.

Warianty tytułu

PL

Minimalizacja stanów za pomocą kolorowania grafu niezgodności

• Konferencja: Electron Technology Conference ELTE 2010. 10 ; International Microelectronics and Packing IMAPS-CPMT. 34 ; 22-25.09.2010 ; Wrocław, Poland
• Języki publikacji: EN

Abstrakty

EN

A method for state minimization of FSMs is presented which is based on coloring the incompatibility graph, introduced in letter algorithm, it is very compact and can be implemented as a quick computer program, especially as a preprocessing method in the process of exact state minimization.

PL

Metoda minimalizacji stanów układów sekwencyjnych jest przedstawiona w artykule. Zaprezentowana metoda wykorzystująca metodę kolorowania grafu niezgodności stanów jest bardzo zwięzła i może być zaimplementowana jako szybki program komputerowy. Metoda jest szczególnie przydatna w procesie wstępnego zredukowania liczby stanów w celu przeprowadzenia dokładnej minimalizacji.

Słowa kluczowe

EN

finite state machine; state minimization; graph coloring

PL

automat sekwencyjny; minimalizacja liczby stanów; kolorowanie grafów

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2011
• Tom: Vol. 52, nr 3
• Strony: 160--162
• Opis fizyczny: Bibliogr. 6 poz., tab., wykr.

Twórcy

autor

Czerwiński R.

autor

Kania D.

• Politechnika Śląska, Instytut Elektroniki, Gliwice

Bibliografia

• [1] Hartmanis J., Stearns R. E.: Some dangers in the state reduction of sequential machines. Information and Control, Vol. 5, 1962, pp. 252-260.
• [2] Paull M., Unger S.: Minimizing the number of states in incompletely specified state machines. IRE Transactions on Electronic Computers, EC-8, 1959, pp. 356-367.
• [3] Kam T., Villa T., Brayton R., Sangiovanni-Vincentelli A.: Synthesis of Finite State Machines: Functional Optimization. Kluwer Academic Publishers, 1998.
• [4] Perkowski M., Malvi R., Grygiel S., Burns M., Mishchenko A.: Graph coloring Algorithms for Fast Evaluation of Curtis Decomposition. The 36-th ACM/IEEE Design Automation Conference, DAC'99, New Orleans, 1999, pp. 225-230.
• [5] Wan W., Perkowski M.: A new Approach to the Decomposition of Incompletely Specified Multi-Output Functions Based on Graph Coloring and Local Transformations and Its Applications to FPGA Mapping. Proc. of the Conf. on European Design Automation, 1992, pp. 230-235.
• [6] MCNC, LGSynth'91 benchmarks, Collaborative Benchmarking Laboratory, Department of Computer Science at North Carolina State University.