License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1339
URN: urn:nbn:de:0030-drops-13390
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1339/
Go to the corresponding LIPIcs Volume Portal

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

On Termination for Faulty Channel Machines

pdf-format:
22011.BouyerPatricia.Paper.1339.pdf (0.2 MB)

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.


BibTeX - Entry

@InProceedings{bouyer_et_al:LIPIcs:2008:1339,
  author =	{Patricia Bouyer and Nicolas Markey and Jo{\"e}l Ouaknine and Philippe Schnoebelen and James Worrell},
  title =	{{On Termination for Faulty Channel Machines}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{121--132},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1339},
  URN =		{urn:nbn:de:0030-drops-13390},
  doi =		{10.4230/LIPIcs.STACS.2008.1339},
  annote =	{Keywords: Automated Verification, Computational Complexity}
}

Keywords: Automated Verification, Computational Complexity
Collection: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI