Title :
Characterizing tractability with membrane creation
Author :
Gutierréz-Naranjo, Miguel A. ; Jiménez, Mario J Pérez ; Nùnez, Agustín Riscos ; Campero, Francisco J Romero
Author_Institution :
Dept. Comput. Sci. & Artificial Intelligence, Sevilla Univ., Spain
Abstract :
This paper analyzes the role that membrane dissolution rules play in order to characterize (in the framework of recognizer P systems with membrane creation) the tractability of decision problems - that is, the efficient solvability of problems by deterministic Turing machines. In this context, the use or not of these rules provides an interesting borderline between the tractability and the (presumable) intractability.
Keywords :
Turing machines; biocomputing; computability; deterministic Turing machines; membrane creation; membrane dissolution rules; recognizer P systems; solvability; tractability; Artificial intelligence; Bibliographies; Biology computing; Biomembranes; Character recognition; Computational modeling; Computer science; NP-complete problem; Skin; Turing machines;
Conference_Titel :
Symbolic and Numeric Algorithms for Scientific Computing, 2005. SYNASC 2005. Seventh International Symposium on
Print_ISBN :
0-7695-2453-2
DOI :
10.1109/SYNASC.2005.24
