Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "exact transversal" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-4 z 4
    Tytuł:
    Zastosowanie teorii hipergrafów w procesie analizy systemów dyskretnych opisanych sieciami Petriego
    Application of hypergraphs to analysis of discrete-systems described with Petri Nets
    Autorzy:
    Adamski, M.
    Wiśniewska, M.
    Powiązania:
    https://bibliotekanauki.pl/articles/155263.pdf
    Data publikacji:
    2011
    Wydawca:
    Stowarzyszenie Inżynierów i Techników Mechaników Polskich
    Tematy:
    hipergraf
    transwersala dokładna
    sieć Petriego
    system dyskretny
    hypergraph
    exact transversal
    Petri net
    discrete system
    Opis:
    W artykule zaprezentowane zostały nowe metody wspomagające proces analizy systemów dyskretnych opisanych sieciami Petriego. Relacje w prototypowanym systemie dyskretnym są odwzorowane hiper-grafem. Dzięki temu projektowany, wbudowany, rekonfigurowany sterownik logiczny może zostać poddany efektywniejszemu procesowi analizy z wykorzystaniem nowych algorytmów, związanych z traktowanymi łącznie teoriami hipergrafów i sieci Petriego. Wykorzystano między innymi takie procedury jak dopełnienie, dualizm, transwersale, transwersale dokładne oraz kolorowanie hipergrafu. W artykule w sposób nieformalny wykorzystano autorskie twierdzenia, wspomagające cały proces projektowania sterowników. Szczególną uwagę zwrócono na nowe sposoby analizy systemów dyskretnych, opisanych sieciami Petriego, takie jak częściowa weryfikacja poprawności specyfikacji sterownika na podstawie struktury hipergrafu współbieżności oraz zastosowanie transwersal do-kładnych w procesie wyodrębniania powiązanych ze sobą procesów sekwencyjnych.
    In the paper application of the hypergraph theory to analysis of discrete-systems described by means of Petri Nets is proposed. The relations between local states are represented by hypergraph vertices whose edges correspond to the global states. Therefore, the analysis of a prototype system can be performed by more effective operations supported by the hypergraph theory as well as the Petri net theory (such as dualism, hypergraph complement, transversals, exact transversals, hypergraph colouring). In the paper the authors propose application of the concurrency hypergraph to the analysis of a discrete-system. Such a structure refers to the traditional concurrency graph, however it keeps information about global states of the analysed system. Moreover, the concurrency hypergraph has some unique properties, which can lead to reduction in the computational complexity of some algorithms of the analysis. All minimal transversals in the concurrency hypergraph are also exact transversals. Therefore, such a hypergraph can be applied also to the decomposition process of a discrete-system, which is described by a Petri Net. After the analysis, a controller described by a Petri Net can be decomposed into concurrent sub-nets (concurrent automata). Each exact transversal of the concurrency hypergraph refers to the concurrent automata. The proposed solution allows significantly reducing the computational complexity to a polynomial. The traditional methods, based on the coloring of a concurrency graph are exponential time algorithms, thus they are defined to be NP-complete.
    Źródło:
    Pomiary Automatyka Kontrola; 2011, R. 57, nr 8, 8; 945-947
    0032-4140
    Pojawia się w:
    Pomiary Automatyka Kontrola
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Algorytm selekcji wykorzystujący teorię hipergrafów
    A selection algorithm based on the hypergraph theory
    Autorzy:
    Stefanowicz, Ł.
    Wiśniewski, R.
    Adamski, M.
    Powiązania:
    https://bibliotekanauki.pl/articles/152957.pdf
    Data publikacji:
    2014
    Wydawca:
    Stowarzyszenie Inżynierów i Techników Mechaników Polskich
    Tematy:
    selekcja
    podsieci automatowe
    implikanty proste
    hipergraf
    hipergraf transwersal dokładnych
    transwersala
    transwersala dokładna
    selection
    State Machine Components
    SMCs
    prime implicants
    hypergraph
    transversal
    exact transversal
    Opis:
    Artykuł porusza kwestię selekcji określonych elementów zbioru z wykorzystaniem teorii hipergrafów. Przedstawiona została idea wspólnego algorytmu selekcji, w przypadku takich problemów, jak selekcja podsieci automatowych w dekompozycji sieci Petriego, a także selekcja implikantów prostych w procesie miminalizacji funkcji logicznych. Jako bazowy algorytm, wykorzystano metodę transwersal dokładnych, jednocześnie usprawniając ją o alternatywną scieżkę w przypadku, kiedy dany hipergraf selekcji nie należy do klasy hipergrafu transwersal dokładnych. Jak pokazują badania, metoda może być dobrą alternatywą obok wykorzystywanych metod tradycyjnych.
    The paper deals with the selection problem based on the hypergraph theory. There is presented an idea of a common selection algorithm for selection of State Machine Components and Prime Implicants. The exact transversal method was used as a baseline algorithm. It was improved by supporting it with an optional path when a given selection hypergraph did not belong to the xt-class (class of the exact transversal hypergraph). In this case, the exact transversal was searched. When it was unsuccessful, the regular transversal was searched. The studies prove that the method allows obtaining the exact solution when the selection hypergraph does not belong to the xt-class, but has an exact transversal. The presented results show that a hypergraph which does not belong to the xt-class may have an exact transversal enabling obtaining a solution which would be as good as the one obtained with the backtracking method. The exact solution was also obtained with the use of an ordinary transversal, which de facto indicated that the regular transversals allowed, in certain cases, obtaining the exact solution. It seems to confirm the aptly determined class of solutions of the proposed improvements. In some cases, the solution contained one extra subnet, but in one tested case, the solution turned out to be much worse than the exact one.
    Źródło:
    Pomiary Automatyka Kontrola; 2014, R. 60, nr 7, 7; 516-518
    0032-4140
    Pojawia się w:
    Pomiary Automatyka Kontrola
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Zastosowanie hipergrafów w procesie selekcji implikantów prostych
    Application of hypergraphs to the prime implicant selection process
    Autorzy:
    Wiśniewski, R.
    Stefanowicz, Ł.
    Powiązania:
    https://bibliotekanauki.pl/articles/155992.pdf
    Data publikacji:
    2013
    Wydawca:
    Stowarzyszenie Inżynierów i Techników Mechaników Polskich
    Tematy:
    minimalizacja funkcji logicznych
    selekcja implikantów prostych
    hipergraf
    transwersala dokładna
    minimization of Boolean functions
    selection of prime implicants
    hypergraph
    exact transversal
    Opis:
    W referacie przedstawiona została nowa koncepcja selekcji implikantów prostych w procesie dwupoziomowej minimalizacji funkcji logicznych. Aktualnie znane metody selekcji bazują na połączeniu metod dokładnych z przybliżonymi. W artykule zaproponowana została nowatorska metoda selekcji, która w całości opiera się na algorytmach dokładnych, poprzez zastosowanie teorii hipergrafów. Najbardziej istotną zaletą proponowanego rozwiązania jest wielomianowa złożoność obliczeniowa całej operacji selekcji, która w przypadku ogólnym ma złożoność wykładniczą.
    : In the paper a new idea for the selection of prime implicants is proposed. The method is based on the two-level minimization process of the Boolean functions, according to the Quine-McCluskey approach. Initially, the set of prime implicants for the logic function ought to be calculated. Next, the selection process is applied to achieve the minimal formula. Such an operation is a typical covering problem and in general case it has exponential computational complexity. In the paper we propose a new prime implicants selection method. An idea is based on the hypergraph theory. The prime implicants table is formed as a selection hypergraph. If the selection hypergraph belongs to the Exact Transversal Hypergraph class (xt-class), the solution may be obtained in a polynomial time, which is not possible in a general case. The proposed method is illustrated by an example. All necessary steps are shown in order to apply the proposed selection algorithm to minimize an exemplary Boolean function.
    Źródło:
    Pomiary Automatyka Kontrola; 2013, R. 59, nr 11, 11; 1195-1197
    0032-4140
    Pojawia się w:
    Pomiary Automatyka Kontrola
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Dekompozycja sterowników współbieżnych z zastosowaniem transwersal dokładnych hipergrafu
    Exact transversals in decomposition of Petri Nets into concurrent subnets
    Autorzy:
    Wiśniewska, M.
    Adamski, M.
    Wiśniewski, R.
    Powiązania:
    https://bibliotekanauki.pl/articles/155099.pdf
    Data publikacji:
    2011
    Wydawca:
    Stowarzyszenie Inżynierów i Techników Mechaników Polskich
    Tematy:
    hipergraf
    transwersala dokładna
    sieć Petriego
    dekompozycja sieci Petriego na podsieci współbieżne typu automatowego
    hypergraph
    exact transversal
    Petri net
    decomposition of a Petri Net into concurrent subnets automata
    Opis:
    W artykule zaprezentowany został nowatorski sposób dekompozycji cyfrowych sterowników współbieżnych opisanych z wykorzystaniem sieci Petriego na podsieci typu automatowego. W proponowanym rozwiązaniu relacje pomiędzy miejscami sieci Petriego określone za pomocą hipergrafu współbieżności. W odróżnieniu od dotychczas stosowanych rozwiązań, w artykule zaproponowano autorską koncepcję wyznaczania zbiorów niewspółbieżnych, która bazuje na obliczeniu transwersal dokładnych w hipergrafie współbieżności.
    In the paper a new decomposition method of a control system into concurrent automata is presented. The control unit is described as a Petri Net which is further decomposed into concurrent subnets. The main idea of the proposed method is application of exact transversals to the decomposition algorithm. Contrary to the traditional solutions, the authors propose the application of a concurrency hypergraph instead of a standard concurrency graph. The concurrent subnets are found by calculation of exact transversals in the hypergraph. The selection of concurrent automata is also performed with application of exact transversals. Such a solution allows achieving the optimal results (the fewest number of concurrent automata). The proposed concurrency hypergraph has some unique properties. First of all, it is defined to be an exact hypergraph. Therefore, each exact transver-sal in such a hypergraph refers to the concurrent automata. Moreover, all minimal transversals of the hypergraph are also exact transversals. Finally, computation and selection of all exact transversals can be performed in polynomial-time, and this is the most important advantage of the proposed method. The traditional solutions are based on the coloring of a concurrency graph, thus the complexity is NP-complete. All steps that are required in order to perform the decomposition of a controller described by a Petri Net are shown. The proposed method is compared with the traditional solution. Finally, the preliminary results of experiments are presented and discussed.
    Źródło:
    Pomiary Automatyka Kontrola; 2011, R. 57, nr 8, 8; 851-853
    0032-4140
    Pojawia się w:
    Pomiary Automatyka Kontrola
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-4 z 4

      Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies