Digitale Bibliotheek
Sluiten Bladeren door artikelen uit een tijdschrift
   volgende >>
     Tijdschrift beschrijving
       Alle jaargangen van het bijbehorende tijdschrift
         Alle afleveringen van het bijbehorende jaargang
           Alle artikelen van de bijbehorende aflevering
                                       Details van artikel 1 van 18 gevonden artikelen
  Asynchronous Systems of Parallel Communicating Finite Automata
Titel: Asynchronous Systems of Parallel Communicating Finite Automata
Auteur: Vollweiler, Marcel
Verschenen in: Fundamenta informaticae
Paginering: Jaargang 136 (2015) nr. 1-2 pagina's 177-197
Jaar: 2015-02-06
Inhoud: 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.
Uitgever: IOS Press
Bronbestand: Elektronische Wetenschappelijke Tijdschriften

                             Details van artikel 1 van 18 gevonden artikelen
   volgende >>
 Koninklijke Bibliotheek - Nationale Bibliotheek van Nederland