2026-07-22T21:49:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1339 2024-03-06T10:32:57Z ddc:004 open_access

On Termination for Faulty Channel Machines Bouyer, Patricia Markey, Nicolas Ouaknine, Joël Schnoebelen, Philippe Worrell, James Automated Verification Computational Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Patricia Bouyer and Nicolas Markey and Joël Ouaknine and Philippe Schnoebelen and James Worrell 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1339 urn:nbn:de:0030-drops-13390 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1339 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode