Skip to Main content Skip to Navigation
Journal articles

Splicing systems and the Chomsky hierarchy

Abstract : 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 splicing systems already considered in the literature.
Document type :
Journal articles
Complete list of metadata
Contributor : Isabelle Fagnot Connect in order to contact the contributor
Submitted on : Tuesday, October 2, 2012 - 5:08:53 PM
Last modification on : Friday, September 16, 2022 - 2:04:00 PM

Links full text



Jean Berstel, Luc Boasson, Isabelle Fagnot. Splicing systems and the Chomsky hierarchy. Theoretical Computer Science, Elsevier, 2012, 436 (1), pp.2-22. ⟨10.1016/j.tcs.2012.03.008⟩. ⟨hal-00737873⟩



Record views