Asynchronous Systems of Parallel Communicating Finite Automata

• Autorzy: Vollweiler M.

Identyfikatory

DOI

10.3233/FI-2015-1149

• Języki publikacji: EN

Abstrakty

EN

Synchronous systems of parallel communicating one-way finite automata have already been investigated. There, all components work stepwise in parallel, and the communication between the components is realized by requesting states in a one-directional manner. This means that one component can request information in form of the current state from another component, where the latter one sends its current state without realizing that a communication takes place. Here, we introduce asynchronous systems of parallel communicating one-way and two-way finite automata with a bidirectional communication protocol. A communication only takes place, when both components - the requesting and the responding component - are ready to communicate. It is shown that almost all language classes that are characterized by these systems coincide with the language classes that are characterized by multi-head finite automata. Moreover, our communication protocol uses blocking point-to-point communications, i.e. a communication takes place between two components, and a communicating component is blocked until the communication has been finished. There have also been studied asynchronous systems of finite automata with non-blocking communication in the literature. Thus, we compare synchronous and asynchronous systems on the one hand and asynchronous systems with blocking and non-blocking communication on the other hand. Finally, we give some results on the communication complexity of our systems, where the amount of communication is measured by counting each message which is sent from one component to another during a computation of a system. Particularly, we show that with constantly many communications our systems can only accept regular languages, and at most linearly (polynomially) many communications are needed for systems of one-way (two-way) components depending on the length of the input. Further, there exists no system that executes more than constantly many and less than linearly many communications.

Słowa kluczowe

EN

machine theory; finite state machine; robots; computer simulation; programming languages

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 136, nr 1/2
• Strony: 177--197
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Vollweiler M.

• Fachbereich Elektrotechnik/Informatik Universität Kassel, 34109 Kassel, Germany

Bibliografia

• [1] Bordihn, H., Kutrib, M., Malcher, A.: Undecidability and Hierarchy Results for Parallel Communicating Finite Automata, International Journal of Foundations of Computer Science, 22(7), 2011, 1577–1592.
• [2] Bordihn, H., Kutrib, M., Malcher, A.: On the Computational Capacity of Parallel Communicating Finite Automata, International Journal of Foundations of Computer Science, 23(03), 2012, 713–732.
• [3] Choudhary, A., Krithivasan, K., Mitrana, V.: Returning and non-returning parallel communicating finite automata are equivalent, Informatique Théorique et Applications, 41(2), 2007, 137–145.
• [4] Csuhaj-Varjú, E., Dassow, J., Kelemen, J., Păun, G.: Grammar Systems: A Grammatical Approach to Distribution and Cooperation, Gordon and Breach Science Publishers, Inc., Newark, NJ, USA, 1994.
• [5] Csuhaj-Varjú, E., Martín-Vide, C., Mitrana, V., Vaszil, G.: Parallel Communicating Pushdown Automata Systems, International Journal of Foundations of Computer Science, 11(4), 2000, 631–650.
• [6] Czeizler, E., Czeizler, E.: Parallel Communicating Watson-Crick Automata Systems, Automata and Formal Languages, 11th International Conference, AFL 2005, Dobog´ok˝o, Hungary, May 17-20 (Z.Ésik, Z. Fülöp, Eds.), Institute of Informatics, University of Szeged, 2005.
• [7] Hartmanis, J.: On Non-Determinancy in Simple Computing Devices, Acta Informatica, 1(4), 1972, 336–344.
• [8] Hopcroft, J. E., Ullman, J. D.: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.
• [9] Ibarra, O. H.: On Two-Way Multihead Automata, Journal of Computer and System Sciences, 7(1), 1973, 28–36.
• [10] Jurdziński, T.: Communication Aspects of Computation of Systems of Finite Automata, Ph.D. Thesis, Institute of Computer Science, University of Wrozław,Wrocław, 2000.
• [11] Jurdziński, T., Kutyłowski, M., Lorys, K.: Multi-party Finite Computations, in: Computing and Combinatorics (T. Asano, H. Imai, D. Lee, S.-i. Nakano, T. Tokuyama, Eds.), vol. 1627 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 1999, 318–329.
• [12] Jurdziński, T., Kutyłowski, M., Zatopiański, J.: Communication Complexity for Asynchronous Systems of Finite Devices, Proceedings of the 15th International Parallel & Distributed Processing Symposium (IPDPS-01), Los Alamitos, CA, April 23-27, 2001, IEEE Computer Society, 2001.
• [13] Jurdziński, T., Kutyłowski,M., Zatopiański, J.: Efficient Simulation of Synchronous Systems by Multi-speed Systems, ITA, 39(2), 2005, 403–419.
• [14] Martín-Vide, C., Mateescu, A., Mitrana, V.: Parallel Finite Automata Systems Communicating by States, International Journal of Foundations of Computer Science, 13(5), 2002, 733–749.
• [15] Martín-Vide, C., Mitrana, V.: Some undecidable problems for parallel communicating finite automata systems, Information Processing Letters, 77(5-6), 2001, 239–245.
• [16] Otto, F.: Asynchronous PC Systems of Pushdown Automata, in: Language and Automata Theory and Applications (A.-H. Dediu, C.Martín-Vide, B. Truthe, Eds.), vol. 7810 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, Berlin, 2013, 456–467.
• [17] Păun, G., Santean, L.: Parallel Communicating Grammar Systems: The Regular Case, Analele Universitatii din Bucuresti, Seria matematica-informatica, 2, 1989, 55–63.
• [18] Vollweiler, M., Otto, F.: Systems of Parallel Communicating Restarting Automata, 4th Workshop on Non-Classical Models for Automata and Applications (R. Freund, M. Holzer, B. Truthe, U. Ultes-Nitsche, Eds.), Österreichische Computer Gesellschaft, Fribourg, Switzerland, 2012