LIPIcs.STACS.2008.1339.pdf
- Filesize: 177 kB
- 12 pages
Document
On Termination for Faulty Channel Machines
Authors
-
Part of:
Volume:
25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2008-02-06
Cite AsGet BibTex
Patricia Bouyer, Nicolas Markey, Joël Ouaknine, Philippe Schnoebelen, and James Worrell. On Termination for Faulty Channel Machines. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 121-132, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.STACS.2008.1339
https://doi.org/10.4230/LIPIcs.STACS.2008.1339
Abstract
A channel machine consists of a finite controller together with
several fifo channels; the controller can read messages from the
head of a channel and write messages to the tail of a channel. In
this paper, we focus on channel machines with insertion errors,
i.e., machines in whose channels messages can spontaneously appear.
Such devices have been previously introduced in the study of Metric
Temporal Logic. We consider the termination problem: are all the
computations of a given insertion channel machine finite? We show
that this problem has non-elementary, yet primitive recursive
complexity.
Keywords
- Automated Verification
- Computational Complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads