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

Autor:	Sama Goliaei, Sahar Ardalan, Ayaz Isazadeh
Rok vydání:	2020
Předmět:	Spacetime Hardware and Architecture Computer science Dominating set Model of computation Graph (abstract data type) Algorithm Software Cellular automaton Theoretical Computer Science
Zdroj:	International Journal of Innovative Computing and Applications. 11:1
ISSN:	1751-6498 1751-648X
DOI:	10.1504/ijica.2020.10027029
Popis:	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:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::77086597ad954df0f603b295c91dc460 https://doi.org/10.1504/ijica.2020.10027029 Zobrazit plný text záznamu