Accepting splicing systems with permitting and forbidding words

Abstract: In this paper we propose a generalization of the accepting splicingsystems introduced in Mitrana et al. (Theor Comput Sci 411:2414?2422,2010). More precisely, the input word is accepted as soon as a permittingword is obtained provided that no forbidding word has been obtained sofar, otherwise it is rejected. Note that in the new variant of acceptingsplicing system the input word is rejected if either no permitting word isever generated (like in Mitrana et al. in Theor Comput Sci 411:2414?2422,2010) or a forbidding word has been generated and no permitting wordhad been generated before. We investigate the computational power ofthe new variants of accepting splicing systems and the interrelationshipsamong them. We show that the new condition strictly increases thecomputational power of accepting splicing systems. Although there areregular languages that cannot be accepted by any of the splicing systemsconsidered here, the new variants can accept non-regular and even non-context-free languages, a situation that is not very common in the case of(extended) finite splicing systems without additional restrictions. We alsoshow that the smallest class of languages out of the four classes definedby accepting splicing systems is strictly included in the class of context-free languages. Solutions to a few decidability problems are immediatelyderived from the proof of this result.

Genome-Wide Analysis of the Response of Dickeya dadantii 3937 to Plant Antimicrobial Peptides

Antimicrobial peptides constitute an important factor in the defense of plants against pathogens, and bacterial resistance to these peptides have previously been shown to be an important virulence factor in Dickeya dadantii, the causal agent of soft-rot disease of vegetables. In order to understand the bacterial response to antimicrobial pep- tides, a transcriptional microarray analysis was performed upon treatment with sub-lethal concentration of thionins, a widespread plant peptide. In all, 36 genes were found to be overexpressed, and were classified according to their deduced function as i) transcriptional regulators, ii) transport, and iii) modification of the bacterial membrane. One gene encoding a uricase was found to be repressed. The majority of these genes are known to be under the control of the PhoP/PhoQ system. Five genes representing the different functions induced were selected for further analysis. The results obtained indicate that the presence of antimicrobial peptides induces a complex response which includes peptide-specific elements and general stress-response elements contributing differentially to the virulence in different hosts.

Splicing Systems: Accepting Versus Generating.

In this paper we propose a condition for rejecting the input word by an accepting splicing system which is defined by a finite set of forbidding words. We investigate the computational power of the new variants of accepting splicing systems. We show that the new condition strictly increases the computational power of accepting splicing systems. Rather surprisingly, accepting splicing systems considered here can accept non-regular languages, a situation that has never occurred in the case of (extended) finite splicing systems without additional restrictions.

Rule Representation in Distributed Environments with Accepting Networks of Splicing Processors.

This paper presents the model named Accepting Networks of Evolutionary Processors as NP-problem solver inspired in the biological DNA operations. A processor has a rules set, splicing rules in this model,an object multiset and a filters set. Rules can be applied in parallel since there exists a large number of copies of objects in the multiset. Processors can form a graph in order to solve a given problem. This paper shows the network configuration in order to solve the SAT problem using linear resources and time. A rule representation arquitecture in distributed environments can be easily implemented using these networks of processors, such as decision support systems, as shown in the paper.