Paper Info
Title
Accepting splicing systems with permitting and forbidding words
Abstract
In this paper we propose a generalization of the accepting splicing systems introduced in Mitrana et al. (Theor Comput Sci 411:2414---2422, 2010 ). More precisely, the input word is accepted as soon as a permitting word is obtained provided that no forbidding word has been obtained so far, otherwise it is rejected. Note that in the new variant of accepting splicing system the input word is rejected if either no permitting word is ever generated (like in Mitrana et al. in Theor Comput Sci 411:2414---2422, 2010 ) or a forbidding word has been generated and no permitting word had been generated before. We investigate the computational power of the new variants of accepting splicing systems and the interrelationships among them. We show that the new condition strictly increases the computational power of accepting splicing systems. Although there are regular languages that cannot be accepted by any of the splicing systems considered 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 also show that the smallest class of languages out of the four classes defined by accepting splicing systems is strictly included in the class of context-free languages. Solutions to a few decidability problems are immediately derived from the proof of this result.
Year
DOI
Venue
2013
10.1007/s00236-012-0169-8
Acta Informatica
Keywords
Field
DocType
Computational Power, Regular Language, Empty Word, Input Word, Splice System
Discrete mathematics,Computer science,Decidability,RNA splicing,Regular language
Journal
Volume
Issue
ISSN
50
1
1432-0525
Citations 
PageRank 
References 
2
0.55
13
Authors
5
Name
Order
Citations
PageRank
Fernando Arroyo1265.82
Juan Castellanos2978.77
Jürgen Dassow3530118.27
Victor Mitrana4950119.63
José-Ramón Sánchez-Couso5113.45