On Termination for Faulty Channel Machines
On Termination for Faulty Channel Machines
复制标题
关于故障通道机器的终止
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
J. Worrell
中科院分区：
文献类型：
--
作者：
P. Bouyer;N. Markey;Joël Ouaknine;P. Schnoebelen;J. Worrell
通道机由有限控制器和
多个FIFO通道;控制器可以从
将消息写入通道的头部，并将消息写入通道的尾部。在
在本文中，我们关注具有插入误差的通道机，
也就是说，在这些机器的通道中，信息可以自发地出现。
这种装置以前曾在公制的研究中介绍过。
时间逻辑。我们考虑终止问题：所有的
给定的插入通道机器的计算是有限的？我们表明
这个问题有非初等的，但原始的递归
复杂性
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.