Time-Free Solution for QSAT by Using Timed Tissue P Systems

Yun Yun Niu; Zhi Gao Wang

doi:10.4028/www.scientific.net/AMM.568-570.812

Paper Titles

Introducing Genetic Algorithm as an Intelligent Optimization Technique
p.793

Research of Association Rules Algorithm Based on Matrix under Cloud Computing
p.798

Semi-Uniform Solution for Common Algorithmic Problem by P System in the Minimally Parallel Mode
p.802

The Research of Algorithm of Optimum Route Calculation in Express Traffic System Based on Time Measure
p.807

Time-Free Solution for QSAT by Using Timed Tissue P Systems
p.812

Research on the GPS Elevation Fitting with RBF Neural Network Model Considering Effects of Sample Data Preprocessing
p.817

A Survey of Quantum Genetic Algorithm for Combinatorial Optimization Problems
p.822

The Study on User Model Construction Method Based on Ontology
p.827

Based on Data Fusion Intelligent Traffic Information Analysis and Optimization
p.831

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 568-570Time-Free Solution for QSAT by Using Timed Tissue...

Time-Free Solution for QSAT by Using Timed Tissue P Systems

Abstract:

A timed tissue P system is constructed by adding a time mapping to the rules of tissue P system to specify the execution time for each rule. It is a more realistic model from a biological point of view. In this study, we investigate the computational efficiency of timed tissue P systems. A uniform and time-free solution to QSAT problem, a famous PSPACE-complete problem, is proposed, where the execution time of the computational processes involved can vary arbitrarily and the output produced is always the same.

You might also be interested in these eBooks

Measurement Technology and its Application III

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 568-570)

Pages:

812-816

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.568-570.812

Citation:

Cite this paper

Online since:

June 2014

Authors:

Yun Yun Niu*, Zhi Gao Wang

Keywords:

Membrane Computing, PSPACE-Complete Problem, QSAT, Time-Free Solution, Tissue p System

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] Gh. Păun: Journal of Computer and System Sciences Vol. 61(1) (2001), pp.108-143.

Google Scholar

[2] C. Martín Vide, J. Pazos, Gh. Păun and A. Rodíguez Patón: Theoretical Computer Science Vol. 296 (2003), pp.295-326.

DOI: 10.1016/s0304-3975(02)00659-x

Google Scholar

[3] Gh. Păun, M.J. Pérez-Jiménez and A. Riscos-Núñez: Int. J. of Computers, Communications and Control Vol. 3(3) (2008), pp.295-303.

Google Scholar

[4] D. Díaz-Pernil, M.A. Gutérrez-Naranjo, M.J. Pérez-Jiménez, and A. Riscos-Núñez: Proc. of IWINAC 2007, LNCS 4527, pp.170-179.

Google Scholar

[5] D. Díaz-Pernil, M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, and A. Riscos-Núñez: Proc. of 6th Brainstorming Week on Membrane Computing, Report RGNC 01/08, Fenix Editoria (2008), pp.124-134.

DOI: 10.1007/978-3-540-77312-2_16

Google Scholar

[6] D. Díaz-Pernil, M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, and A. Riscos-Núñez: Electronic Notes in Theoretical Computer Science Vol. 171 (2007), pp.81-93.

DOI: 10.1016/j.entcs.2007.05.009

Google Scholar

[7] L. Pan, X. Zeng and X. Zhang: Neural Computation Vol. 23 (2011), pp.1320-1342.

Google Scholar

[8] C. Matteo: In Proceeding of Tenth Brainstorming Week on Membrane Computing Vol. 1 (2012), pp.204-210.

Google Scholar

[9] T. Song, H. Zheng, J. He and L. Zhang: Journal of Applied Mathematics, Vol. 2013, Article ID 975798, 7 pages, doi: 10. 1155/2013/975798.

Google Scholar