Measuring Communication in Parallel Communicating Finite Automata
Systems of deterministic finite automata communicating by sending their states upon request are investigated, when the amount of communication is restricted. The computational power and decidability properties are studied for the case of returning centralized systems, when the number of necessary co...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2014-05-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1405.5600v1 |
| _version_ | 1818534905294880768 |
|---|---|
| author | Henning Bordihn Martin Kutrib Andreas Malcher |
| author_facet | Henning Bordihn Martin Kutrib Andreas Malcher |
| author_sort | Henning Bordihn |
| collection | DOAJ |
| description | Systems of deterministic finite automata communicating by sending their states upon request are investigated, when the amount of communication is restricted. The computational power and decidability properties are studied for the case of returning centralized systems, when the number of necessary communications during the computations of the system is bounded by a function depending on the length of the input. It is proved that an infinite hierarchy of language families exists, depending on the number of messages sent during their most economical recognitions. Moreover, several properties are shown to be not semi-decidable for the systems under consideration. |
| first_indexed | 2024-12-11T18:17:42Z |
| format | Article |
| id | doaj.art-01c3d8824797476b829de657f78bbd9e |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-11T18:17:42Z |
| publishDate | 2014-05-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-01c3d8824797476b829de657f78bbd9e2022-12-22T00:55:21ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802014-05-01151Proc. AFL 201412413810.4204/EPTCS.151.8:18Measuring Communication in Parallel Communicating Finite AutomataHenning BordihnMartin KutribAndreas MalcherSystems of deterministic finite automata communicating by sending their states upon request are investigated, when the amount of communication is restricted. The computational power and decidability properties are studied for the case of returning centralized systems, when the number of necessary communications during the computations of the system is bounded by a function depending on the length of the input. It is proved that an infinite hierarchy of language families exists, depending on the number of messages sent during their most economical recognitions. Moreover, several properties are shown to be not semi-decidable for the systems under consideration.http://arxiv.org/pdf/1405.5600v1 |
| spellingShingle | Henning Bordihn Martin Kutrib Andreas Malcher Measuring Communication in Parallel Communicating Finite Automata Electronic Proceedings in Theoretical Computer Science |
| title | Measuring Communication in Parallel Communicating Finite Automata |
| title_full | Measuring Communication in Parallel Communicating Finite Automata |
| title_fullStr | Measuring Communication in Parallel Communicating Finite Automata |
| title_full_unstemmed | Measuring Communication in Parallel Communicating Finite Automata |
| title_short | Measuring Communication in Parallel Communicating Finite Automata |
| title_sort | measuring communication in parallel communicating finite automata |
| url | http://arxiv.org/pdf/1405.5600v1 |
| work_keys_str_mv | AT henningbordihn measuringcommunicationinparallelcommunicatingfiniteautomata AT martinkutrib measuringcommunicationinparallelcommunicatingfiniteautomata AT andreasmalcher measuringcommunicationinparallelcommunicatingfiniteautomata |