PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Word Blending in Formal Languages

Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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 αωγ1 and γ2ωβ that share a non-empty overlap w, results in αωβ. 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). Technically, word blending is related to the binary word operation Latin product, the crossover operation, and simple splicing. We study closure properties of the families in the Chomsky hierarchy under word blending, language equations involving this operation, and its descriptional state complexity when applied to regular languages. We also define iterated word blending and show that, for a given alphabet, there are finitely many languages that can be obtained from an initial language by iterated word blending.
Wydawca
Rocznik
Strony
151--173
Opis fizyczny
Bibliogr. 33 poz., rys.
Twórcy
  • Department of Computer Science, University of Western Ontario, Canada
autor
  • School of Computer Science, University of Waterloo, Canada
autor
  • School of Computer Science, University of Waterloo, Canada
autor
  • School of Computer Science, University of Waterloo, Canada
Bibliografia
  • [1] Franco G, Giagulli C, Laudanna C, Manca V. DNA extraction by XPCR. In: Ferretti C, Mauri G, Zandron C (eds.), Proc. DNA Computing, (DNA 10), volume 3384 of LNCS. Springer. 2005 pp. 104-112. doi:10.1007/11493785_9.
  • [2] Franco G, Manca V, Giagulli C, Laudanna C. DNA recombination by XPCR. In: Carbone A, Pierce NA (eds.), Proc. DNA Computing, (DNA 11), volume 3892 of LNCS. Springer, 2006 pp. 55-66. doi:10.1007/11753681_5.
  • [3] Franco G. A Polymerase Based Algorithm for SAT. In: Coppo M, Lodi E, Pinna GM (eds.), Proc. Italian Conference on Theoretical Computer Science, (ICTCS 2005), volume 3701 of LNCS. Springer, 2005 pp. 237-250. doi:10.1007/11560586_20.
  • [4] Franco G, Manca V. Algorithmic applications of XPCR. Natural Computing, 2011. 10(2):805-819. doi:10.1007/s11047-010-9199-8.
  • [5] Manca V, Franco G. Computing by polymerase chain reaction. Mathematical Biosciences, 2008. 211(2):282-298. doi:10.1016/j.mbs.2007.08.010.
  • [6] Franco G, Bellamoli F, Lampis S. Experimental Analysis of XPCR-based protocols. 2017. arXiv preprint arXiv:1712.05182.
  • [7] Csuhaj-Varju E, Petre I, Vaszil G. Self-assembly of strings and languages. Theoretical Computer Science, 2007. 374(1):74-81. URL https://doi.org/10.1016/j.tcs.2006.12.004.
  • [8] Brzozowski JA, Kari L, Li B, Szykuła M. State Complexity of Overlap Assembly. In: Câmpeanu C (ed.), Proc. Implementation and Application of Automata, (CIAA 2018), volume 10977 of LNCS. Springer, 2018 pp. 109-120. doi:10.1007/978-3-319-94812-6_10.
  • [9] Enaganti SK, Ibarra OH, Kari L, Kopecki S. On the overlap assembly of strings and languages. Natural Computing, 2017. 16(1):175-185. doi:10.1007/s11047-015-9538-x.
  • [10] Enaganti SK, Ibarra OH, Kari L, Kopecki S. Further remarks on DNA overlap assembly. Information and Computation, 2017. 253(1):143-154. URL https://doi.org/10.1016/j.ic.2017.01.009.
  • [11] Holzer M, Jakobi S. Chop Operations and Expressions: Descriptional Complexity Considerations. In: Mauri G, Leporati A (eds.), Proc. Developments in Language Theory, (DLT 2011), volume 6795 of LNCS. Springer, 2011 pp. 264-275. doi:10.1007/978-3-642-22321-1_23.
  • [12] Holzer M, Jakobi S. State Complexity of Chop Operations on Unary and Finite Languages. In: Kutrib M, Moreira N, Reis R (eds.), Proc. Descriptional Complexity of Formal Systems, (DCFS 2012), volume 7386 of LNCS. Springer, 2012 pp. 169-182. doi:10.1007/978-3-642-31623-4_13.
  • [13] Holzer M, Jakobi S, Kutrib M. The Chop of Languages. Theoretical Computer Science, 2017. 682:122-137. URL https://doi.org/10.1016/j.tcs.2017.02.002.
  • [14] Carausu A, Păun G. String intersection and short concatenation. Revue Roumaine de Mathématiques Pures et Appliquées, 1981. 26(5):713-726.
  • [15] Golan JS. The Theory of Semirings with Applications in Mathematics and Theoretical Computer Science. Addison-Wesley Longman Ltd., 1992. ISBN: 0582078555, 9780582078550.
  • [16] Ceterchi R. An algebraic characterization of semi-simple splicing. Fundamenta Informaticae, 2006. 72(1-2):19-25.
  • [17] Ito M, Lischke G. Generalized periodicity and primitivity for words. Mathematical Logic Quarterly, 2007. 53(1):91-106. URL https://doi.org/10.1002/malq.200610030.
  • [18] Domaratzki M. Minimality in template-guided recombination. Information and Computation, 2009. 207(11):1209-1220. URL https://doi.org/10.1016/j.ic.2009.02.009.
  • [19] Pixton D. Splicing in abstract families of languages. Theoretical Computer Science, 2000. 234(1):135-166. doi:10.1016/S0304-3975(98)00046-2.
  • [20] Păun G. On the splicing operation. Discrete Applied Mathematics, 1996. 70(1):57-79. URL https://doi.org/10.1016/0166-218X(96)00101-1.
  • [21] Bonizzoni P, De Felice C, Zizza R. The structure of reflexive regular splicing languages via Schützenberger constants. Theoretical Computer Science, 2005. 334(1):71-98. doi:10.1016/ j.tcs.2004.12.033.
  • [22] Goode E, Pixton D. Recognizing splicing languages: Syntactic monoids and simultaneous pumping. Discrete Applied Mathematics, 2007. 155(8):989-1006. URL https://doi.org/10.1016/j.dam.2006.10.006.
  • [23] Enaganti SK, Kari L, Ng T, Wang Z. Word Blending in Formal Languages: The Brangelina Effect. In: Stepney S, Verlan S (eds.), Proc. Unconventional Computation and Natural Computation, (UCNC 2018), volume 10867 of LNCS. Springer, 2018 pp. 72-85. ISBN-10:0126157505, 13:978-0126157505. doi:10.1007/978-3-319-92435-9_6.
  • [24] Gries ST. Shouldn’t it be breakfunch? A quantitative analysis of blend structure in English. Linguistics, 2004. 42(3):639-667. doi:10.1515/ling.2004.021.
  • [25] Mateescu A, Păun G, Rozenberg G, Salomaa A. Simple splicing systems. Discrete Applied Mathematics, 1998. 84(1-3):145-163. URL https://doi.org/10.1016/S0166-218X(98)00002-X.
  • [26] Head T. Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors. Bulletin of Mathematical Biology, 1987. 49(6):737-759. doi:10.1007/BF02481771.
  • [27] Daley M, Ibarra OH, Kari L. Closure and decidability properties of some language classes with respect to ciliate bio-operations. Theoretical Computer Science, 2003. 306(1-3):19-38. doi:10.1016/S0304-3975(03)00139-7.
  • [28] Salomaa A. Formal Languages. Academic Press Professional, Inc., 1977.
  • [29] Kari L. On language equations with invertible operations. Theoretical Computer Science, 1994. 132(1-2):129-150. URL https://doi.org/10.1016/0304-3975(94)90230-5.
  • [30] Kari L. On insertion and deletion in formal languages. Ph.D. thesis, University of Turku, 1993.
  • [31] Hopcroft JE, Motwani R, Ullman JD. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Longman Publishing Co., Inc., 3 edition, 2006. ISBN: 10:0321455363, 13:978-0321455369.
  • [32] Pixton D. Regularity of Splicing Languages. Discrete Applied Mathematics, 1996. 69(1-2):101-124. URL https://doi.org/10.1016/0166-218X(95)00079-7.
  • [33] Salomaa K, Yu S. On the state complexity of combined operations and their estimation. International Journal of Foundations of Computer Science, 2007. 18(4):683-698. URL https://doi.org/10.1142/S0129054107004917.
Uwagi
Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).
This research was supported by the NSERC (Natural Sciences and Engineering Research Council of Canada) Discovery Grant R2824A01, and a University of Waterloo School of Computer Science Grant to L.K.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-b0d0306f-1268-4416-a3cd-8b8d742c6871
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.