Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
The Power of Analogue-Digital Machines Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Universal Matrix Insertion Grammars with Small Size

verfasst von : Henning Fernau, Lakshmanan Kuppusamy, Sergey Verlan

Erschienen in: Unconventional Computation and Natural Computation

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We study matrix insertion grammars (MIS) towards representation of recursively enumerable languages with small size. We show that pure MIS of size (3; 1, 2, 2) (i.e., having ternary matrices inserting one symbol in two symbol context) can characterize all recursively enumerable languages. This is achieved by either applying an inverse morphism and a weak coding, or a left (right) quotient with a regular language or an intersection with a regular language followed by a weak coding. The obtained results complete known results on insertion-deletion systems from DNA computing area.

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 "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

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
Vorheriges Kapitel Solving the Bin-Packing Problem by Means of Tissue P System with 2-Division
Nächstes Kapitel Deduplication on Finite Automata and Nested Duplication Systems
Literatur
1.
Benne, R. (ed.): RNA Editing: The Alteration of Protein Coding Sequences of RNA. Series in Molecular Biology. Ellis Horwood, Chichester (1993)
2.
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
3.
Fernau, H., Kuppusamy, L., Raman, I.: Descriptional complexity of graph-controlled insertion-deletion systems. In: Câmpeanu, C., Manea, F., Shallit, J. (eds.) DCFS 2016. LNCS, vol. 9777, pp. 111–125. Springer, Cham (2016). doi:10.​1007/​978-3-319-41114-9_​9 CrossRef
4.
Fernau, H., Kuppusamy, L., Raman, I.: Generative power of matrix insertion-deletion systems with context-free insertion or deletion. In: Amos, M., Condon, A. (eds.) UCNC 2016. LNCS, vol. 9726, pp. 35–48. Springer, Cham (2016). doi:10.​1007/​978-3-319-41312-9_​4
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.
Fujioka, K.: Morphic characterizations of languages in Chomsky hierarchy with insertion and locality. Inf. Comput. 209(3), 397–408 (2011)MathSciNetCrossRefMATH
7.
Fujioka, K.: Morphic characterizations with insertion systems controlled by a context of length one. Theoret. Comput. Sci. 469, 69–76 (2013)MathSciNetCrossRefMATH
8.
Galiukschov, B.S.: Semicontextual grammars (in Russian). In: Matematika Logica i Matematika Linguistika, pp. 38–50. Kalinin University (1981)
9.
Geffert, V.: Normal forms for phrase-structure grammars. RAIRO Informatique théorique et Applications/Theor. Inform. Appl. 25, 473–498 (1991)MathSciNetCrossRefMATH
10.
11.
Ivanov, S., Verlan, S.: Random context and semi-conditional insertion-deletion systems. Fundamenta Informaticae 138, 127–144 (2015)MathSciNetMATH
12.
13.
Kari, L., Păun, G., Thierrin, G., Yu, S.: At the crossroads of DNA computing, 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)
14.
15.
16.
Krassovitskiy, A.: On the power of insertion P systems of small size. In: Martínez del Amor, M.A., Orejuela-Pinedo, E.F., Păun, G., Pérez-Hurtado, I., Riscos-Núñez, A. (eds.) Seventh Brainstorming Week on Membrane Computing, vol. II, pp. 29–43. Fénix Editora, Sevilla (2009)
17.
Kuppusamy, L., Mahendran, A.: Modelling DNA and RNA secondary structures using matrix insertion-deletion systems. Int. J. Appl. Math. Comput. Sci. 26(1), 245–258 (2016)MathSciNetCrossRefMATH
18.
Marcus, M., Păun, G.: Regulated Galiukschov semicontextual grammars. Kybernetika 26(4), 316–326 (1990)MathSciNetMATH
19.
Margenstern, M., Păun, G., Rogozhin, Y., Verlan, S.: Context-free insertion-deletion systems. Theoret. Comput. Sci. 330(2), 339–348 (2005)MathSciNetCrossRefMATH
20.
Matveevici, A., Rogozhin, Y., Verlan, S.: Insertion-deletion systems with one-sided contexts. In: Durand-Lose, J., Margenstern, M. (eds.) MCU 2007. LNCS, vol. 4664, pp. 205–217. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-74593-8_​18 CrossRef
21.
Motwani, R., Panigrahy, R., Saraswat, V., Ventkatasubramanian, S.: On the decidability of accessibility problems (extended abstract). In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC, pp. 306–315. ACM (2000)
22.
Mutyam, M., Krithivasan, K., Reddy, A.S.: On characterizing recursively enumerable languages by insertion grammars. Fundamenta Informaticae 64(1–4), 317–324 (2005)MathSciNetMATH
23.
Onodera, K.: A note on homomorphic representation of recursively enumerable languages with insertion grammars. Trans. Inf. Process. Soc. Japan 44(5), 1424–1427 (2003)MathSciNet
24.
25.
Păun, G., Pérez-Jiménez, M.J., Yokomori, T.: Representations and characterizations of languages in Chomsky hierarchy by means of insertion-deletion systems. Int. J. Found. Comput. Sci. 19(4), 859–871 (2008)MathSciNetCrossRefMATH
26.
Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer, New York (1998)CrossRefMATH
27.
28.
Verlan, S.: On minimal context-free insertion-deletion systems. J. Autom. Lang. Comb. 12(1–2), 317–328 (2007)MathSciNetMATH
Metadaten
Titel
Universal Matrix Insertion Grammars with Small Size
verfasst von
Henning Fernau
Lakshmanan Kuppusamy
Sergey Verlan
Copyright-Jahr
2017
Buch
Unconventional Computation and Natural Computation

Print ISBN: 978-3-319-58186-6

Electronic ISBN: 978-3-319-58187-3

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-58187-3_14