Další formáty:
BibTeX
LaTeX
RIS
@article{38302, author = {Sosík, Petr and Langer, Miroslav}, article_location = {Amsterdam}, doi = {http://dx.doi.org/10.1016/j.tcs.2015.09.020}, keywords = {Membrane computing; Catalytic P system; Universal computation; Register machine}, language = {eng}, issn = {0304-3975}, journal = {Theoretical Computer Science}, title = {Small (purely) catalytic P systems simulating register machines}, volume = {623}, year = {2016} }
TY - JOUR ID - 38302 AU - Sosík, Petr - Langer, Miroslav PY - 2016 TI - Small (purely) catalytic P systems simulating register machines JF - Theoretical Computer Science VL - 623 SP - 65-74 EP - 65-74 PB - Elsevier SN - 03043975 KW - Membrane computing KW - Catalytic P system KW - Universal computation KW - Register machine N2 - The paper contributes to the topic of (purely) catalytic P systems. Catalytic P systems represent the original and likely the simplest class of membrane computing models. It is known that (purely) catalytic P systems with two (respectively three) catalysts and one membrane can simulate any Minsky register machine and, hence, they are computationally complete. However, the problem of minimal size of such a universal catalytic P system remains open for about ten years. We improve known results about small catalytic P systems simulating register machines in three different modes (generating, accepting, computing functions). Together with some specific universal register machine [7], one could eventually construct a small universal catalytic P system. As a consequence, we also improve the previous construction of a minimal catalytic P system generating a non-semilinear set, diminishing the number of necessary rules from 29 to 24. (C) 2015 Elsevier B.V. All rights reserved. ER -
SOSÍK, Petr a Miroslav LANGER. Small (purely) catalytic P systems simulating register machines. \textit{Theoretical Computer Science}. Amsterdam: Elsevier, roč.~623, s.~65-74. ISSN~0304-3975. doi:10.1016/j.tcs.2015.09.020. 2016.
|