Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений

Подождите немного. Документ загружается.

11.2. Системы репликаций 491

(d, e) = (a, b), то строка-вставка будет начинаться с префикса

bca. Если (d, e) = (b, a), то она будет начинаться с самого ле-

вого вхождения a (на третьей позиции каждой порождаемой

строки) и содержать соседнее вхождение c. В обоих случаях

число вхождений a, b, c увеличивается одновременно, и значит,

мы не можем породить ранее упоминавшиеся строки из L

(γ),

(γ).

Суммируя эти леммы, мы получаем следующий результат.

Теорема 11.8. Все семейства SREP (g), g ∈ D, попарно

несравнимы, исключения составляют следующие строгие

включения и равенство:

SREP (mp) ⊂ SREP (ml), SREP (ap) ⊂ SREP (al),

SREP (t) ⊂ SREP (Mp) ⊂ SREP (M l) = SREP (aM).

Следствие 11 .3. SREP (g), g ∈ D, строго содержатся в CS.

Леммы 11.14 – 11.16 обеспечивают для языка L ⊆ V

∗

необ-

ходимые условия пр ин адл ежност и семейству SR EP (g) в тер-

минах свойств множества Париха Ψ

(L), ассоциированного с

L. Это подталкивает к более систематическому изучению для

репликационных языков как данного множества, так и множе-

ства длин length(L) = {|x| | x ∈ L}. Кроме того, в случае, когда

L по рождается детерминированным способом, вдоль последо-

вательности

. . .

при некотором γ = (V, w

, a#b) (и значит, L = L(γ) =

, w

, . . . }), можно рассмотреть функцию роста L,

growth

(n) = |w

|, n > 0.

В случае детерминированных репликационных систем изу-

чение функции роста инт ересно и не только с математической

точки зрения, поскольку это характеризует возможности си-

стемы.

Мы приведем здесь без доказательств некоторые резуль-

таты о функциях роста и множествах длин репликационных

языков различных типов. Доказательства и дополнительные

детали можно найти в [220].

492 11. И вновь о сплетении

1. Последовательность u(n) неотрицательных целых чисел яв-

ляется функцией роста для репликационной системы γ с ре-

жимом репликации t тогда и только тогда, когда u(n) — гео-

метрическая прогрессия со знаменателем 2 и первым эле-

ментом, не равным 1.

2. Последовательность u(n) неотрицательных целых чисел яв-

ляется функцией роста для репликационной системы γ с ре-

жимом репликации g, где g ∈ {Mp, Ml, aM}, тогда и только

тогда, когда u(n) имеет вид u(n) = l + 2

k, где k > 2, l > 0.

3. Последовательность u(n) неотрицательных целых чисел яв-

ляется функцией роста для репликационной системы γ с ре-

жимом репликации g, где g ∈ {mp, ml}, тогда и только то-

гда, когда u(n) — арифметическая прогрессия u(n) = l + nk

с 1 6 k < l.

4. Множество неотрицательных целых чисел N ⊆ N является

множеством длин для репликационной системы γ с режи-

мом репликации am тогда и только тогда, когда либо

(1) существуют неотрицательные целые числа l, r и k

, k

. . . k

> 2, l >

i=1

, такие, что N = {l + c

+ c

· · · + c

| c

, . . . , c

∈ N}, либо

(2) существует l ∈ N, l > 2, такое, что N = {n | n > l}.

5. Линейное множество H = {v

+ c

+ · · · + c

| c

∈ N},

где v

∈ N

, при любом i, 0 6 i 6 r, а p > 1, является

множеством Париха репликационной системы с режимом

репликации am, тогда и только тогда, когда v

i=1

и существуют s ∈ {1, 2} и j

, . . . , j

, 1 6 j

< · · · < j

6 p,

такие что для любого i, 1 6 i 6 r, v

) = · · · = v

) = 1 и,

кроме того, если s = 1, то v

) > 2.

