| Autor: |
Ardalan, Sahar, Goliaei, Sama, Isazadeh, Ayaz |
| Zdroj: |
International Journal of Innovative Computing and Applications; 2020, Vol. 11 Issue: 1 p1-8, 8p |
| Abstrakt: |
Signal machine is an abstract geometrical model of computation, which can be viewed as a continuous space and time generalisation of cellular automata. Almost all studies that have been made are about deterministic signal machines. In spite of few studies that have been made on non-deterministic signal machines, the present paper shows their high efficiency in solving problems using a well-known combinatorial problem. We provide a method to solve the graph dominating set problem using non-deterministic signal machines. First, we show how to design a signal machine for each specific instance of the dominating set problem. Then, we propose a signal machine which solves the dominating set problem for any instance of the problem, and show how to reduce the space complexity of solution using non-determinism. |
| Databáze: |
Supplemental Index |
| Externí odkaz: |
|
