Vector addition tree automata
Vector addition tree automata
复制标题
向量加法树自动机
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Sylvain Salvati
中科院分区：
文献类型：
--
作者：
P. D. Groote;Bruno Guillaume;Sylvain Salvati
我们引入了一类新的自动机，我们称之为向量加法树自动机。这些自动机是具有状态的向量加法系统的自然推广，它们本身等价于Petri网。然后，我们证明了乘法指数线性逻辑的可证明性的可判定性（这是一个公开问题）等价于向量加法树自动机的可达关系的可判定性。这一结果推广了Petri网和Petri网之间的联系。乘法指数线性逻辑喇叭片段。
We introduce a new class of automata, which we call vector addition tree automata. These automata are a natural generalization of vector addition systems with states, which are themselves equivalent to Petri-nets. Then, we prove that the decidability of provability in multiplicative exponential linear logic (which is an open problem) is equivalent to the decidability of the reachability relation for vector addition tree automata. This result generalizes the well-known connection existing between Petri nets and the !-horn fragment of multiplicative exponential linear logic.