Normal forms in Virus Machines
This work is incremental, refining theoretical understanding of virus machines for researchers in computational models and bio-inspired computing.
The paper introduces normal forms for virus machines, restricting features like the number of hosts, instructions, and virus objects to characterize computational power, proving new results for families of sets such as finite, semilinear, and recursively enumerable sets.
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).