Derivation languages and descriptional complexity measures of restricted flat splicing systems

DOI10.1016/J.TCS.2019.10.003MaRDI QIDQ2306014zbMATH OpenOpenAlexWikidataFDO

Authors Prithwineel Paul, Kumar S. Ray

Publication date 20 March 2020

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

Full work available at URL https://arxiv.org/abs/1804.02312

zbMATH Keywords

Chomsky hierarchycontrol languageflat splicinglabeled restricted flat splicing systemsSzilard language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: In this paper, we associate the idea of derivation languages with flat splicing systems and compare the families of derivation languages (Szilard and control languages) of these systems with the family of languages in Chomsky hierarchy. We show that the family of Szilard languages of labeled flat finite splicing systems of type $(m,n)$ (i.e., $SZL{S}_{n,FIN}^m$ ) and $REG$, $CF$ and $CS$ are incomparable. Also, it is decidable whether or not $S{Z}_{n,FIN}^m(mathscrLS)subseteqR$ and $RsubseteqS{Z}_{n,FIN}^m(mathscrLS)$ for any regular language $R$ and labeled flat finite splicing system $mathscrLS$. Also, any non-empty regular, non-empty context-free and recursively enumerable language can be obtained as homomorphic image of Szilard language of the labeled flat finite splicing systems of type $(1,2),(2,2)$ and $(4,2)$ respectively. We also introduce the idea of control languages for labeled flat finite splicing systems and show that any non-empty regular and context-free language can be obtained as a control language of labeled flat finite splicing systems of type $(1,2)$ and $(2,2)$ respectively. At the end, we show that any recursively enumerable language can be obtained as a control language of labeled flat finite splicing systems of type $(4,2)$ when $lambda$-labeled rules are allowed.

Recommendations

• On derivation languages of a class of splicing systems
• On the power of the splicing operation¹
• DESCRIPTIONAL COMPLEXITY OF SPLICING SYSTEMS
• Publication:4942039
• Language generating alphabetic flat splicing P systems

Cites work

• Characterizations of recursively enumerable languages by means of insertion grammars
• Computational power of tissue P systems for generating control languages
• Control Languages Associated with Tissue P Systems
• DNA computing based on splicing: The existence of universal computers
• DNA computing based on splicing: Universality results
• scientific article; zbMATH DE number 3839343 (Why is no real title available?)
• scientific article; zbMATH DE number 1236223 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Language generating alphabetic flat splicing P systems
• On some derivation mechanisms and the complexity of their Szilard languages
• On Szilard languages of labelled insertion grammars
• Splicing semigroups of dominoes and DNA
• Splicing systems and the Chomsky hierarchy
• Splicing systems with targets are computationally universal

Cited in

(4)

• On derivation languages of a class of splicing systems
• On homomorphic images of the Szilard languages of matrix insertion-deletion systems with matrices of size 2
• Languages generated by numerical P systems with thresholds
• Descriptional Complexity of Semi-Simple Splicing Systems

This page was built for publication: Derivation languages and descriptional complexity measures of restricted flat splicing systems

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