nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Context-Sensitive Fusion Grammars Are Universal

verfasst von : Aaron Lye

Erschienen in: Language and Automata Theory and Applications

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Context-sensitive fusion grammars are a special case of context-dependent fusion grammars where a rule has only a single positive context condition instead of finite sets of positive and negative context conditions. They generate hypergraph languages from start hypergraphs via successive applications of context-sensitive fusion rules and multiplications of connected components, as well as a filtering mechanism to extract terminal hypergraphs from derived hypergraphs in a certain way. The application of a context-sensitive fusion rule consumes two complementarily labeled hyperedges and identifies corresponding attachment vertices provided that the context condition holds. In this paper, we show that the Post correspondence problem can be formulated very intuitively by such a grammar. Furthermore, we prove that these grammars can generate all recursively enumerable string languages (up to representation of strings as graphs) and are universal in this respect.

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 Complexity of Automatic Sequences

Nächstes Kapitel Cyclic Shift on Multi-component Grammars

1. W.l.o.g. assume \((S {:}{:}= S) \in P\) such that each derivation is of length \(\ge 2\).

2. For technical reasons each word contains the derivation twice, the middle is separated by cc, \(w_{n+1}\) is separated by ccc, the first is in reverse order and the second is reversed. This yields \(w_ncw_{n-1}c\ldots cw_2cw_1cc r(w_2)cr(w_3)c\ldots cr(w_n)cccr(w_{n+1}).\) String in \(L_P\) are of the form \(d = (w_n c w_{n-1} c\ldots c w_2 c w_1 cc r(w_2) c \ldots c r(w_n) ccc r(w_{n+1})),\) where \(n \ge 2, w_i \mathop {\rightarrow }\limits w_{i+1}\) in G and \(w_{n+1} \in T^*\); and strings in \(L_=\) are of the form \(z = (z_m c\ldots c z_2 c S cc r(z_2) c \ldots c r(z_m) ccc)\), where \(z_i \in (N \cup T)^*\). Therefore, \(d = zz'\) for some \(z'\) if and only if \(n=m+1, S = w_1, z_i = w_i\) for \(i=1,\ldots ,m\) and \(z' = r(w_{n+1})\). Consequently, \(r(w) = r(w_{n+1}) = r(y_{n}) r(v_{n}) r(x_{n}) \in L_=\backslash L_P.\)

Applying first \( fr (A)\) with \(A \in \{Y_0,Y_1\}\) and then \(A \in \{X_0,X_1,X_2,X_3\}\) is arbitrary. The rules may be applied in any order.

For the case of two context-free fusion rules see [2]; for the case involving reduce see Lemma 2. All multiplications can be done initially (using the same argument as in [2]).

Adleman, L.M.: Molecular computation of solutions to combinatorial problems. Science 266, 1021–1024 (1994)CrossRef

Kreowski, H.-J., Kuske, S., Lye, A.: Fusion grammars: a novel approach to the generation of graph languages. In: de Lara, J., Plump, D. (eds.) ICGT 2017. LNCS, vol. 10373, pp. 90–105. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-61470-0_6CrossRefMATH

Kreowski, H.-J., Kuske, S., Lye, A.: Relating DNA computing and splitting/fusion grammars. In: Guerra, E., Orejas, F. (eds.) ICGT 2019. LNCS, vol. 11629, pp. 159–174. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-23611-3_10CrossRefMATH

Kreowski, H.-J., Kuske, S., Lye, A.: Transformation of petri nets into context-dependent fusion grammars. In: Martín-Vide, C., Okhotin, A., Shapira, D. (eds.) LATA 2019. LNCS, vol. 11417, pp. 246–258. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-13435-8_18CrossRefMATH

Lye, A.: Transformation of turing machines into context-dependent fusion grammars. In: Post-Proceedings of 10th International Workshop on Graph Computation Models, (GCM 2019). Electronic Proceedings in Theoretical Computer Science (EPTCS) (2019). https://doi.org/10.4204/EPTCS

Post, E.L.: A variant of a recursively unsolvable problem. Bull. Am. Math. Soc. 52, 264–269 (1946). https://doi.org/10.1090/s0002-9904-1946-08555-9MathSciNetCrossRefMATH

Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing – New Computing Paradigms. Springer, Heidelberg (1998). https://doi.org/10.1007/978-3-662-03563-4CrossRefMATH

Titel: Context-Sensitive Fusion Grammars Are Universal
verfasst von: Aaron Lye
Verlag: Springer International Publishing
Buch: Language and Automata Theory and Applications
Print ISBN: 978-3-030-40607-3

Electronic ISBN: 978-3-030-40608-0

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-40608-0_19

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

Springer Professional "Wirtschaft"

Premium Partner