提出病毒机器的规范化形式，揭示其计算能力边界。
Normal forms in Virus Machines
- 通过限制主机数、指令数和病毒对象数构建规范模型
- 证明了病毒机器可表征有限集、半线性集和递归可枚举集
- 为病毒计算模型提供理论分析新框架，适合理论计算机研究者
本文进一步研究病毒机器（VM）的计算能力。病毒机器是一种受病毒传播与复制网络启发的计算范式，由有向图结构的进程单元（称为宿主）及控制病毒对象在宿主间传输的指令图构成。本文通过引入正常形式，对计算模型的若干特征进行约束，包括宿主数量、指令数量以及每个宿主中病毒对象的数量。在回顾已有成果的基础上，本文提出了系列正常形式，如网络中环的规模，并由此给出了对有限集、半线性集以及递归可枚举集（NRE）等集合族的新刻画。
原文摘要 · Abstract (English)
In the present work, we further study the computational power of virus machines (VMs in short).VMs provide a computing paradigm inspired by the transmission and replication networks of viruses.VMs consist of process units (called hosts) structured by a directed graph whose arcs are called channels and an instruction graph that controls the transmissions of virus objects among hosts. The present work complements our understanding of the computing power of VMs by introducing normal forms; these expressions restrict the features in a given computing model.Some of the features that we restrict in our normal forms include (a) the number of hosts, (b) the number of instructions, and (c) the number of virus objects in each host. After we recall some known results on the computing power of VMs we give our series of normal forms, such as the size of the loops in the network, proving new characterisations of family of sets, such as finite sets, semilinear sets, or recursively enumerable sets (NRE).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。