Towards Generalised Half-Duplex Systems
| Autor: | Loïc Germerie Guizouarn, Cinzia Di Giusto, Etienne Lozes |
|---|---|
| Přispěvatelé: | Constraints and Applications (C&A), Modèles Discrets pour les Systèmes Complexes (Laboratoire I3S - MDSC), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Theoretical computer science FIFO (computing and electronics) Computer science Binary number 02 engineering and technology [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE] [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL] 03 medical and health sciences 0302 clinical medicine [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] Channel (programming) 0202 electrical engineering electronic engineering information engineering Time complexity ComputingMilieux_MISCELLANEOUS Computer Science::Information Theory [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] Finite-state machine 020207 software engineering [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation Undecidable problem Decidability Automaton Computer Science::Performance Computer Science - Distributed Parallel and Cluster Computing 030220 oncology & carcinogenesis Distributed Parallel and Cluster Computing (cs.DC) [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM] |
| Zdroj: | Electronic Proceedings in Theoretical Computer Science Electronic Proceedings in Theoretical Computer Science, EPTCS, 2021, 347, pp.22-37. ⟨10.4204/EPTCS.347.2⟩ |
| ISSN: | 2075-2180 |
| DOI: | 10.4204/EPTCS.347.2⟩ |
| Popis: | FIFO automata are finite state machines communicating through FIFO queues. They can be used for instance to model distributed protocols. Due to the unboundedness of the FIFO queues, several verification problems are undecidable for these systems. In order to model-check such systems, one may look for decidable subclasses of FIFO systems. Binary half-duplex systems are systems of two FIFO automata exchanging over a half-duplex channel. They were studied by Cece and Finkel who established the decidability in polynomial time of several properties. These authors also identified some problems in generalising half-duplex systems to multi-party communications. We introduce greedy systems, as a candidate to generalise binary half-duplex systems. We show that greedy systems retain the same good properties as binary half-duplex systems, and that, in the setting of mailbox communications, greedy systems are quite closely related to a multiparty generalisation of half-duplex systems. In Proceedings ICE 2021, arXiv:2109.14908 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|