caa a22 4500 445843063 CHVBK 20180317145350.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s11047-010-9208-y doi (NATIONALLICENCE)springer-10.1007/s11047-010-9208-y Computational power of insertion-deletion (P) systems with rules of size two [Elektronische Daten] [Alexander Krassovitskiy, Yurii Rogozhin, Sergey Verlan] This article investigates insertion-deletion systems of small size, where at most two symbols can be used in the description of insertion or deletion rules in a context-free or contextual manner. The basic result shows a characterization by context-free grammars of insertion-deletion systems, which insert or delete one symbol in one symbol left context (systems of size (1, 1, 0; 1, 1, 0)). If context-free insertion or deletion rules are considered (systems of size (2, 0, 0; 1, 1, 0) or (1, 1, 0; 2, 0, 0)), then we show that corresponding systems are not computationally complete. However, if the insertion and the deletion operations having same size as above are considered in the distributed framework of P systems, then the computational power strictly increases and the obtained models become computationally complete. The article also shows that if context-free insertion and deletion rules of two symbols (of size (2, 0, 0; 2, 0, 0)) are used in combination with P systems, then the obtained model is still not computationally complete. Finally some open problems are presented. Springer Science+Business Media B.V., 2010 Insertion-deletion systems nationallicence P systems nationallicence Decidability nationallicence Universality nationallicence Computational completeness nationallicence Krassovitskiy Alexander Research Group on Mathematical Linguistics, Rovira i Virgili University, Av. Catalunya, 35, 43002, Tarragona, Spain aut Rogozhin Yurii Research Group on Mathematical Linguistics, Rovira i Virgili University, Av. Catalunya, 35, 43002, Tarragona, Spain aut Verlan Sergey LACL, Département Informatique, Université Paris Est, 61, av. Général de Gaulle, 94010, Créteil, France aut Natural Computing Springer Netherlands 10/2(2011-06-01), 835-852 1567-7818 10:2<835 2011 10 11047 https://doi.org/10.1007/s11047-010-9208-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s11047-010-9208-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Krassovitskiy Alexander Research Group on Mathematical Linguistics, Rovira i Virgili University, Av. Catalunya, 35, 43002, Tarragona, Spain aut NATIONALLICENCE 700 1- Rogozhin Yurii Research Group on Mathematical Linguistics, Rovira i Virgili University, Av. Catalunya, 35, 43002, Tarragona, Spain aut NATIONALLICENCE 700 1- Verlan Sergey LACL, Département Informatique, Université Paris Est, 61, av. Général de Gaulle, 94010, Créteil, France aut NATIONALLICENCE 773 0- Natural Computing Springer Netherlands 10/2(2011-06-01), 835-852 1567-7818 10:2<835 2011 10 11047 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer