id: 06049404
dt: j
an: 06049404
au: Berstel, Jean; Boasson, Luc; Fagnot, Isabelle
ti: Splicing systems and the Chomsky hierarchy.
so: Theor. Comput. Sci. 436, 2-22 (2012).
py: 2012
pu: Elsevier Science Publishers, Amsterdam
la: EN
cc: 
ut: formal languages; splicing system; Chomsky hierarchy
ci: 
li: doi:10.1016/j.tcs.2012.03.008
ab: Summary: 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 splicing systems already
    considered in the literature.
rv: