Nicolas Markey

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.

@inproceedings{stacs2008-BMOSW,
  author =              {Bouyer, Patricia and Markey, Nicolas and Ouaknine,
                         Jo{\"e}l and Schnoebelen, {\relax Ph}ilippe and
                         Worrell, James},
  title =               {On Termination for Faulty Channel Machines},
  editor =              {Albers, Susanne and Weil, Pascal},
  booktitle =           {{P}roceedings of the 25th {S}ymposium on
                         {T}heoretical {A}spects of {C}omputer {S}cience
                         ({STACS}'08)},
  acronym =             {{STACS}'08},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {1},
  pages =               {121-132},
  year =                {2008},
  month =               feb,
  doi =                 {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
                         \emph{insertion errors}, \textit{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.},
}