论文标题
俯卧系统的分拟合有限是基本的
Bisimulation Finiteness of Pushdown Systems Is Elementary
论文作者
论文摘要
我们表明，如果下降系统是相当于有限系统的一分化系统的，则已经存在一个双拟合当量有限系统，其大小在俯卧撑系统的描述大小中具有基本界限。结果，我们得到的是，如果给定的下降系统与某些有限系统相等，则基本可决定。这改善了以前最著名的Ackermann上限，以解决此问题。
We show that in case a pushdown system is bisimulation equivalent to a finite system, there is already a bisimulation equivalent finite system whose size is elementarily bounded in the description size of the pushdown system. As a consequence we obtain that it is elementarily decidable if a given pushdown system is bisimulation equivalent to some finite system. This improves a previously best-known ACKERMANN upper bound for this problem.
