Splicing systems and the Chomsky hierarchy

DOI10.1016/J.TCS.2012.03.008MaRDI QIDQ428896zbMATHOpenAlexFDO

Authors 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)

Recommendations

• On the power of circular splicing
• On the power of the splicing operation¹
• Marked Systems and Circular Splicing
• Deciding whether a regular language is generated by a splicing system
• Deciding whether a regular language is generated by a splicing system

Cites work

• scientific article; zbMATH DE number 3845078 (Why is no real title available?)
• scientific article; zbMATH DE number 176945 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1236223 (Why is no real title available?)
• scientific article; zbMATH DE number 1948488 (Why is no real title available?)
• scientific article; zbMATH DE number 1738645 (Why is no real title available?)
• A characterization of (regular) circular languages generated by monotone complete splicing systems
• A characterization of regular circular languages generated by marked splicing systems
• A modification of a substitution theorem and some necessary and sufficient conditions for sets to be context-free
• An algebraic characterization of semi-simple splicing
• Aspects of Molecular Computing
• Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors
• On the regularity of circular splicing languages: a survey and new developments
• Regularity of splicing languages

Cited in

(11)

• Rewriting P systems with flat-splicing rules
• Language generating alphabetic flat splicing P systems
• Derivation languages and descriptional complexity measures of restricted flat splicing systems
• Array P systems and pure 2D context-free grammars with independent mode of rewriting
• DESCRIPTIONAL COMPLEXITY OF SPLICING SYSTEMS
• Hybrid and generalized marked systems
• Complexity Theory for Splicing Systems
• Descriptional Complexity of Semi-Simple Splicing Systems
• On derivation languages of a class of splicing systems
• scientific article; zbMATH DE number 1953224 (Why is no real title available?)
• Unavoidable sets and circular splicing languages

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q428896)