.png){kind=icon}
返回
Reversible Two-Party Computations
.png){kind=icon}
PRE
AI
DOI：10.1142/S0129054125460050.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
确定性同步系统由两个有限自动机组成，它们在共享的只读输入上反向运行，并研究其执行可逆计算的能力。这意味着自动机也是逆向确定性的，因此能够唯一地来回推进计算步骤。我们研究了此类设备的计算能力，并发现一方面存在某些正则语言无法被此类系统接受；另一方面，此类系统甚至可以接受非半线性语言。由于系统通过发送消息进行通信，我们还考虑了在计算过程中对发送消息数量进行限制的系统。我们获得了关于可逆类中允许通信量的有限层次结构，并将其与一般（不一定是可逆的）类进行了区分。最后，我们研究了封闭性质和可判定性问题，并发现如果允许超对数规模的通信量，空集性、有限性、包含性和等价性等问题均不可半判定。
Keyword:
Watson-Crick automata
reversible computation
limited communication
computational capacity
closure properties
decidability of formal language problems
