Document Open Access Logo

On Termination for Faulty Channel Machines

Authors Patricia Bouyer, Nicolas Markey, Joël Ouaknine, Philippe Schnoebelen, James Worrell

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2008.1339.pdf
  • Filesize: 177 kB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • Automated Verification
  • Computational Complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get 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

Author Details

Patricia Bouyer
Nicolas Markey
Joël Ouaknine
Philippe Schnoebelen
James Worrell
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact