Evaluating non-deterministic signal machine relative complexity: a case study on dominating set problem. (19th February 2020)

• Record Type: Journal Article
• Authors: Ardalan, Sahar; Goliaei, Sama; Isazadeh, Ayaz
• Is Part Of: International journal of innovative computing and applications. Volume 11:Number 1(2020)
• Page Start: 1
• Page End: 8
• Publication Date: 2020-02-19
• Subjects: abstract geometrical computation -- non-deterministic signal machines -- dominating set problem -- computational model; Evolutionary computation -- Periodicals; Neural networks (Computer science) -- Periodicals; Genetic programming (Computer science) -- Periodicals; Biologically-inspired computing -- Periodicals; Swarm intelligence -- Periodicals; Quantum computers -- Periodicals; 006.3
• Languages: English
• ISSNs: 1751-648X

Abstract

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.