Here we continue the study of bio-Turing machines introduced in [2] and further investigated in [17]. We introduce a restricted model of bio-Turingmachine and we investigate its computational power, a hierarchy of languages accepted, and deterministic and nondeterministic variants. A comprehensive example illustrating the modelling power of the introduced machine ends the paper.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In this paper, we continue the study of contextual and rewriting P systems. In contextual P systems, we improve a universality result avoiding the extended feature and by using rules of small weight. In rewriting P systems, we have two (rather surprising) universality results, both of them using three membranes, for non-extended systems with replicated rewriting and with leftmost rewriting, respectively.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We consider P Systems with string objects which evolve by means of one-sided contextual rules and erasing contextual rules. The generative power of these systems with three or less than three membranes is investigated. We show that systems with three membranes characterize the family of recursively enumerable languages. When the string replication is used in one-sided contextual rules, these systems are able of solving NP-complete problems in linear time: this is exemplified with SAT and HPP.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.