Descriptional complexity of tissue-like P systems with cell division

TitleDescriptional complexity of tissue-like P systems with cell division
Publication TypeJournal Papers
Year of Publication2009
AuthorsDíaz-Pernil, D., Gallego-Ortiz P., Gutiérrez-Naranjo M. A., Pérez-Jiménez M. J., & Riscos-Núñez A.
Journal TitleLecture Notes in Computer Science
ISBN Number978-3-642-03744-3
PublisherSpringer Berlin / Heidelberg
Volume5715
Pages168-178
Date Published09/2009
Abstract

In this paper we address the problem of describing the complexity of the evolution of a tissue-like P system with cell division. In the computations of such systems the number of (parallel) steps is not sufficient to evaluate the complexity. Following this consideration, Sevilla Carpets were introduced as a tool to describe the space-time complexity of P systems.
Sevilla Carpets have already been used to compare two different solutions of the Subset Sum problem (both designed in the framework of P systems with active membranes) running on the same instance. In this paper we extend the comparison to the framework of tissue-like P systems with cell division.

URLhttp://www.springerlink.com/content/u40g73212807k276/
DOI10.1007/978-3-642-03745-0_21