Random Context and Semi-conditional Insertion-deletion Systems
Titel:
Random Context and Semi-conditional Insertion-deletion Systems
Auteur:
Ivanov, Sergiu Verlan, Sergey
Verschenen in:
Fundamenta informaticae
Paginering:
Jaargang 138 (2015) nr. 1-2 pagina's 127-144
Jaar:
2015-04-08
Inhoud:
In this article we introduce the operations of insertion and deletion working in random context and semi-conditional modes. We show that conditional application of insertion and deletion rules strictly increases the computational power. In the case of semi-conditional insertion-deletion systems, context-free insertion and deletion rules of one symbol are sufficient to achieve computational completeness. In the random context case, our results expose asymmetry between the computational power of insertion and deletion rules: semi-conditional systems of size (2, 0, 0; 1, 1, 0) (with context-free two-symbol insertion rules, and one-symbol deletion rules with one-symbol left context) are computationally complete, while systems of size (1, 1, 0; 2, 0, 0) (and, more generally, of size (1, 1, 0; p, 1, 1)) are not.
Tijdschrift beschrijving