Reversible parallel communicating finite automata systems
- We study the concept of reversibility in connection with parallel communicating systems of finite automata (PCFA in short). We define the notion of reversibility in the case of PCFA (also covering the non-deterministic case) and discuss the relationship of the reversibility of the systems and the reversibility of its components. We show that a system can be reversible with non-reversible components, and the other way around, the reversibility of the components does not necessarily imply the reversibility of the system as a whole. We also investigate the computational power of deterministic centralized reversible PCFA. We show that these very simple types of PCFA (returning or non-returning) can recognize regular languages which cannot be accepted by reversible (deterministic) finite automata, and that they can even accept languages that are not context-free. We also separate the deterministic and non-deterministic variants in the case of systems with non-returning communication. We show that there are languages accepted byWe study the concept of reversibility in connection with parallel communicating systems of finite automata (PCFA in short). We define the notion of reversibility in the case of PCFA (also covering the non-deterministic case) and discuss the relationship of the reversibility of the systems and the reversibility of its components. We show that a system can be reversible with non-reversible components, and the other way around, the reversibility of the components does not necessarily imply the reversibility of the system as a whole. We also investigate the computational power of deterministic centralized reversible PCFA. We show that these very simple types of PCFA (returning or non-returning) can recognize regular languages which cannot be accepted by reversible (deterministic) finite automata, and that they can even accept languages that are not context-free. We also separate the deterministic and non-deterministic variants in the case of systems with non-returning communication. We show that there are languages accepted by non-deterministic centralized PCFA, which cannot be recognized by any deterministic variant of the same type.…
| Verfasserangaben: | Henning BordihnORCiD, György VaszilORCiD |
|---|---|
| DOI: | https://doi.org/10.1007/s00236-021-00396-9 |
| ISSN: | 0001-5903 |
| ISSN: | 1432-0525 |
| Titel des übergeordneten Werks (Englisch): | Acta informatica |
| Verlag: | Springer |
| Verlagsort: | Berlin ; Heidelberg ; New York, NY |
| Publikationstyp: | Wissenschaftlicher Artikel |
| Sprache: | Englisch |
| Datum der Erstveröffentlichung: | 12.08.2021 |
| Erscheinungsjahr: | 2021 |
| Datum der Freischaltung: | 28.06.2023 |
| Freies Schlagwort / Tag: | Finite automata; Reversibility; Systems of parallel communicating; automata |
| Band: | 58 |
| Ausgabe: | 4 |
| Seitenanzahl: | 17 |
| Erste Seite: | 263 |
| Letzte Seite: | 279 |
| Fördernde Institution: | National Research, Development and Innovation Fund of Hungary [K 120558]; [K 16] |
| Organisationseinheiten: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science |
| DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
| Peer Review: | Referiert |
| Lizenz (Deutsch): |  CC-BY - Namensnennung 4.0 International |
