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 znak sumowania n-elementów ciągu+ =(sigma 0 suma zbiorów sigma 1)+

• Autorzy: Bocian S.

Warianty tytułu

EN

Complexity of the characteristic semi-group of the asynchronous automatons direct product of the strongly connected and determined analogs of their exten-sions for the each word from language n-ary sumation+ = (sigma 0 union (cup) sigma1)+

• Języki publikacji: PL

Abstrakty

PL

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 do realizowania 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ółgrup 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".

EN

This publication continues the series of articles [6,7,8,9,12,14,15,16,17] concerning the computational complexity of the characteristic semi-group of the asynchronous automatons of the strongly connected and determined analogs of their extensions. In the designing of rail vehicles control are used more and more the digital microsystems for realization the intelligent, scattered and synchronous control. In the digital microsystems it is possible to create the software using the state machine (automaton) and create the software based on the previously drawn up graph of the automaton. This allows the analysis of the digital microsystem work in the rail vehicles and estimation of the computational complexity of characteristic semigroups of the automatons. This has an important impact on the time complexity of calculations, as well as the amount of memory needed to solve the problem. This article was written as a result of the Research Project of the Ministry of Science and Higher Education No. N N509 398236 "Digital microsystems for the intelligent, scattered and synchronous rail vehicles control".

Słowa kluczowe

PL

złożoność obliczeniowa; półgrupy charakterystycznych automatów; złożoność czasowa obliczeń; automat asynchroniczny; mikrosystemy cyfrowe; sterowanie inteligentne; sterowanie rozproszone; maszyna stanowa (automat); graf automatu

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Pojazdy Szynowe
• Rocznik: 2011
• Tom: Nr 1
• Strony: 13--38
• Opis fizyczny: Bibliogr. 30 poz., rys.

Twórcy

autor

Bocian S.

• Instytut Pojazdów Szynowych " TABOR "

Bibliografia

• [1] Arbib M.A.: Algebraic theory ofmachines 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 ofstrongly connected automata, Math.Syst. Theory 4, 4 (1970). 
• [4] Beatty L C.; On some properties ofsemigroup of a machinę which arę 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., Mikolajczak.: Computational aspect of assigning characteristic semigroup asychronous auto-
• mata and their extensions, Colloąia Mathematica Societatis Janos Bolyai nr 44,Amsterdam, New York, Budapest, 1985.
• [8] Bocian S.: Rozprawa doktorska , Politechnika Poznańska, 1986.
• [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ólgrupy 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 INTERNA-TIONAL 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 X — (ćT0 ^J (Jj) , Pojazdy Szynowe Nr 4/2010.
• [18] FleckA.C.: Isomorphism groups of automata, J. Assoc. Comp. Mach. 9, 4 (1962).
• [19] Gecseg F.,PeakJ.: Algebraic theory of automata, Akademia Kiado, Budapest, 1972.
• [20] Grzymala-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 offinite 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] KerntopfP.: Podstawowe pojęcia matematyczne w teorii automatów, PWN, Warszawa 1967. [24] Mikołaj czak B., Miądowicz Z.: On the automorphisms group ofstrongły rełated  automata and structurał properties offinite automata and extensions, Foundations ofControł Engineering,l,2 (1976).
• [25] Mikołaj czak B.: On the structure of cycłic automata and their generałized periodic sums, Technicał Report, Computer Science Department, Cornełł University, 1977.
• [26] Mikołaj czak B.: On the structure of cycłic automata and their generałized periodic sums, Foundations of Controł Engineering, 3,1 (1978).
• [27] Mikołaj czak B.: Uogólnione przekształcenia okresowe automatów skończonych, Politechnika Poznańska,Rozprawy nr. 98, Poznań 1979.
• [28] Mikołaj czak B.: Algebraiczna i strukturalna teoria automatów, PWN Warszawa - Łódź, 1985. [29] Mikołaj czak B.: Przekształcenia i złożoność obliczeniowa problemów w teorii automatów, PWN Warszawa -Poznań, 1988.
• [30] Oehmke R.H.: The semigroup ofa strongly connected automaton, Math. Systems Theory, 15 (178).