Splicing systems and the Chomsky hierarchy

Details Splicing systems and the Chomsky hierarchy Splicing systems and the Chomsky hierarchy

2011-02-04

arxiv.org/abs/1102.0947v1

Computer Science

Formal Languages and Automata Theory

Scientific paper

In this paper, we prove decidability properties and new results on the position of the family of languages generated by (circular) splicing systems within the Chomsky hierarchy. The two main results of the paper are the following. First, we show that it is decidable, given a circular splicing language and a regular language, whether they are equal. Second, we prove the language generated by an alphabetic splicing system is context-free. Alphabetic splicing systems are a generalization of simple and semi-simple splicin systems already considered in the literature.

Affiliated with

Also associated with

No associations

Rating

Splicing systems and the Chomsky hierarchy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Splicing systems and the Chomsky hierarchy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Splicing systems and the Chomsky hierarchy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-491948