nach oben

Acta Informatica

Erschienen in:

05.02.2018 | Original Article

On path-controlled insertion–deletion systems

verfasst von: Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman

Erschienen in: Acta Informatica | Ausgabe 1/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A graph-controlled insertion–deletion system is a regulated extension of an insertion–deletion system. It has several components and each component contains some insertion–deletion rules. These components are the vertices of a directed control graph. A transition is performed by any applicable rule in the current component on a string and the resultant string is then moved to the target component specified in the rule. This also describes the arcs of the control graph. Starting from an axiom in the initial component, strings thus move through the control graph. The language of the system is the set of all terminal strings collected in the final component. In this paper, we investigate a variant of the main question in this area: which combinations of size parameters (the maximum number of components, the maximal length of the insertion string, the maximal length of the left context for insertion, the maximal length of the right context for insertion; plus three similar restrictions with respect to deletion) are sufficient to maintain computational completeness of such restricted systems under the additional restriction that the (undirected) control graph is a path? Notice that these results also bear consequences for the domain of insertion–deletion P systems, improving on a number of previous results from the literature, concerning in particular the number of components (membranes) that are necessary for computational completeness results.

Vorheriger Artikel Symbolic checking of Fuzzy CTL on Fuzzy Program Graph

Nächster Artikel Petri nets are dioids: a new algebraic foundation for non-deterministic net theory

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

The shuffle operation, denoted by

https://static-content.springer.com/image/art%3A10.1007%2Fs00236-018-0312-2/MediaObjects/236_2018_312_IEq42_HTML.gif

, is defined recursively by

$$\begin{aligned} (au\sqcup \mathchoice{}{}{}{}\sqcup \,\, bv) = a(u \sqcup \mathchoice{}{}{}{}\sqcup \,\, bv) \cup b(au \sqcup \mathchoice{}{}{}{}\sqcup \,\, v) \end{aligned}$$

and $(u \sqcup \mathchoice{}{}{}{}\sqcup \,\, \lambda ) = (\lambda \sqcup \mathchoice{}{}{}{}\sqcup \,\, u) = \{u\},$ where $u,v \in \varSigma ^*$ and $a,b \in \varSigma $.

A type-0 grammar G is usually specified by a quadruple (N, T, P, S) consisting of a nonterminal alphabet N, a terminal alphabet T, a finite set of (production) rules P and a start symbol $S\in N$. Rules are written in the form $\alpha \rightarrow \beta $, $\alpha ,\beta \in (N\cup T)^*$. This defines a rewrite relation $\Rightarrow _G\subseteq (N\cup T)^*\times (N\cup T)^*$, with $u\Rightarrow _Gv$ if v is obtained from u by replacing the subword $\alpha $ by $\beta $, for some $\alpha \rightarrow \beta \in P$. The reflexive transitive closure $\Rightarrow _G^*$ can be used to define the semantics of G—the language of G—collecting all $w\in T^*$ with $S\Rightarrow _G^*w$.

Alhazov, A., Freund, R., Ivanov, S.: Length P systems. Fundam. Inform. 134(1–2), 17–38 (2014)MathSciNetMATH

Alhazov, A., Krassovitskiy, A., Rogozhin, Y., Verlan, S.: P systems with minimal insertion and deletion. Theor. Comput. Sci. 412(1–2), 136–144 (2011)MathSciNetCrossRefMATH

Benne, R. (ed.): RNA Editing: The Alteration of Protein Coding Sequences of RNA. Series in Molecular Biology. Ellis Horwood, Chichester (1993)

Biegler, F., Burrell, M.J., Daley, M.: Regulated RNA rewriting: modelling RNA editing with guided insertion. Theor. Comput. Sci. 387(2), 103–112 (2007)MathSciNetCrossRefMATH

Dassow, J., Păun, G.: Regulated Rewriting in Formal Language Theory, EATCS Monographs in Theoretical Computer Science, vol. 18. Springer, Berlin (1989)CrossRef

Fernau, H.: An essay on general grammars. J. Autom. Lang. Comb. 21, 69–92 (2016)MathSciNetMATH

Fernau, H., Kuppusamy, L.: Parikh images of matrix ins-del systems. In: Gopal, T.V., Jäger, G., Steila, S. (eds.) Theory and Applications of Models of Computation, TAMC, LNCS, vol. 10185, pp. 201–215. Springer, Berlin (2017)CrossRef

Fernau, H., Kuppusamy, L., Raman, I.: Computational completeness of path-structured graph-controlled insertion-deletion systems. In: Carayol, A., Nicaud, C. (eds.) Implementation and Application of Automata–22nd International Conference, CIAA, LNCS, vol. 10329, pp. 89–100. Springer, Berlin (2017)

Fernau, H., Kuppusamy, L., Raman, I.: Graph-controlled insertion-deletion systems generating language classes beyond linearity. In: Pighizzini, G., Câmpeanu, C. (eds.) Descriptional Complexity of Formal Systems–19th IFIP WG 102 International Conference, DCFS, LNCS, vol. 10316, pp. 128–139. Springer, Berlin (2017)CrossRef

10.

Fernau, H., Kuppusamy, L., Raman, I.: Investigations on the power of matrix insertion-deletion systems with small sizes. Natl. Comput. (accepted) (2017)

11.

Fernau, H., Kuppusamy, L., Raman, I.: On the computational completeness of graph-controlled insertion-deletion systems with binary sizes. Theor. Comput. Sci. 682, 100–121 (2017). (Special Issue on Languages and Combinatorics in Theory and Nature)MathSciNetCrossRefMATH

12.

Fernau, H., Kuppusamy, L., Raman, I.: On the generative power of graph-controlled insertion-deletion systems with small sizes. J. Autom. Lang. Comb. 22, 61–92 (2017)MathSciNetMATH

13.

Freund, R., Kogler, M., Rogozhin, Y., Verlan, S.: Graph-controlled insertion-deletion systems. In: McQuillan, I., Pighizzini, G. (eds.) Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems, DCFS, EPTCS, vol. 31, pp. 88–98 (2010)

14.

Geffert, V.: Normal forms for phrase-structure grammars. RAIRO Theor. Inform. Appl. 25, 473–498 (1991)MathSciNetCrossRefMATH

15.

Haussler, D.: Insertion languages. Inf. Sci. 31(1), 77–89 (1983)MathSciNetCrossRefMATH

16.

Ivanov, S., Verlan, S.: About one-sided one-symbol insertion-deletion P systems. In: Alhazov, A., Cojocaru, S., Gheorghe, M., Rogozhin, Y., Rozenberg, G., Salomaa, A. (eds.) Membrane Computing—14th International Conference, CMC 2013, LNCS, vol. 8340, pp. 225–237. Springer, Berlin (2014)

17.

Ivanov, S., Verlan, S.: Random context and semi-conditional insertion-deletion systems. Fundam. Inform. 138, 127–144 (2015)MathSciNetMATH

18.

Kari, L.: On insertion and deletion in formal languages. Ph.D. thesis, University of Turku, Finland (1991)

19.

Kari, L., Păun, Gh., Thierrin, G., Yu, S.: At the crossroads of DNA computing and formal languages: characterizing recursively enumerable languages using insertion-deletion systems. In: Rubin, H., Wood, D.H. (eds.) DNA Based Computers III, DIMACS Series in Discrete Mathematics and Theretical Computer Science, vol. 48, pp. 329–338 (1999)

20.

Kari, L., Thierrin, G.: Contextual insertions/deletions and computability. Inf. Comput. 131(1), 47–61 (1996)MathSciNetCrossRefMATH

21.

Krassovitskiy, A., Rogozhin, Y., Verlan, S.: Further results on insertion-deletion systems with one-sided contexts. In: Martín-Vide, C., Otto, F., Fernau, H. (eds.) Language and Automata Theory and Applications, Second International Conference, LATA, LNCS, vol. 5196, pp. 333–344. Springer, Berlin (2008)CrossRef

22.

Krassovitskiy, A., Rogozhin, Y., Verlan, S.: Computational power of insertion-deletion (P) systems with rules of size two. Natl. Comput. 10, 835–852 (2011)MathSciNetCrossRefMATH

23.

Krishna, S.N., Rama, R.: Insertion-deletion P systems. In: Jonoska, N., Seeman, N.C. (eds.) DNA Computing, 7th International Workshop on DNA-Based Computers, 2001, Revised Papers, LNCS, vol. 2340, pp. 360–370. Springer, Berlin (2002)

24.

Kuppusamy, L., Mahendran, A., Krishna, S.N.: Matrix insertion-deletion systems for bio-molecular structures. In: Natarajan, R., Ojo, A.K. (eds.) Distributed Computing and Internet Technology–7th International Conference, ICDCIT, LNCS, vol. 6536, pp. 301–312. Springer, Berlin (2011)CrossRef

25.

Kuppusamy, L., Rama, R.: On the power of tissue P systems with insertion and deletion rules. In: Pre-Proceedings of Workshop on Membrane Computing, Report RGML, vol. 28, pp. 304–318. Univ. Tarragona, Spain (2003)

26.

Marcus, S.: Contextual grammars. Revue Roumaine de Mathématiques Pures et Appliquées 14, 1525–1534 (1969)MathSciNetMATH

27.

Margenstern, M., Păun, Gh, Rogozhin, Y., Verlan, S.: Context-free insertion-deletion systems. Theor. Comput. Sci. 330(2), 339–348 (2005)MathSciNetCrossRefMATH

28.

Matveevici, A., Rogozhin, Y., Verlan, S.: Insertion-deletion systems with one-sided contexts. In: Durand-Lose, J.O., Margenstern, M. (eds.) Machines, Computations, and Universality, 5th International Conference, MCU, LNCS, vol. 4664, pp. 205–217. Springer, Berlin (2007)CrossRef

29.

Păun, Gh: Marcus Contextual Grammars, Studies in Linguistics and Philosophy, vol. 67. Kluwer Academic Publishers, Dordrecht (1997)CrossRef

30.

Păun, G.: Membrane Computing: An Introduction. Springer, Berlin (2002)CrossRefMATH

31.

Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer, Berlin (1998)CrossRefMATH

32.

Petre, I., Verlan, S.: Matrix insertion-deletion systems. Theor. Comput. Sci. 456, 80–88 (2012)MathSciNetCrossRefMATH

33.

Takahara, A., Yokomori, T.: On the computational power of insertion-deletion systems. Natl. Comput. 2(4), 321–336 (2003)MathSciNetCrossRefMATH

34.

Verlan, S.: Recent developments on insertion-deletion systems. Comput. Sci. J. Moldova 18(2), 210–245 (2010)MathSciNetMATH

Titel: On path-controlled insertion–deletion systems
verfasst von: Henning Fernau
Lakshmanan Kuppusamy
Indhumathi Raman
Publikationsdatum: 05.02.2018
Verlag: Springer Berlin Heidelberg
Erschienen in: Acta Informatica / Ausgabe 1/2019
Print ISSN: 0001-5903
Elektronische ISSN: 1432-0525
DOI: https://doi.org/10.1007/s00236-018-0312-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"