Normal forms in Virus Machines
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912732984377344 |
|---|---|
| author | Ramírez-de-Arellano, A. Cabarle, F. G. C. Orellana-Martín, D. Pérez-Jiménez, M. J. |
| author_facet | Ramírez-de-Arellano, A. Cabarle, F. G. C. Orellana-Martín, D. Pérez-Jiménez, M. J. |
| contents | 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_03327 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Normal forms in Virus Machines Ramírez-de-Arellano, A. Cabarle, F. G. C. Orellana-Martín, D. Pérez-Jiménez, M. J. Computation and Language Formal Languages and Automata Theory 68Q07 (Primary) 68Q10, 68R01 (Secondary) F.0; F.1.1 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). |
| title | Normal forms in Virus Machines |
| topic | Computation and Language Formal Languages and Automata Theory 68Q07 (Primary) 68Q10, 68R01 (Secondary) F.0; F.1.1 |
| url | https://arxiv.org/abs/2409.03327 |