Solving SAT by Accepting Networks of Splicing Processors with Filtered Connections

In this paper we simplify accepting networks of splicing processors considered in the paper by Manea et al. 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 coincide. Thus, the possibility of controlling the computation in...

Full description

Saved in:
Bibliographic Details
Main Authors: Castellanos, J., de Mingo Lopez, L.F., Mitrana, V.
Format: Conference Proceeding
Language:English
Subjects:
Artificial intelligence
Computer networks
Computer science
Context modeling
Filtering
Filters
Genetic mutations
Mathematics
Polynomials
Splicing
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we simplify accepting networks of splicing processors considered in the paper by Manea et al. 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 coincide. Thus, the possibility of controlling the computation in such networks is drastically diminished. In spite of this and of the fact that splicing is not a powerful operation we present here a linear time solution to a much celebrated NP-complete problem, namely SAT, based on these networks viewed as problem solvers. It is worth mentioning that the other resources (number of nodes, symbols, splicing rules, and axioms) of the networks solving instances of SAT are linearly bounded
DOI:10.1109/CIC.2006.67