10.4230/LIPICS.STACS.2008.1339
Bouyer, Patricia
Patricia
Bouyer
Markey, Nicolas
Nicolas
Markey
Ouaknine, Joël
Joël
Ouaknine
Schnoebelen, Philippe
Philippe
Schnoebelen
Worrell, James
James
Worrell
On Termination for Faulty Channel Machines
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Automated Verification
Computational Complexity
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
2008
2008-02-06
2008-02-06
2008-02-06
en
urn:nbn:de:0030-drops-13390
10.4230/LIPIcs.STACS.2008
978-3-939897-06-4
1868-8969
10.4230/LIPIcs.STACS.2008
LIPIcs, Volume 1, STACS 2008
25th International Symposium on Theoretical Aspects of Computer Science
2013
1
12
121
132
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
1
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
181649 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 1, 25th International Symposium on Theoretical Aspects of Computer Science, pages 121-132