Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Completely Reachable Automata Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems

Authors : Henning Fernau, Lakshmanan Kuppusamy, Indhumathi Raman

Published in: Descriptional Complexity of Formal Systems

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We consider graph-controlled insertion-deletion systems and prove that the systems with sizes (i) (3; 1, 1, 1; 1, 0, 1), (ii) \((3;1,1,1;1,1,0)\) and (iii) (2; 2, 0, 0; 1, 1, 1) are computationally complete. Moreover, graph-controlled insertion-deletion systems simulate linear languages with sizes (2; 2, 0, 1, 1, 0, 0), (2; 2, 1, 0; 1, 0, 0), (3; 1, 0, 1; 1, 0, 0), or (3; 1, 1, 0; 1, 0, 0). Simulations of metalinear languages are also studied. The parameters in the size \((k;n,i',i'';m,j',j'')\) of a graph-controlled insertion-deletion system denote (from left to right) 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; a similar list of three parameters concerning deletion follows.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Contextual Array Grammars with Matrix and Regular Control
next chapter Operations on Weakly Recognizing Morphisms
Literature
1.
Alhazov, A., Krassovitskiy, A., Rogozhin, Y., Verlan, S.: P systems with minimal insertion and deletion. Theoret. Comput. Sci. 412(1–2), 136–144 (2011)MathSciNetCrossRefMATH
2.
Benne, R. (ed.): RNA Editing: The Alteration of Protein Coding Sequences of RNA. Series in Molecular Biology. Ellis Horwood, Chichester (1993)
3.
Biegler, F., Burrell, M.J., Daley, M.: Regulated RNA rewriting: modelling RNA editing with guided insertion. Theoret. Comput. Sci. 387(2), 103–112 (2007)MathSciNetCrossRefMATH
4.
Chomsky, N., Schützenberger, M.P.: The Algebraic Theory of Context-Free Languages. Studies in Logic and the Foundations of Mathematics, pp. 118–161. North-Holland, Amsterdam (1970)
5.
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)
6.
Geffert, V.: How to generate languages using only two pairs of parentheses. J. Inf. Process. Cybern. EIK 27(5/6), 303–315 (1991)MATH
7.
8.
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.) CMC 2013. LNCS, vol. 8340, pp. 225–237. Springer, Heidelberg (2014)CrossRef
9.
Ivanov, S., Verlan, S.: Universality of graph-controlled leftist insertion-deletion systems with two states. In: Durand-Lose, J., Nagy, B. (eds.) Machines, Computations, and Universality - 7th International Conference, MCU. LNCS, vol. 9288, pp. 79–93. Springer, Switzerland (2015)CrossRef
10.
Kari, L.: On insertion and deletion in formal languages. Ph.D. thesis, University of Turku, Finland (1991)
11.
12.
Krassovitskiy, A., Rogozhin, Y., Verlan, S.: Computational power of insertion-deletion (P) systems with rules of size two. Nat. Comput. 10, 835–852 (2011)MathSciNetCrossRefMATH
13.
Kuppusamy, L., Mahendran, A., Krishna, S.N.: Matrix insertion-deletion systems for bio-molecular structures. In: Natarajan, R., Ojo, A. (eds.) ICDCIT 2011. LNCS, vol. 6536, pp. 301–312. Springer, Heidelberg (2011)CrossRef
14.
Kuppusamy, L., Rama, R.: On the power of tissue P systems with insertion and deletion rules. Pre-Proceedings of Workshop on Membrane Computing. Report RGML, vol. 28, pp. 304–318. Univ. Tarragona, Spain (2003)
15.
Kutrib, M., Malcher, A.: Finite turns and the regular closure of linear context-free languages. Discrete Appl. Math. 155(16), 2152–2164 (2007)MathSciNetCrossRefMATH
16.
Margenstern, M., Păun, G., Rogozhin, Y., Verlan, S.: Context-free insertion-deletion systems. Theoret. Comput. Sci. 330(2), 339–348 (2005)MathSciNetCrossRefMATH
17.
18.
Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer, Heidelberg (1998)CrossRefMATH
19.
20.
Verlan, S.: Recent developments on insertion-deletion systems. Comput. Sci. J. Moldova 18(2), 210–245 (2010)MathSciNetMATH
Metadata
Title
Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems
Authors
Henning Fernau
Lakshmanan Kuppusamy
Indhumathi Raman
Copyright Year
2016
Book
Descriptional Complexity of Formal Systems

Print ISBN: 978-3-319-41113-2

Electronic ISBN: 978-3-319-41114-9

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-41114-9_9

Premium Partner

    Image Credits