6. Пусть γ = (V, w, a#b) — репликационная система. Тогда

множество Париха языка L, порожденного γ с режимом

репликации af, линейно, т. е. Ψ

(L) = {v

+· · ·+c

∈ N, 1 6 i 6 r} для некоторых r > 1 и v

, . . . , v

∈ N

, где

p = card(V ).

11.2. Системы репликаций 493

Таким образом, функции роста (соответственно множества

длин, множеств а Париха) простых репликационных систем,

изучавшихся выше, являются либо экспоненциальными, либо

линейными. Было бы интересно указать модели с полиноми-

альным нелинейным ростом.

11.3 Комментарии к библиографии

Ограниченные варианты операции сплетения, включая разре-

шающие и запрещающие контексты, языки-мишени, приори-

тетные условия, рассматриваются в [257] (для конечных мно-

жеств правил сплетения, как и в разделе 11.1) и далее — в [160],

где, кроме того, исследуются и регулярные множества правил.

В обеих этих работах изучается лишь неитеративное сплетение.

H-системы с самосплетением вида γ = (V, {w}, R) с од-

ной аксиомой и конечным множеством правил сплетения рас-

сматриваются в [63], где, к примеру, доказано, что такие си-

стемы порождают семейство языков, являющееся анти-AFL,

несравнимое с REG, CF , и несколькими семействами L язы-

ков. Там же установлена неразрешимость проблемы порожда-

емости контекстно-свободных языков H-системами с самоспле-

тением.

Простые репликационные системы вводятся и исследуются

в работе [219], легшей в основу раздела 11.2. Дополнительные

результаты можно найти в [222], где рассматриваются одно-

родные репликационные системы с конечным числом аксиом

степени один, радиуса один, а также репл икация как операция

с формальными языками, и в [220], посвященной порождаю-

щим возможностям и функциям роста.

Среди других работ, касающихся операции сплетения, H-

систем и смежных понятий, отметим, например, [86], где да-

ются характеризации REG, CF, RE с помощью систем Поста

и неких родственных классов расширенных H-систем.

Сплетение на графах изучается в [90].

Вариант H-систем, близкий к исходному виду операции

сплетения, введенной Хэдом, и использующий, как и в репли-

кационных системах, разрезающие правила, рассматривается в

494 11. И вновь о сплетении

[91, 100]. Здесь разрезающие правила связывают с маркерами,

которые определяют пары разр езающих схем, производящие

подходящие др уг другу концы. Две строки сначала разреза-

ются, затем фрагменты рекомбинируются, если это разрешено

соответствующими маркерами.

Проблема изучения H-систем исследуется в [167, 318]. В

[168] дается доказательство леммы о сохранении регулярности,

содержащее очень подробное построение на языке конечных ав-

томатов.

Существует родственная сплетению операция над цепочка-

ми ДНК — кроссинговер: даются две строки x, y, мы переходим

от x к y, обратно к x, и так далее, некоторое количество раз

(заданное или нет). При этом об ъединяются подслова строк x

и y , определяемые позициями прыжков из одной строки в дру-

гую. 1-сплетение — это частный случай такой операции, ко-

гда происходит лишь один прыжок от x к y. Когда количество

прыжков заранее не задано, операцию кроссинговера можно

смоделировать с п омощью итерируемого сплетения. Интерес-

ный случай возникает, когда число прыжков фиксировано за-

ранее (и места, где эти прыжки происходят, упорядочены, так

что мы объединяем подстроки, возникающие одна за другой

слева направо в x и y). Результаты, касающиеся такой опера-

ции, содержатся в [18, 152, 224].

Рекомбинация строк в качестве основн ой операции возни-

кает также в «развивающихся грамматиках» из [62].

Обзоры результатов и библиографическую информацию,

касающуюся операции сплетения, H-систем и вычисления с

помощью сплетения, можно найти в [139, 242, 245, 261, 262].

Список литературы

Сборники статей

[AMC] N. Jonoska, Gh. P˘aun, G. Rozenberg, eds. Aspects of Molecular

Computing, Lect. Notes Computer Sci., 2950, B erlin: Springer

2004.

[CBTE] Gh. P˘aun, ed. Computing with Bio-Molecules. Theory and

Experiments, Berlin: Springer, 1998.

[CTCS] Gh. P˘aun, G. Rozenberg, A. Salomaa, eds. Current Trends

in Theoretical Computer Science. Entering the 21st Century,

Singapore: World Sc ientiﬁc, 2001.

[DNA1] R. J. Lipton, E. B. Baum, eds. DNA Based Computers.

Proc. DIMACS Workshop held at Princeton Univ., Princeton,

NJ, 1995, DIMACS: Series in Discrete Math. and Theoretical

Computer Sci., 27, Providence, RI: Amer. Math. Soc., 1996.

[DNA2] E. B. Baum, L. F. Landweber, eds. DNA Based Computers.

Proc. 2nd Annual Meeting hel d at Princeton Univ., Princeton,

NJ, 1996, DIMACS: Series in Discrete Math. and Theoretical

Computer Sci., 44, Providence, RI: Amer. Math. Soc., 1998.

[DNA3] H. Rubin, D. H. Wood, eds. Proc. 3rd DIMACS Workshop

on DNA Based Computers held at the Univ. of Pennsylvania,

Philadelphia, 1997, DIMACS: Series in Discrete Math. and

Theoretical Computer Sci., 48, Providence, RI: Amer. Math.

Soc., 1999.

[DNA4] L. Kari, H. Rubin, D. H. Wood, eds. Proc. 4th DIMACS

Workshop on DNA Based Computers held at the Univ. of

Pennsylvania, Philadelphia, 1998, том 52 журнала BioSystems,

1999.

[DNA5] E. Winfree, D. K. Giﬀord, eds. Proc. 5th DIMACS Workshop

on DNA Based Computers held at the Massachusetts Institute

of Technology, Cambridge, MA, 1999, DIMACS: Series in

Discrete Math. and Theoretical Computer Sci., 54, Providence,

RI: Amer. Math. Soc., 2000.

496 Список литературы

[DNA6] A. Condon, G. Rozenb erg, eds. DNA Computing, 6th Intern.

Workshop on DNA Based Computers, Leiden, 2000, Lect. Notes

Computer Sci., 2054, Berlin: Springer, 2001.

[DNA7] N. Jonoska, N.C. Seeman, eds. DNA Computing, 7th Intern.

Workshop on DNA Based Computers, Tampa, FL, 2001, Lect.

Notes Computer Sci., 2340, Berlin: Springer, 2002.

[DNA8] M. Hagiya, A. Obuchi, eds. DNA Computing, 8th Intern.

Workshop on DNA Based Computers, Sapporo, 2002, Lect.

Notes Computer Sci., 2568, Berlin: Springer, 2003.

[DNA9] J. Chen, J. H. Reif, eds. DNA Computing, 9th Intern. Workshop

on DNA Based Computers, Madison, WI, 2003, Lect. Notes

Computer Sci., 2943, Berlin: Springer, 2004.

[EC97] IEEE Intern. Conf. on Evolutionary Computing, Indianapolis,

1997.

[FNC] W. Brauer, H. Egrig, J. Karhum¨aki, A. Salomaa, eds. Formal

and Natural Computing, Lect. Notes Computer Sci., 2300,

Berlin: Springer, 2002.

[GCB] R. Hofestadt, T. Lengauer, M. Loﬄer, D. Schomburg, eds. Proc.

German Conf. on Bioinformatics, Leipzig, 1996, Lect. Notes

Computer Sci., 1278, Berlin: Springer, 1997.

[HFL] G. Rozenberg, A. Salomaa, eds. Handbook of Formal Languages.

3 volumes. Berlin: Springer, 1997.

[INBS] IEEE Conf. on Intelligence in Neural and Biologic Systems,

Herndon-Washington, 1995.

[MCLB] C. Martin-Vide, V. Mitrana, eds. Where Mathematics,

Computer Science, Linguistics, and Biology Meet, Dordrecht:

Kluwer, 2001.

[PCB1] L. Hunter, T. E. Klein, eds. Proc. First Annual Paciﬁc Symp.

on Biocomputing, Hawaii, 1996, Singapore: World Scientiﬁc,

1996.

[PCB2] R. B. Altman, et al., eds. Proc. 2nd Paciﬁc Conf. on

Biocomputing, Hawaii, 1997, Singapore: World Scientiﬁc, 1997.

[PCB3] R. B. Altman, A. K. Dunker, L. Hunter, T. E. Klein, eds.

3rd Annual Paciﬁc Conf. on Biocomputing, Hawaii, 1998,

Singapore: World Sc ientiﬁc, 1998.

[UMC1] C. S. Calude, J. Casti, M. J. Dinneen, eds. Unconventional

Models of Computation, Berlin: Springer, 1998.

[UMC2] I. Antoniou, C. S. Calude, M. J. Dinneen, eds. Unconventional

Models of Computation, UMC’2K, Berlin: Springer 2001.

Список литературы 497

[UMC3] C. S. Calude, M. J. Dinneen, F. Peper, eds. Unconventional

Models of Computation, UMC’02, Lect. Notes in Comput. Sci.,

2509, Berlin: Springer, 2002,

Статьи, диссертации, монографии

[1] Б. С. Галюкшов. Полуконтекстуальные грамматики. Матем.

логика и матем. лингвистика, Таллинский ун-т, 1981, 38–50.

[2] L. M. Adleman. Molecular comp utation of solutions to

combinatorial problems. Science, 226 (1994), 1021–1024.

[3] L. M. Adleman. On the potential of molecular computing — reply.

Science, 268 (1995), 483–484.

[4] L. M. Adleman. On constructing a molecular compu ter. [DNA1],

1–22.

[5] L. M. Adleman. Computing with DNA. Scientiﬁc American, 279,

2 (1998), 54–61.

[6] L. M. Adleman, P. W. K. Rothemund, S. Roweis, E. Winfree. On

applying molecular computation to the Data Encryption Standard.

[DNA2], 28–48, см. также J. Computational Biology, 6 (1999), 53–

63.

[7] A. V. Aho, J. D. Ullman. The Theory of Parsing, Translation, and

Compiling. Englewood Cliﬀs: Prentice Hall, Vol. I: 1971, Vol. II:

1973 [Русский перевод: А. Ахо, Дж. Ульман. Теория синтакси-

ческого анализа, перевода и компиляции. В 2-х томах. М.: Мир,

1979].

[8] B. Alberts, et al. Molecular Biology of the Cell. 3rd ed. New York:

Garland Publishing, 1994.

[9] G. Alford. An explicit construction of a universal extended H

system. [UMC1], 108–117.

[10] M. Amos. DNA Computation. PhD Thesis, Univ. of Warwick,

Dept. of Computer Sci., 1997.

[11] M. Amos. Theoretical and experimental DNA computation. Bull.

EATCS, 67 (1999), 125–138, см. также [CTCS], 614–630.

[12] M. Amos. Theoretical and Experimental DNA Computation.

Berlin: Springer, 2004.

[13] M. Amos, et al. Practical implementation of DNA computations.

[UMC1], 1–18.

[14] M. Amos, Gh. P˘aun, G. Rozenberg, A. Salomaa. Topics in the

theory of DNA computing. Theoretical Computer Sci., 287 (2002),

3–38.

498 Список литературы

[15] E. Anderson, et al. Solution of a problem in DNA computing,

Theoretical Computer Sci., 287 (2002), 387–391.

[16] M. Arita, M. Hagiya, A. Suyama. Joining and rotating data with

molecules. [EC97], 243–248.

[17] P. Arsenics, K. Grabowski, J. J. Mulawka. Optimal sequence

design for DNA computing. Proc. 4th Polish Conf. Evolutionary

Algorithms and Global Optimization, 2000, 245–254.

[18] A. Atanasiu. On the free crossovering operation. Ann. Univ. Buc.,

Matem.-Inform. Series, 45 (1996), 3–8.

[19] C. Baio cchi. Three s mall universal Turing machines. Proc.

MCU’2001 (M. Margenstern, Yu. Rogozhin, eds.), Lect. Notes

Computer Sci. 2055, Berlin: Springer, 2001, 1–10.

[20] B. Baker, R. Book. Reversal-b oun ded multipushdown machines. J.

Computer System Sci., 8 (1974), 315–332.

[21] R. Barua, J. Misra. Binary arithmetic for DNA computers. [DNA8],

124–132.

[22] E. B. Baum. A DNA associative memory potentially larger than

the brain. [DNA1], 23–28.

[23] R. Beene, ed. RNA-Editing: The Alteration of Protein Coding

Sequences of RNA. Chichester: Ellis Horwood, 1993.

[24] Y. Benenson, et al. Programmable and autonomous computing

machine made of biomolecules, Nature, 414 (2001), 430–434.

[25] Y. Benenson, et al. DNA molecule provides a computing machine

with both data and fuel. Proc. National Acad. Sci. USA, 100

(2003), 2191–2196.

[26] A. J. Blumberg. Parallel computation on a DNA substrate.

[DNA3], 275–289.

[27] D. Boneh, C. Dunworth, R. J. Lipton. Breaking DES using a

molecular computing. [DNA1], 37–66.

[28] D. Boneh, C. Dunworth, R. J. Lipton, J. Sgall. On the

computational power of DNA. Discrete Appl. Math., 71 (1996),

79–94.

[29] P. Bonizzoni, C. de Felice, G. Mauri, R. Zizza. DNA and circular

splicing. [DNA6], 117–129.

[30] P. Bonizzoni, G. Mauri, C. Ferretti, R. Zizza. Separating some

splicing models. Inform. Processing Letters, 76 (2001), 255–259.

[31] R. S . Braich, et al. Solution of a satisﬁability problem on a gel-

based DNA computer. [DNA6], 27–42.

[32] F. J. Brandenburg. Representations of language families by

homomorphic equality operations and generalized equality sets.

Theoretical Computer Sci., 55 (1987), 183–263.

Список литературы 499

[33] A. Brenneman, A. Condon. Strand design for bio-molecular

computation. Theoretical Computer Sci., 287 (2002), 39–58.

[34] C. Calude, J. Hromkovic. Complexity: A language-theoretic point

of view. [HFL], Vol. 2, 1–60.

[35] C. Calude, Gh. P˘aun. Global syntax and semantics for recursively

enumerable languages. Fundamenta Informaticae, 4 (1981), 245–

254.

[36] J. Castellanos, C. Martin-Vide, V. Mitrana, J. Sempere. Solving

NP-complete problems with networks of evolutionary processors.

Proc. 6th Intern. Work-Conf. Artiﬁcial and Natural Neural

Networks, IWANN’2001 (J. Mira, A. Prieto, eds.), Lect. Notes

Computer Sci., 2048, Berlin: Springer, 2001, 621–628.

[37] V. T. Chakaravarthy, K. Krithivasan. A note on extended H

systems with permitting/forbidding contexts of radius one. Bull.

EATCS, 62 (1997), 208–213.

[38] R. Ceterchi. M arcus contextual languages and their cut-and-paste

properties, Intern. Conf. on Rough Sets and Current Trends in

Computing (L. Polkowski, A. Skowron, eds.), Var¸sovia, 1998, Lect.

Notes in AI, 1424, Berlin: Springer, 1998, 99–106.

[39] R. Ceterchi. Modeling DNA recombinant behavior with ﬁxed -point

equations, [CBTE], 340–352.

[40] J. Chen, R. J. Deaton, Y.-Zh. Wang. A DNA-based memory with

in vitro learning and associative recall. [DNA9] 145–156.

[41] J. Chen, D. H. Wood. A new DNA separation technique with low

error rate. [DNA3], 43–56.

[42] J. Chen, D. H. Wood. Computation with biomolecules, Proc.

National Acad. Sci. USA, 97 (2000), 1328–1330.

[43] K. Chen, V. Ramachandran. A space-eﬃcient randomized DNA

algorithm for k-SAT. [DNA6], 199–208.

[44] J. Collado-Vides. The search for a grammatical theory of gene

regulation is formally justiﬁed by showing the inadequacy of

context-free grammars. CABIOS, 7 (1991), 321–326.

[45] A. Condon, R. M. Corn, A. Marathe. On combinatorial DNA word

design. J. Computational Biology, 8 (2001), 201–220.

[46] M. Conrad. Information processing in molecular systems. Currents

in Modern Biology, 5 (1972), 1–14.

[47] M. Conrad. On design principles for a molecular computer, Comm.

ACM, 28 (1985), 464–480.

[48] M. Conrad. The price of programmability. The Universal Turing

Machine: A Half-Century Survey (R. Herken, ed.), Hamburg:

Kammerer & Unverzagt, 1988, 285–307.

500 Список литературы

[49] M. Conrad, K.-P. Zauner. Design for a DNA c onformational

processor. [DNA3], 290–295.

[50] E. Csuhaj-Varju, J. Dassow. On cooperating distributed grammar

systems. J. Inf. Process. Cybern., EIK, 26, 1–2 (1990), 49–63.

[51] E. Csuhaj-Varju, J. Dassow, J. Kelemen, Gh. P˘aun. Grammar

Systems. A Grammatical Approach to Distribution and

Cooperation. London: Gordon and Breach, 1994.

[52] E. Csuhaj-Varju, R. Freund, F. Wachtler. Test tube systems with

cutting/recombination operation. [PCB2].

[53] E. Csuhaj-Varju, R. Freund, L. Kari, Gh. P˘aun. DNA computing

based on splicing: universality results. [PCB1], 179–190.

[54] E. Csuhaj -Varju, L. Kari, Gh. P˘aun. Test tube distributed systems

based on splicing. Computers and AI, 15 (1996), 211–232.

[55] E. Csuhaj-Varju, J. Kelemen, Gh. P˘aun. Grammar systems with

WAVE-like communication. Computers and AI, 15 (1996), 419–

436.

[56] E. Csuhaj-Varju, V. Mitrana. Evolutionary systems: A language

generating device inspired by evolving communities of cells. Acta

Informatica, 36 (2000), 913–926.

[57] E. Csuhaj-Varju, G. Vaszil. Test tube systems with objects,

Romanian J. Inform. Sci. and Technology, 4 (2001).

[58] K. Culik II. A purely homomorphic characterization of recursively

enumerable sets. J. ACM, 26 (1979), 345–350.

[59] K. Culik II, T. Harju. Splicing semigroups of dominoes and DNA.

Discrete Appl. Math., 31 (1991), 261–277.

[60] R. Dassen, H. J. Hoogeboom, N. van Vugt. A characterization of

non-iterated splicing with regular rules. [MCLB], 319–327.

[61] J. Dassow, V. Mitrana. Splicing grammar systems. Computers and

AI, 15 (1996), 109–122.

[62] J. Dassow, V. Mitrana. Evolutionary grammars: A grammatical

model for genome evolution. [GCB], 199–209.

[63] J. Dassow, V. Mitrana. Self cross-over systems. [CBTE], 283–294.

[64] J. Dassow, V. Mitrana. On some operations suggested by genome

evolution. [PCB2], 97–108.

[65] J. Dassow, V. Mitrana, A. Salomaa. Context-free evolutionary

grammars and the structural language of nucleic acids. Biosystems,

43 (1997) 169–177.

[66] J. Dassow, Gh. P˘aun. Regulated Rewriting in Formal Language

Theory. Berlin: Springer-Verlag, 1989.