Top

Published in:

2020 | OriginalPaper | Chapter

Context-Sensitive Fusion Grammars Are Universal

Author : Aaron Lye

Published in: Language and Automata Theory and Applications

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

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.

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

next chapter 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

Title: Context-Sensitive Fusion Grammars Are Universal
Author: Aaron Lye
Publisher: Springer International Publishing
Book: Language and Automata Theory and Applications
Print ISBN: 978-3-030-40607-3

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

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

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner