After the Computability in Europe 2007 Conference, several authors were invited to submit papers that continue their work presented at the conference for special issues of some journals. You can find below brief presentations of the two such papers I co-authored, and that were acceped to appear in Theoretical Computer Science - Track C.
Two Complementary Operations Inspired by the DNA Hairpin Formation: Completion and Reduction, written together with Victor Mitrana and Takashi Yokomori.
Abstract: We consider two complementary operations: hairpin completion introduced in [D. Cheptea, C. Martin-Vide, V. Mitrana, A new operation on words suggested by DNA biochemistry: hairpin completion, in Proc. Transgressive Computing, 216--228, 2006] with motivations coming from DNA biochemistry and hairpin reduction as the inverse operation of the hairpin completion. Both operations are viewed here as formal operations on words and languages. We settle the closure properties of the classes of regular and linear context-free languages under hairpin completion in comparison with hairpin reduction. While the class of linear context-free languages is exactly the weak-code image of the class of the hairpin completion of regular languages, rather surprisingly, the weak-code image of the class of the hairpin completion of linear context-free languages is a class of mildly context-sensitive languages. The closure properties with respect to the hairpin reduction of some time and space complexity classes are also studied. We show that the factors found in the general cases are not necessary for regular and context-free languages. This part of the paper completes the results in the previously cited paper, where a similar investigation was made for hairpin completion. Finally, we briefly discuss the iterated variants of these operations.
On Small, Reduced, and Fast Universal Accepting Networks of Splicing Processors, written together with Remco Loos and Victor Mitrana.
Abstract: In this paper, we show that accepting networks of splicing processors (ANSPs) of size 2 are computationally complete. Since, by definition, an ANSP needs at least two nodes to perform non-trivial computations, this completely settles the question of designing complete ANSPs of minimal size. Also, we derive from this result the fact that all the languages in PSPACE can be accepted by ANSPs of size 2, having polynomial length complexity (the ANSP complexity measure for the space used in a computation). However, the construction that we propose, although efficient from the descriptional complexity and space complexity points of view, does not seem to have good properties from the time complexity point of view. In this respect, we prove that ANSPs of size 3 can decide all languages in NP in polynomial time. The previous lower bound on size for both completeness and efficient acceptance of NP-languages was 7. We also consider ANSPs with restricted features, proving the following normal forms: for any ANSP there exists an equivalent ANSP without input filters, and one without output filters. Finally, we show how to construct a small universal ANSP and make several considerations on the computational efficiency of universal ANSPs.
Complete versions of these papers are available upon request.
Two Complementary Operations Inspired by the DNA Hairpin Formation: Completion and Reduction, written together with Victor Mitrana and Takashi Yokomori.
Abstract: We consider two complementary operations: hairpin completion introduced in [D. Cheptea, C. Martin-Vide, V. Mitrana, A new operation on words suggested by DNA biochemistry: hairpin completion, in Proc. Transgressive Computing, 216--228, 2006] with motivations coming from DNA biochemistry and hairpin reduction as the inverse operation of the hairpin completion. Both operations are viewed here as formal operations on words and languages. We settle the closure properties of the classes of regular and linear context-free languages under hairpin completion in comparison with hairpin reduction. While the class of linear context-free languages is exactly the weak-code image of the class of the hairpin completion of regular languages, rather surprisingly, the weak-code image of the class of the hairpin completion of linear context-free languages is a class of mildly context-sensitive languages. The closure properties with respect to the hairpin reduction of some time and space complexity classes are also studied. We show that the factors found in the general cases are not necessary for regular and context-free languages. This part of the paper completes the results in the previously cited paper, where a similar investigation was made for hairpin completion. Finally, we briefly discuss the iterated variants of these operations.
On Small, Reduced, and Fast Universal Accepting Networks of Splicing Processors, written together with Remco Loos and Victor Mitrana.
Abstract: In this paper, we show that accepting networks of splicing processors (ANSPs) of size 2 are computationally complete. Since, by definition, an ANSP needs at least two nodes to perform non-trivial computations, this completely settles the question of designing complete ANSPs of minimal size. Also, we derive from this result the fact that all the languages in PSPACE can be accepted by ANSPs of size 2, having polynomial length complexity (the ANSP complexity measure for the space used in a computation). However, the construction that we propose, although efficient from the descriptional complexity and space complexity points of view, does not seem to have good properties from the time complexity point of view. In this respect, we prove that ANSPs of size 3 can decide all languages in NP in polynomial time. The previous lower bound on size for both completeness and efficient acceptance of NP-languages was 7. We also consider ANSPs with restricted features, proving the following normal forms: for any ANSP there exists an equivalent ANSP without input filters, and one without output filters. Finally, we show how to construct a small universal ANSP and make several considerations on the computational efficiency of universal ANSPs.
Complete versions of these papers are available upon request.
