nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Word Blending in Formal Languages: The Brangelina Effect

verfasst von : Srujan Kumar Enaganti, Lila Kari, Timothy Ng, Zihao Wang

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

KI-gestützte Suche

Aus

Abstract

In this paper we define and investigate a binary word operation that formalizes an experimentally observed outcome of DNA computations, performed to generate a small gene library and implemented using a DNA recombination technique called Cross-pairing Polymerase Chain Reaction (XPCR). The word blending between two words \(x w y_1\) and \(y_2 w z\) that share a non-empty overlap w, results in xwz. We study closure properties of families in the Chomsky hierarchy under word blending, language equations involving this operation, and its descriptional state complexity when applied to regular languages. Interestingly, this phenomenon has been observed independently in linguistics, under the name “blend word” or “portmanteau”, and is responsible for the creation of words in the English language such as smog (smoke + fog), labradoodle (labrador + poodle), and Brangelina (Brad + Angelina).

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 Mechanical Sequential Counting with Liquid Marbles

Nächstes Kapitel Computational Completeness of Simple Semi-conditional Insertion-Deletion Systems

Bonizzoni, P., Ferretti, C., Mauri, G., Zizza, R.: Separating some splicing models. Inf. Process. Lett. 79(6), 255–259 (2001)MathSciNetCrossRef

Bonizzoni, P., Felice, C.D., Zizza, R.: The structure of reflexive regular splicing languages via Schützenberger constants. Theor. Comput. Sci. 334(1), 71–98 (2005)CrossRef

Brzozowski, J., Kari, L., Li, B., Szykuła, M.: State complexity of overlap assembly. arXiv preprint arXiv:1710.06000 (2017)

Carausu, A., Păun, Gh.: String intersection and short concatenation. Revue Roumaine de Mathématiques Pures et Appliquées 26(5), 713–726 (1981)

Csuhaj-Varju, E., Petre, I., Vaszil, Gy.: Self-assembly of strings and languages. Theor. Comput. Sci. 374(1), 74–81 (2007)MathSciNetCrossRef

Domaratzki, M.: Minimality in template-guided recombination. Inf. Comput. 207(11), 1209–1220 (2009)MathSciNetCrossRef

Enaganti, S.K., Ibarra, O.H., Kari, L., Kopecki, S.: On the overlap assembly of strings and languages. Nat. Comput. 16(1), 175–185 (2017)MathSciNetCrossRef

Enaganti, S.K., Ibarra, O.H., Kari, L., Kopecki, S.: Further remarks on DNA overlap assembly. Inf. Comput. 253, 143–154 (2017)MathSciNetCrossRef

Franco, G.: A polymerase based algorithm for SAT. In: Coppo, M., Lodi, E., Pinna, G.M. (eds.) ICTCS 2005. LNCS, vol. 3701, pp. 237–250. Springer, Heidelberg (2005). https://doi.org/10.1007/11560586_20CrossRef

10.

Franco, G., Bellamoli, F., Lampis, S.: Experimental analysis of XPCR-based protocols. arXiv preprint arXiv:1712.05182 (2017)

11.

Franco, G., Giagulli, C., Laudanna, C., Manca, V.: DNA extraction by XPCR. In: Ferretti, C., Mauri, G., Zandron, C. (eds.) DNA 2004. LNCS, vol. 3384, pp. 104–112. Springer, Heidelberg (2005). https://doi.org/10.1007/11493785_9CrossRefMATH

12.

Franco, G., Manca, V.: Algorithmic applications of XPCR. Nat. Comput. 10(2), 805–819 (2011)MathSciNetCrossRef

13.

Franco, G., Manca, V., Giagulli, C., Laudanna, C.: DNA recombination by XPCR. In: Carbone, A., Pierce, N.A. (eds.) DNA 2005. LNCS, vol. 3892, pp. 55–66. Springer, Heidelberg (2006). https://doi.org/10.1007/11753681_5CrossRefMATH

14.

Golan, J.S.: The Theory of Semirings with Applications in Mathematics and Theoretical Computer Science. Addison-Wesley Longman Ltd., Reading (1992)MATH

15.

Goode, E., Pixton, D.: Recognizing splicing languages: syntactic monoids and simultaneous pumping. Discrete Appl. Math. 155(8), 989–1006 (2007)MathSciNetCrossRef

16.

Gries, S.T.: Shouldn’t it be breakfunch? A quantitative analysis of blend structure in English. Linguistics 42(3), 639–667 (2004)CrossRef

17.

Head, T.: Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviors. Bull. Math. Biol. 49(6), 737–759 (1987)MathSciNetCrossRef

18.

Holzer, M., Jakobi, S.: Chop operations and expressions: descriptional complexity considerations. In: Mauri, G., Leporati, A. (eds.) DLT 2011. LNCS, vol. 6795, pp. 264–275. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22321-1_23CrossRef

19.

Holzer, M., Jakobi, S.: State complexity of chop operations on unary and finite languages. In: Kutrib, M., Moreira, N., Reis, R. (eds.) DCFS 2012. LNCS, vol. 7386, pp. 169–182. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31623-4_13CrossRefMATH

20.

Holzer, M., Jakobi, S., Kutrib, M.: The chop of languages. In: Automata and Formal Languages, 13th International Conference, AFL 2011, Debrecen, pp. 197–210 (2011)

21.

Ito, M., Lischke, G.: Generalized periodicity and primitivity for words. Math. Logic Q. 53(1), 91–106 (2007)MathSciNetCrossRef

22.

Kari, L.: On language equations with invertible operations. Theor. Comput. Sci. 132(1–2), 129–150 (1994)MathSciNetCrossRef

23.

Manca, V., Franco, G.: Computing by polymerase chain reaction. Math. Biosci. 211(2), 282–298 (2008)MathSciNetCrossRef

24.

Mateescu, A., Păun, Gh., Rozenberg, G., Salomaa, A.: Simple splicing systems. Discrete Appl. Math. 84(1–3), 145–163 (1998)MathSciNetCrossRef

25.

Mateescu, A., Salomaa, A.: Handbook of Formal Languages. Springer, New York (1997)

26.

Pixton, D.: Splicing in abstract families of languages. Theor. Comput. Sci. 234, 135–166 (2000)MathSciNetCrossRef

27.

Păun, Gh.: On the splicing operation. Discrete Appl. Math. 70(1), 57–79 (1996)MathSciNetCrossRef

28.

Salomaa, A.: Formal Languages. Academic Press Inc., New York (1977)MATH

29.

Salomaa, K., Yu, S.: On the state complexity of combined operations and their estimation. Int. J. Found. Comput. Sci. 18(4), 683–698 (2007)MathSciNetCrossRef

Titel: Word Blending in Formal Languages: The Brangelina Effect
verfasst von: Srujan Kumar Enaganti
Lila Kari
Timothy Ng
Zihao Wang
Verlag: Springer International Publishing
Buch: Unconventional Computation and Natural Computation
Print ISBN: 978-3-319-92434-2

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

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-92435-9_6

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"