Złożoność półgrupy charakterystycznej automatów asynchronicznych spójnych ustalonych analogów ich rozszerzeń związanych z izomorfizmami

• Autorzy: Bocian, S.

Warianty tytułu

EN

Complexity of the characteristic semigroup of the asynchronous automatons of the connected determined analogs, their extensions associated with isomorphisms

• Języki publikacji: PL

Abstrakty

PL

Półgrupa charakterystyczna automatu ingeruje w algorytm obliczeniowy uogólnionych homomorfizmów automatów, zatem wyznaczanie złożoności pólgrupy charakterystycznej pozwala na oszacowanie złożoności obliczeniowej uogólnionych homomorfizmów dla innych klas automatów. W zakresie modelu matematycznego koncepcja ustalonego analogu rozszerzenia automatu A związanego z izomorfizmami g0, g1,..., gq-1 , gdzie q stopień rozszerzenia przy, odpowiednich założeniach symuluje automat zmienny w czasie. Automat zmienny w czasie jest adekwatnym modelem matematycznym dla wielu procesów technicznych i obliczeniowych czasu rzeczywistego. Automaty te symulują pracę kilku automatów za pomocą jednego automatu zmiennego w czasie.

EN

The characteristic semigroup of the automaton interferes in the computational algorithm of the generalized homeomorphisms of the automatons. Then determination the complexity of the characteristic semigroup enables to estimate the complexity of the computational generalized homeomorphism for the other classes of the automatons. In the range of the mathematical model the conception of the determined analog of the extension of the automaton A associated with the isomorphism g0, g1,…,gq-1, where q is the grade of the extensions, with the suitable assumptions it simulates the automaton variable in time. The variable automation in time is the adequate mathematical model for the many technical and computational processes of the real time.

Słowa kluczowe

PL

automat asynchroniczny spójny; półgrupa charakterystyczna; teoria automatów

EN

connected asynchronous automaton; characteristic semi-group of automaton; automata theory

• Czasopismo: Logistyka
• Rocznik: 2014
• Tom: nr 3
• Strony: 605--614
• Opis fizyczny: Bibliogr. 21 poz., rys., pełen tekst na CD

Twórcy

autor

Bocian, S.

• Instytut Pojazdów Szynowych „TABOR” POLSKA; Poznań 61-055;Warszawska 181,

Bibliografia

• 1. Arbib M.A.: Algebraic theory of machines languages and semigroups, Acadimic Press, New York and London 1968.
• 2. Aho A.V., Hopcroft 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. Beyga L.: On periodic sums of automata associated with isomorphism, Foundations of Control Enginiering 1,3 (1976).
• 5. 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.
• 6. Bocian S., Mikołajczak B.: Computational aspect of assigning characteristic semigroup asynchronous automata and their extensions, Colloqia Mathematica Societatis Janos Bolyai nr 44,Amsterdam, New York, Budapest, 1985.
• 7. 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.
• 8. Bocian S.: Mikrosystemy cyfrowe stosowane w pojazdach szynowych I złożoność obliczeniowa pólgrupy charakterystycznej automatu spójnego. TRANSCOMP – XVII INTERNATIONAL CONFERENCE COMPUTER SYSTEMS AIDED SCIENCES, INDUSTRY AND TRANSPORT(Technika Transportu Szynowego-TTS, 9/2013), Zakopane 2013.
• 9. Fleck A.C.: Isomorphism groups of automata, J. Assoc. Comp. Mach. 9, 4 (1962).
• 10. Gecseg F., Peak J.: Algebraic theory of automata, Akademia Kiado, Budapest, 1972.[8]
• 11. Grzymała-Busse J.W.: On the periodic reprezentation and reducibility of periodic automata, J.Assoc. Comput. Mach. 16, 3(1969).
• 12. Grzymała-Busse J.W.: On the endomorphisms of finite automata, Mach. Syst. Theory 4, 4 (1970).
• 13. Grzymała-Busse J.W.: Podautomaty automatów skończonych związane ze zmianą czasu pracy, Politechnika Poznańska, Rozprawy nr.46, Poznań, 1972.
• 14. Kerntopf P.: Podstawowe pojęcia matematyczne w teorii automatów, PWN, Warszawa 1967.
• 15. 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).
• 16. Mikołajczak B.: On the structure of cyclic automata and their generalized periodic sums, Technical Report, Computer Science Department, Cornell University, 1977.
• 17. Mikołajczak B.: On the structure of cyclic automata and their generalized periodic sums, Foundations of Control Engineering, 3,1 (1978).
• 18. Mikołajczak B.: Uogólnione przekształcenia okresowe automatów skończonych, Politechnika Poznańska, Rozprawy nr.98, Poznań 1979.
• 19. Mikołajczak B.: Algebraiczna i strukturalna teoria automatów, PWN Warszawa - Łódź, 1985.
• 20. Mikołajczak B.: Przekształcenia i złożoność obliczeniowa problemów w teorii automatów, PWN Warszawa – Poznań, 1988.
• 21. Oehmke R.H.: The semigroup of a strongly connected automaton, Math. Systems Theory, 15 (178).