Rozpoznawanie grafów doskonałych na potrzeby automatycznej syntezy układów cyfrowych

• Autorzy: Mielcarek K.

Warianty tytułu

EN

Recognizing of perfect graphs for automatic synthesis of integrated digital circuits

• Konferencja: Konferencja Informatyka - Sztuka czy Rzemiosło (19-22 czerwca 2006; Złotniki Lubańskie; Polska)
• Języki publikacji: PL

Abstrakty

PL

Niniejszy artykuł ma na celu wskazanie potencjalnej użyteczności algorytmów do rozpoznawania grafów doskonałych. Zagadnienia prezentowane poniżej dają się rozwiązać w czasie wielomianowym, gdzie dla grafów w ogólności problem złożoności należy do klasy problemów NP-zupełnych. Zastosowanie grafów doskonałych jako pośredniego modelu formalnego jest o tyle użyteczne, że znacząca większość zależności, opisujących rzeczywiste układy sekwencyjne, daje w wyniku grafy należące do podklasy grafów doskonałych. Badania w tej dziedzinie są prowadzone w wielu ośrodkach światowych mają na celu przy-spieszenie procesów automatycznej analizy i syntezy układów dyskretnych. Referat jest związany z wykorzystaniem sieci Petriego do opisu układów cyfrowych, a w szczególności rekonfigurowalnych sterowników logicznych. Pokazano przykład analizy dyskretnej przestrzeni stanów lokalnych automatu współbieżnego, modelującego program sterownika logicznego przedstawionego w języku SFC. Do analizy wykorzystano metody badania grafów doskonałych.

EN

: This paper should to point out potential strength of perfect graph algorithms for automated synthesis of digital circuits. Typically known problems are NP-complete but using perfect graphs complexity is decreasing to polynomial. Studies in this matter shows that plenty of dependencies describing real sequential circuits can be described using perfect graphs. There shown the analysis of digital controller described in SFC. In analysis was used methods for testing perfect graphs.

Słowa kluczowe

PL

grafy doskonałe; algorytmy rozpoznawania grafów doskonałych; teoria grafów; synteza sterowników automatyczna

EN

perfect graphs; perfect graphs recognizing algorithms; graph theory; automatic synthesisi of digital controllers

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2006
• Tom: R. 52, nr 6 bis
• Strony: 14--16
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Mielcarek K.

• Instytut Informatyki i Elektroniki, Uniwersytet Zielonogórski,

Bibliografia

• [1] Adamski M., „Metodologia projektowania reprogramowalnych ste-rowników logicznych z wykorzystaniem elementów CPLD i FPGA”, Reprogramowalne Układy Cyfrowe RUC 98, Szczecin 12-13.03.1998, ss. 15-22, 1998
• [2] Adamski M., „Aplication Specific logic Controler for Safety Critical Systems”, 1999 IFACTriennial congress, Beijing (Chiny) vol. 0, ss. 519-529
• [3] Olivier Coudert, „Exact Coloring of Real-Life Graphs is Easy”, Synopsys, Inc. 700 East Middlefield Rd., Moutain View, CA 94043, Proc. of the 34th Design Automation Conference DAC,, Anaheim, CA, USA, June 1997, pp. 121-126
• [4] Cornuejols G., Xinming Liu, Vuskovic K., “A polynomial algorithm for recognizing perfect graphs”, Proceeding 44th Annual IEEE Symposium, 2003
• [5] Giovani De Micheli: „Synteza i optymalizacja układów cyfrowych”, Wydawnictwa Naukowo-Techniczne, Warszawa 1998
• [6] Martin Charles Golumbic: „Algorithmic Graph Theory and Perfect Graphs”, Courant Institute of Mathematical Science, New York University, Academic Press 1980
• [7] International Electrotechnical Commission, “Programable controllers. Part 3 - Programming Languages IEC 1131-3”, Genewa, 1993
• [8] Leuker G. S., “Interval graph algorithms. Ph. D. thesis”, Princeton University
• [9] Mielcarek K, „Grafy doskonałe jako alternatywa dla automatycznej syntezy i optymalizacji układów cyfrowych”, Metody i systemy kom-puterowe w badaniach naukowych i projektowaniu inżynierskim: IV Krajowa Konferencja. Kraków, Polska, 2003, Oprogramowanie Naukowo-Techniczne, 2003
• [10] M. Conforti, G. Cornuejols, A. Kapoor, K. Vuskovic, „Even-hole-free-graphs, Part II: Recognition algorithm”, Journal of Graph Theory 40 (2002) 238-266
• [11] G. Cornuejols, W. H. Cunnigham, „Compositions for perfect graphs”, Discrete Mathematics 55 (1985) 245-254