Title: Evaluating non-deterministic signal machine relative complexity: a case study on dominating set problem

Authors: Sahar Ardalan; Sama Goliaei; Ayaz Isazadeh

Addresses: University of Tabriz, 29 Bahman Blvd, Tabriz, Iran ' University of Tehran, Kargar St, North Amirabad, Tehran, Iran ' University of Tabriz, 29 Bahman Blvd, Tabriz, Iran

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.

Keywords: abstract geometrical computation; non-deterministic signal machines; dominating set problem; computational model.

DOI: 10.1504/IJICA.2020.105311

International Journal of Innovative Computing and Applications, 2020 Vol.11 No.1, pp.1 - 8

Received: 05 Oct 2018
Accepted: 13 May 2019
Published online: 24 Feb 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article