Fresh-register automata
Fresh-register automata
复制标题
DOI：
10.1145/1926385.1926420
复制
发表时间：
2011-01
期刊：
影响因子：
--
通讯作者：
N. Tzevelekos
中科院分区：
文献类型：
--
作者：
N. Tzevelekos
名字和新名字生成的基本自动机理论模型是什么？我们引入了FRA(Fresh-Register Automata)，这是一类新的自动机，它在无限的名字字母表上操作，使用有限数量的寄存器来存储新的名字，并将传入的名字与先前存储的名字进行比较。这些有限机器扩展了卡明斯基和弗兰切斯的有限记忆自动机，因为它们能够识别全局新输入，也就是说，在整个当前运行中都是新的名字。我们从可接受语言和互模拟等价性两个方面考察了FRA的表现力。我们建立了这类自动机之间的基本性质和联系，并回答了关键的可判断性问题。作为一个示范例子，我们在FRA中表达了pi-演算的理论，并在这些自动机中用一个适当的、在有限情况下可判定的概念来刻画互模拟等价。
What is a basic automata-theoretic model of computation with names and fresh-name generation? We introduce Fresh-Register Automata (FRA), a new class of automata which operate on an infinite alphabet of names and use a finite number of registers to store fresh names, and to compare incoming names with previously stored ones. These finite machines extend Kaminski and Francez's Finite-Memory Automata by being able to recognise globally fresh inputs, that is, names fresh in the whole current run. We examine the expressivity of FRA's both from the aspect of accepted languages and of bisimulation equivalence. We establish primary properties and connections between automata of this kind, and answer key decidability questions. As a demonstrating example, we express the theory of the pi-calculus in FRA's and characterise bisimulation equivalence by an appropriate, and decidable in the finitary case, notion in these automata.