论文标题
在扁平的频道机器上
On flat lossy channel machines
论文作者
论文摘要
我们表明，对于扁平的有损通道机，即控制图中没有嵌套周期，可及性，重复达到性能，不终端和无界度对于有损耗的通道机而言。上部复杂性结合依赖于对有损通道动作的迭代的精细分析，并使用压缩单词技术进行有效的推理，并具有指数长度的路径。下限已经适用于无环或单路径机。
We show that reachability, repeated reachability, nontermination and unboundedness are NP-complete for Lossy Channel Machines that are flat, i.e., with no nested cycles in the control graph. The upper complexity bound relies on a fine analysis of iterations of lossy channel actions and uses compressed word techniques for efficiently reasoning with paths of exponential lengths. The lower bounds already apply to acyclic or single-path machines.
