Splicing systems and the Chomsky hierarchy

DOI10.1016/j.tcs.2012.03.008zbMath1280.68115OpenAlexW1977983588MaRDI QIDQ428896

Jean Berstel, Luc Boasson, Isabelle Fagnot

Publication date: 25 June 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.008

zbMATH Keywords

Chomsky hierarchysplicing systems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

Language generating alphabetic flat splicing P systems ⋮ Array P systems and pure 2D context-free grammars with independent mode of rewriting ⋮ Rewriting P Systems with Flat-Splicing Rules ⋮ Hybrid and generalized marked systems ⋮ Unavoidable sets and circular splicing languages ⋮ Derivation languages and descriptional complexity measures of restricted flat splicing systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A characterization of (regular) circular languages generated by monotone complete splicing systems
• A characterization of regular circular languages generated by marked splicing systems
• Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors
• Regularity of splicing languages
• A modification of a substitution theorem and some necessary and sufficient conditions for sets to be context-free
• Aspects of Molecular Computing
• On the regularity of circular splicing languages: a survey and new developments

This page was built for publication: Splicing systems and the Chomsky hierarchy