Accepting Networks of Evolutionary Processors with Filtered Connections

Простая страница элемента
dc.creatorDrăgoi,Cezara
dc.creatorManea,Florin
dc.creatorMitrana,Victor
dc.date2007
dc.date.accessioned2024-02-06T12:55:56Z
dc.date.available2024-02-06T12:55:56Z
dc.descriptionIn this paper we simplify a recent model of computation considered in [Margenstern et al. 2005], namely accepting network of evolutionary processors, by moving the filters from the nodes to the edges. Each edge is viewed as a two-way channel such that input and output filters, respectively, of the two nodes connected by the edge coincide. Thus, the possibility of controlling the computation in such networks seems to be diminished. In spite of this observation these simplified networks have the same computational power as accepting networks of evolutionary processors, that is they are computationally complete. As a consequence, we propose characterizations of two complexity classes, namely NP and PSPACE, in terms of accepting networks of evolutionary processors with filtered connections.
dc.formattext/html
dc.identifierhttps://doi.org/10.3217/jucs-013-11-1598
dc.identifierhttps://lib.jucs.org/article/28884/
dc.identifier.urihttps://openrepository.mephi.ru/handle/123456789/9526
dc.languageen
dc.publisherJournal of Universal Computer Science
dc.relationinfo:eu-repo/semantics/altIdentifier/eissn/0948-6968
dc.relationinfo:eu-repo/semantics/altIdentifier/pissn/0948-695X
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rightsJ.UCS License
dc.sourceJUCS - Journal of Universal Computer Science 13(11): 1598-1614
dc.subjectevolutionary processor
dc.subjectnetwork of evolutionary processors
dc.subjectTuring machine
dc.subjectcomplexity class
dc.titleAccepting Networks of Evolutionary Processors with Filtered Connections
dc.typeResearch Article
Файлы
Коллекции