DocumentCode
3282243
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
fYear
2005
fDate
25-29 Sept. 2005
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Symbolic and Numeric Algorithms for Scientific Computing, 2005. SYNASC 2005. Seventh International Symposium on
Print_ISBN
0-7695-2453-2
Type
conf
DOI
10.1109/SYNASC.2005.24
Filename
1595886
Link To Document