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 metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00737873
Contributor : Isabelle Fagnot <>
Submitted on : Tuesday, October 2, 2012 - 5:08:53 PM
Last modification on : Friday, March 27, 2020 - 2:55:02 AM

Links full text

Identifiers

Citation

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⟩

Share

Metrics

Record views

469