Loading...
Please wait, while we are loading the content...
Similar Documents
Networks of Uniform Splicing Processors: Computational Power and Simulation
| Content Provider | MDPI |
|---|---|
| Author | Sandra, Gómez-Canaval Mihaela, Păun Jos, é Angel Sanchez Martín Mitrana, Victor Couso, José Ramón Sánchez |
| Copyright Year | 2020 |
| Description | We investigated the computational power of a new variant of network of splicing processors, which simplifies the general model such that filters remain associated with nodes but the input and output filters of every node coincide. This variant, called network of uniform splicing processors, might be implemented more easily. Although the communication in the new variant seems less powerful, the new variant is sufficiently powerful to be computationally complete. Thus, nondeterministic Turing machines were simulated by networks of uniform splicing processors whose size depends linearly on the alphabet of the Turing machine. Furthermore, the simulation was time efficient. We argue that the network size can be decreased to a constant, namely six nodes. We further show that networks with only two nodes are able to simulate 2-tag systems. After these theoretical results, we discuss a possible software implementation of this model by proposing a conceptual architecture and describe all its components. |
| Starting Page | 1217 |
| e-ISSN | 22277390 |
| DOI | 10.3390/math8081217 |
| Journal | Mathematics |
| Issue Number | 8 |
| Volume Number | 8 |
| Language | English |
| Publisher | MDPI |
| Publisher Date | 2020-07-24 |
| Access Restriction | Open |
| Subject Keyword | Mathematics Hardware and Architecturee Theory of Computation Computational Models Turing Machine 2-tag System Splicing Splicing Processor Network of Uniform Splicing Processors Apache Giraph Apache Spark Spark Graphx Architecture Nsup Engine |
| Content Type | Text |
| Resource Type | Article |
