Złożoność półgrupy charakterystycznej iloczynu prostego
automatów asynchronicznych silnie spójnych i ustalonych analogów
ich rozszerzeń dla każdego słowa z języka Σ+ = (sigma_0 ∪ sigma_1)+
1
Instytut Pojazdów Szynowych „TABOR”
Data publikacji: 02-02-2011
Rail Vehicles/Pojazdy Szynowe 2011,1,13-38
STRESZCZENIE
Niniejsza publikacja kontynuuje cykl artykułów [6,7,8,9,12,14,15,16,17] dotyczący
złożoności obliczeniowej półgrupy charakterystycznej automatów asynchronicznych
silnie spójnych i ustalonych analogów ich rozszerzeń. W projektowaniu sterowania
pojazdów szynowych wykorzystuje się coraz częściej mikrosystemy cyfrowe
dorealizowania sterowania inteligentnego, rozproszonego. W mikrosystemach
cyfrowych tworzenie oprogramowania możliwe jest z wykorzystaniem maszyny stanowej
(automatu),któryumożliwia tworzenie oprogramowania w oparciu o sporządzony
wcześniej graf automatu. Umożliwia to analizę pracy mikrosystemu cyfrowego
w pojazdach szynowych i oszacowanie złożoności obliczeniowej pólgrup charakterystycznych
automatów. Ma to istotny wpływ na złożoność czasową obliczeń,
jak również wielkości pamięci, potrzebnej do rozwiązania problemu.
Artykuł powstał w wyniku realizacji projektu badawczego MN i SzW nr N N509
398236 „Mikrosystemy cyfrowe do inteligentnego, rozproszonego i współbieżnego
sterowania pojazdami szynowymi.”
REFERENCJE (30)
1.
Arbib M.A.: Algebraic theory of machines languages and semigroups, Acadimic Press, New York and London 1968.
2.
Aho A.V., Hopcrofy I.E., Ullman I.D.:Projektowanie i analiza algorytmów komputerowych,PWN,Warszawa 1983.
3.
Barnes B.: On the groups of automorhism of strongly connected automata, Math.Syst. Theory 4, 4 (1970).
4.
Beatty I. C.;On some properties of semigroup of a machine which are preserved under state minimization, Information and Control 11, 3 (1970).
5.
Beyga L.: On periodic sums of automata associated with isomorphism, Foundations of Control Enginiering 1,3 (1976).
6.
Bocian S.: Złożoność półgrupy charakterystycznej automatów asynchronicznych i ich rozszerzeń, Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk nr 552, Warszawa, 1984.
7.
Bocian S., Mikołajczak.: Computational aspect of assigning characteristic semigroup asychronous automata and their extensions, Colloqia Mathematica Societatis Janos Bolyai nr 44,Amsterdam, New York, Budapest, 1985.
9.
Bocian S.: The complexity of semigroup characterization of asynchronous strongly connection automation and their extensions, Computational topology and geometry and computation in teaching mathematic, Universal de Sevilla,1987.
10.
Bocian S.: A new method of calculating the smallest common multiple, Computational topology and geometry and computation in teaching mathematic, Universal de Sevilla,1987.
11.
Bocian S.: Nowy sposób wyznaczania najmniejszej wspólnej wielokrotności liczb naturalnych, jako model matematyczny automatu w technice komputerowej, Pojazdy szynowe 1/2002.
12.
Bocian S.: Złożoność pólgrupy charakterystycznej automatów asynchronicznych silnie spójnych ustalonych analogów ich rozszerzeń związanych z izomorfizmami, TRANSCOMP - XIII INTERNATIONAL CONFERENCE COMPUTER SYSTEMS AIDED SCIENCES, INDUSTRY AND TRANSPORT(Logistyka 6/2009), Zakopane 2009.
13.
Bocian S.: Nowy sposób wyznaczania najmniejszej wspólnej wielokrotności liczb naturalnych, OR – 9834 (praca nie publikowana).
14.
Bocian S: Złożoność półgrupy charakterystycznej sumy prostej i iloczynu prostego automatów asynchronicznych silnie spójnych, TRANSCOMP - XIV INTERNATIONAL CONFERENCE COMPUTER SYSTEMS AIDED SCIENCES, INDUSTRY AND TRANSPORT(Logistyka 6/2010), Zakopane 2010.
15.
Bocian S: Izomorfizm półgrupy charakterystycznej sumy prostej i iloczynu prostego automatów asynchronicznych silnie spójnych i ustalonych analogów ich rozszerzeń TRANSCOMP - XIV INTERNATIONAL CONFERENCE COMPUTER SYSTEMS AIDED SCIENCES, INDUSTRY AND TRANSPORT(Logistyka 6/2010), Zakopane 2010.
16.
Bocian S: Złożoność półgrupy charakterystycznej iloczynu prostego automatów asynchronicznych silnie spójnych ustalonych analogów rozszerzeń związanych z izomorfizmami, TRANSCOMP - XIV INTERNATIONAL CONFERENCE COMPUTER SYSTEMS AIDED SCIENCES, INDUSTRY AND TRANSPORT (Logistyka6/2010), Zakopane 2010.
17.
Bocian S.: Złożoność półgrupy charakterystycznej sumy prostej automatów asynchronicznych silnie spójnych i ustalonych analogów ich rozszerzeń dla każdego słowa z języka Σ+ = ( ∪ ) + 0 1 σ σ , Pojazdy Szynowe Nr 4/2010.
20.
Grzymała-Busse J.W.: On the periodic reprezentation and reducibility of periodic automata, J.Assoc. Comput. Mach. 16, 3(1969).
21.
Grzymała-Busse J.W.: On the endomorphisms of finite automata, Mach. Syst. Theory 4, 4 (1970).
22.
Grzymała-Busse J.W.: Podautomaty automatów skończonych związane ze zmianączsu pracy, Politechnika Poznańska, Rozprawy nr.46, Poznań, 1972.
23.
Kerntopf P.: Podstawowe pojęcia matematyczne w teorii automatów, PWN, Warszawa 1967.
24.
Mikołajczak B., Miądowicz Z.: On the automorphisms group of strongly related automata and structural properties of finite automata and extensions, Foundations of Control Engineering,1,2 (1976).
25.
Mikołajczak B.: On the structure of cyclic automata and their generalized periodic sums, Technical Report, Computer Science Department, Cornell University, 1977.
26.
Mikołajczak B.: On the structure of cyclic automata and their generalized periodic sums, Foundations of Control Engineering, 3,1 (1978).
27.
Mikołajczak B.: Uogólnione przekształcenia okresowe automatów skończonych, Politechnika Poznańska, Rozprawy nr.98, Poznań 1979.
28.
Mikołajczak B.: Algebraiczna i strukturalna teoria automatów, PWN Warszawa - Łódź, 1985.
29.
Mikołajczak B.: Przekształcenia i złożoność obliczeniowa problemów w teorii automatów, PWN Warszawa – Poznań, 1988.
30.
Oehmke R.H.: The semigroup of a strongly connected automaton, Math. Systems Theory, 15 (178).
Udostępnij
| eISSN: | 2719-9630 |
| ISSN: | 0138-0370 |
Przetwarzamy dane osobowe zbierane podczas odwiedzania serwisu. Realizacja funkcji pozyskiwania informacji o użytkownikach i ich zachowaniu odbywa się poprzez dobrowolnie wprowadzone w formularzach informacje oraz zapisywanie w urządzeniach końcowych plików cookies (tzw. ciasteczka). Dane, w tym pliki cookies, wykorzystywane są w celu realizacji usług, zapewnienia wygodnego korzystania ze strony oraz w celu monitorowania ruchu zgodnie z Polityką prywatności. Dane są także zbierane i przetwarzane przez narzędzie Google Analytics (więcej).
Możesz zmienić ustawienia cookies w swojej przeglądarce. Ograniczenie stosowania plików cookies w konfiguracji przeglądarki może wpłynąć na niektóre funkcjonalności dostępne na stronie.
Możesz zmienić ustawienia cookies w swojej przeglądarce. Ograniczenie stosowania plików cookies w konfiguracji przeglądarki może wpłynąć na niektóre funkcjonalności dostępne na stronie.
