автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Идентификация клеточных автоматов: теория и приложения

р Г 5 03

1 9 с?Л-Г} '

ИНСТИТУТ ПРОГРАММНЫХ СИСТЕМ РОССИЙСКОЙ АКАДЕМИИ НАУК

На правах рукописи

АДАМАЦКИЙ Андрей Игоревич

ИДЕНТИФИКАЦИЯ КЛЕТОЧНЫХ АВТОМАТОВ: ТЕОРИЯ И ПРИЛОЖЕНИЯ

Специальность 05.13.17. - теоретические основы информатика

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Переславль-Залесскин 1996

Работа выполнена в Санкт-Петербургском государственном университете Научный консультант:

Доктор технических наук, профессор Д.А. ПОСПЕЛОВ Официальные оппоненты:

Доктор физико-математических наук, профессор Г.С. ОСИПОВ Доктор технических наук О.П. КУЗНЕЦОВ

Доктор физико-математических наук, профессор В.Л. ДУНИН-БАРКОВСКИЙ Ведущая организация:

Московский энергетический институт, кафедра прикладной математики.

У ПЪ Ш

Защита состоится " ^ ^ 1996 года в ' часов на заседании Специализированного Совета Д200.36.01 при Институте программных систем Российской Академии Наук. Адрес: 152140, Переславль-Залесский, "Ботик".

С диссертацией можно ознакомиться в библиотеке ИПС РАН.

/

Автореферат диссертации разослан " о*- 1996 года

Учёный секретарь

диссертационного совета Д200.36.01 ИПС РАН

кандидат физ.-мат. наук ¡лС}^ / Юмагужина В.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы Клеточные автоматы являются математическими моделями естественных и технических распределенных систем, состоящих из большого числа элементов, которые локально взаимодействуют друг с другом. Такие системы характеризуются сложным глобальным поведением несмотря на крайне простые правила локальной эволюции ее элементов.

Концепция клеточно-автоматных вычислений активно используется при создании массово-параллельных высокопроизводительных вычислительных систем. Простота архитектуры элементарного процессора и локальность межпроцессорных связей делают нетривиальной задачу создания алгоритмов массово-параллельных локальных вычислений, что указывает на необходимость разработки оригинальных методик проектирования алгоритмов подобного типа.

В настоящее время интенсифицируются исследования по созданию молекулярных и нейронно-сетевых процессоров, использующих в своей работе принципы параллельной обработки информации в живых системах. Клеточные автоматы — это наиболее приемлемая математическая модель биологических вычислителей, кроме того они активно применяются при имитации разнообразных природных явлений: солитонов,. реакционно-диффузионных сред, химической турбулентности, динамики жидкостей и газа, динамики популяций, эпидемиологии, морфогенеза и т.п.

Особый интерес приобретают такие проблемы собственно теории клеточных автоматов, как предсказание эволюции, характеризация графов глобальных переходов, предельных множеств конфигураций и алгебраических систем, построенных' над клеточными автоматами, исследование тонких свойств клеточно-автоматных отображений и вычислительной мощности клеточных автоматов, взаимное моделирование классов, анализ новых классов клеточных автоматов (например, обратимые и асинхронные автоматы), сравнительный анализ клеточных автоматов и грамматик.

Исходя из вышесказанного можно заключить, что Проблема восстановления правил локальной эволюции элементов распределенной многокомпонентной системы по набору моментальных снимков ее глобальной эволюции становится крайне актуальной в плане автоматического создания математических моделей естественных систем, проектирования массово-параллельных алгоритмов и решения ряда принципиальных задач теории клеточных автоматов.

Цель и задачи исследования. Целью настоящего исследования является создание алгоритмов идентификации клеточных автомагов, т.е. вычисления минимального описания клеточного автомата по последовательности его конфигураций. Решались следующие задачи:

(1) Создать полную классификацию клеточных автоматов, построить иерархию сложности описания и взаимной м о дел пру ем о сти;

(2) Спроектировать алгоритмы идентификации клеточных автоматов для каждого из классов, оценить сложность идентификации, построить схемы параллельной идентификации;

(3) Исследовать применимость алгоритмов идентификации к восстановлению правил локальной эволюции естественных систем;

(4) Оценить применимость идеологии идентификации клеточных автоматов при проектировании массово-параллельных алгоритмов решения задач дискретной вычислительной геометрии.

Методы и объекты исследования. Исследования осуществлены на основе теории автоматов, теории кодирования, теории вероятностей и комбинаторики. Объектом исследования являются клеточные автоматы, которые представляют собой дискретные математические модели многокомпонентных естественных и искусственных систем, состоящих из большого числа относительно простых элементов, связанных между собой локально в регулярные структуры.

Клеточный автомат канонически описывается целочисленной решеткой Ь, каждый узел (клетка) х которой принимает состояния из непустого конечного множества (2 и совершает переходы из состояния в состояние в дискретные моменты времени в соответствии с функцией локальных переходов / в зависимости от состояний ближайших к соседей окрестности и в прошедший момент времени: К=(Ь, (2, и, /}, и. Ь-»ЬЛ,

/: х<«=Ди(ху).

Научная новизна. В работе впервые

(1) проведен полный сравнительный анализ всех возможных классов КА по направлениям асинхронности, нестационарности, недетерминированности и структурной вариабельности и построены иерархии принадлежности, моделируемости и сложности;

(2) доказана разрешимость задачи восстановления функции локальных переходов по набору конфигураций КА, спроектированы алгоритмы идентификации всех классов КА и вычислены оценки сложности последовательной и параллельной идентификации;

(3) построены алгебраические системы и ассоциированные матричные структуры над классами КА;

(4) предложены методы вычисления неконструируемых конфигураций;

(5) проведено практическое внедрение теоретических результатов на примерах идентификации систем движущихся объектов, нейронных сетей, морфогенетических структур, реакционно-диффузионных сред, популяций животных и растений;

(6) предложены способы идентификации эпистемических и акциональных систем распределенного интеллекта;

(7) обоснована схема автоматического проектирования молекулярных компьютеров по структуре решаемой задачи, методы проектирования протестированы на задачах вычислительной геометрии и обработки изображений.

Практическая ценность работы. Результаты работы применены при проектировании, изготовлении опытных образцов и отладке программного обеспечения одноплатного параллельного сопроцессора ЛОКОН 9В51 (НИП "Галафокс"), использованы при проведении НИР "Исследование методов решения задач и программирования (обучения) нейросетевых компьютеров" (СПбГУ, АО "Светлана"), "Исследование структурно-функциональной организации рефлексов и моделирование нейронных сетей" (СПбГУ, МИРЭА), "Исследование параллельных реконфигурируемых компьютерных архитектур для суперкристалла", "Исследование состава, функций и разработка программного обеспечения для отказоустойчивых многопроцессорных систем на суперкристалле", "Разработка к исследование архитектур и прототипа программного обеспечения многопроцессорной системы на пластине", "Исследование массово-параллельных архитектур с учетом возможностей 1.5 мкм технологии для создания сверхвысокопроизводительных систем пятого поколения", "Исследование не-фон Неймановских массово-параллельных архитектур и возможности их реализации на пластине по субмикронной технологии" в отделе Микроэлектроники КТБ АО "Светлана"

(Санкт-Петербург). По результатам работы читается годовой курс в Санкт-Петербургском государственном университете.

Публикации. По теме диссертации опубликовано 35 работ и монография 21 п.л.

Апробация работы. Материалы диссертации были представлены на Международной конференции "Приложения баз данных и микрокомпьютеров" (Йена, 1988), IX Всесоюзной конференции по нейрокибернетике (Ростов-на-Дону, 1989), Ш-м Всесоюзном рабочем совещании "Теоретические исследования и банки данных по молекулярной биологии" (Новосибирск, 1988), Международной конференции "Моделирование и компьютеры в молекулярной биологии" (Новосибирск, 1990), XI, XIII и XIV семинарах по однородным вычислительным средам и систолическим структурам (Львов, 1990, 1991, 1992), Международном симпозиуме по нейронным сетям и нейронным вычислениям (Прага, 1990), 1-й Всесоюзной конференции "Однородные вычислительные структуры" (Львов, 1990), Международной конференции "Сложные системы: фракталы, спиновые стекла и нейронные сети" (Триест, 1991), Международной конференции "Биомод'92" (Санкт-Петербург, 1992), Международном симпозиуме по нейрокибернетике и нейрокомпьютерам (Ростов-на-Дону, 1992), Н-й Международной конференции по промышленной и прикладной математике (Вашингтон, 1991).

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, приложений, заключения и списка литературы. Основной текст содержит 173 страницы, 45 таблиц и 97 рисунков. Список литературы включает 196 наименовании.

СОДЕРЖАНИЕ РАБОТЫ

Во ВВЕДЕНИИ обоснована актуальность темы диссертации, сформулирована цель работы, ее научная новизна и практическая значимость, а также дано краткое изложение ее содержания.

В ПЕРВОЙ ГЛАВЕ осуществляется классификация и строится иерархия КА.

Клеточный автомат (КА) определяется набором Л=< Ь, (3, !(,/>, где (1) Ь — ¿-мерная решетка (¿>1) из п клеток (п>2), (2) — множество состояний клеток, |{3| = д, (3) и: Г,-»!/ — окрестность клетки х еЬ (к<п, к — размер окрестности/число соседей), /:(}* -> (} — функция локальных переходов. Каждая клетка 71 изменяет свое состояние по правилу х'*1 = /(и(х)') = /(у/,...,У/. ), I . Конфигурацией (глобальным состоянием) К называется отображение Функцией

глобальных переходов К. называется отображение -»такое, что

р-(с') = с" о Ух еЬ/(м(х)') = х" для «(х)'сс', х"ес", с',с" е()". Конфигурация с называется полной, если Уи> е()' № с с; неконструируемой, если -Зс'еСЗ" = и

фиксированной, если Г (с) = с.

Детерминированные КА. Исследована взаимная моделируемость, вычислены оценки сложности и построена иерархия детерминированных КА. Определения:

(1)СЬАв (канонические): Э /(и>) =

(2)ТОТА(обобщенные): <Ь,С},и,/т,ст>, д={0,1,...//-1|, о: О* -+{0,1,...,Ш~\)}, /т:{0,1,...,*(9-1»-»0, и Ух еП хы = ^{о{и(х)')) =

(3)NSET: <L,Q,k,/n,P>, p.- Q ->2Q\{0}, /N:2Q\{0|-»Q, и V.v eLVi sN

(4) ATOT: (L,Q,u,fA,a), a: Q* -> M, M={(W...^)|Vi=0)...?-l л; eft..,/^]^*, =A},

х(У.У) = 1''У1 = "! и V* eLVieN хм = Л («(«(*)')),

10, у' *;

(5) MEMO (спамятью): <L,Q,«,/,-/>, ->Q, у>1, .t' = /(«(x)W*)M,...,"(*rr),

(6) NONSTAT (нестационарные): <L,Q,T,и,g,r), g:Q"xT-+Q, r:LxT-> L\ xm=g(r(x',t),t), T -6 N,

(7) ASYN_I (асинхронные): (L,Q,и,/,т,£>, N, x:L-> N и я„1 = Г x',T(x)'^l ,[(*)'_!, t(x)'г 1

l/M*)'), t(x)' = 0 UM*)'), t(x)' = 0'

(8) ASYN_H (асинхронные): <L,Q,!/,/,т,6,5), 5:Q" -» N, 6:LN, 0: L -> N,

[б(х)', t(x)' =0 l5(u(x)'), -t(x)' =0 [ в(х)',т(х)'=0

Обозначим S(X) сложность описания локальных переходов клеток КА класса X. Нами получены следующие оценки: (1) S(CLAS)= q*(k + l), (2) 5(ТОТА)= 2(k{q-\) + \),

, (? + 1)(2"-1) для q<k (3)S(NSET)= ф ,{4) SWOT)=f q+[>[K + 'l -.

I Ам.....(fc + <?) k\q\

Пусть А с: В для классов А и В, если для каждой конфигурации с и любой функции локальных переходов из А, которая преобразует с в d, найдется функция из В, которая преобразует с в с\ Тогда (1) TOTAcCLAS, (2) NSETcCLAS для q < к, (3)TOTAiZSET и NSETctTOTAдля <j > 2 и > 2 .

Пусть А-> В, если >0, где Nx=qk, fc(g-l) + l, 2"-1 для КА

классов CLAS, ТОТА и ISSET соответственно. Тогда: (1) TOTA->CLAS, NSETCCLAS, ТОГАNSET для постоянного к и q->°о, (2) TOTA-»CLAS, NSET->CLAS, NSET-»TOTA для постоянного q и к оо.

Вероятностные КА. Вероятностный вероятностно-асинхронный КА класса РАР определяется как (L,Q,D,«,ti,6), где L— ¿-мерная целочисленная решетка из п клеток, n^.2,d>\, Q — множество состояний клеток, |Q|=?, D — множество задержек переходов, DeN, | D] = h, u.Lk ->L, n:Qk x Q -»[0,1], [0,1] —единичный вещественный интервал, VweQ^Va eQ 7t(w,a)>0 л ^^^(и^а) = 1 7i(w,a) — условная вероятность перехода клетки в состояние а с некоторой задержкой, 5:0' х D —> [0,1], Vw eQ^'Vb eD 6(и>,Ь)>0л^4е1) 6 (и, b) = 1, где b(w,b) суть условная вероятность

перехода клетки в некоторое состояние а с задержкой Ь, если состояние окрестности ее в момент t было w. Выделены четыре класса вероятностных КА:

(1) PS: it:Qk xQ->[0,l], VweQ J^^n^a) = 1,

(2) PA:itQf xQ-»[0,l], Vu> eQ = 1, Л: Q* -> D, клетка л переходит в

состояние x'*i(u(1 = а с вероятностью л(и(х)',в) и задержкой А(и(х)'),

(3) DAp: /Xt-*Q, Vn-eфИЬ eQ f(w)=bu S:Q* x D->[0,1], V\v eQ1 = J,

(4)РАр:я:(Ухд-^[0,)], VweQ'1^, гг(н',в) = ) и o.Qf xD->[0,l], V»<eQf =

Строится иерархия классов: PScPAp, PS CPA, PScDAp, PAcPAp, DApCPAp. Нечеткие KA. Нечеткий KA класса ГАСА-1 определяется набором (L,[0,l],i/,/,й), где VieN х' е[0,1], /:[0,\f ->[0,1], 8:[0,1]* ->DcN, D — множество задержек переходов, / описывается нечеткой формулой с использованием термов ta = \-a, а\/Ь= тах(а,6), акЬ- min(a,i), о,Л е[0,1] и каждая клетка х совершает переходы по правилу Л'*5("(1)> = f(u{x)'). KA класса FACA-2 описывается набором (L,Q,«,n), где тс: Q х Q* х Q х D -> [0,1], 6sD, п(х' ,и(х)' ,х'*"\х'+1 = х', l<s<b-\) — степень перехода клетки х из состояния х' в момент I в состояние х'*ь в момент t + b, и(х)' — конфигурация окрестности клетки в момент t, а в интервале [t,t + b-\] клетка остается в состоянии х'.

Иерархические КА. Иерархический КА определяется конечной последовательностью одномерных КА Ац, Aj, ..., Ар, где А; управляется Ai+1. КА Ар является каноническим и эволюционирует автономно. Каждая клетка КА уровня i (i = 0, —, /7-1) вычисляет по конфигурации своей окрестности индекс некоторой клетки

КА уровня ¿+1 и принимает ее состояние в следующий момент времени. Представим функцию локальных переходов /, КА А; вектором V, = , так что каждая клетка А|

переходит в состояние vtJ в момент / +1, если в момент t конфигурация ее окрестности и(х)' имела индекс j в лексикографическом списке конфигураций, v: Q' N, \(и(х)') = j. Вектор V). является глобальной конфигурацией КА Л;+). Каждая клетка xl КА Aj вычисляет свое следующее состояние по состоянию окрестности ii,(xf)' и конфигурации КА Ai+1 следующим образом:

х? = 1 = 1,...р-1,где суть j-ii символ в слове

С и v(u,(x,)') = J.

Экзотические КА. Исследованы нетривиальные классы КА, клетки которых принимают состояния из булеана некоторого конечного множества и функция локальных переходов конструируется с использованием операторов алгебры множеств (SETCA), КА над словами (VVORDCA), КА с динамически изменяющейся структурой (STRUCA), указывающие КА (POIN). Они определяются так:

(1) SETCA: Q = 2s, /: Q" ->• Q, S —конечное множество,

(2) WORDCA: Q = A", /:Q* -> Q, А — конечный алфавит,

(3) STRUCA: р:Q' -> Ь*\ /:Q' -»Q, = /(р(и(х)м)(*)'), (A) POINcSTRUCA: h:Qk = }{Ых/у yeu(x).

Результаты раздела изложены в работах [7 -9, 14,23,27,28].

Во ВТОРОЙ ГЛАВЕ рассматриваются алгоритмы идентификации КА.

Синхронные КА класса CIAS. Описывается алгоритм идентификации и приводятся примеры. Особое внимание уделяется минимальности идентифицированного КА и изменению размера окрестности при нарушении условия детерминированности локального перехода. Определяются безусловные переходы и условия полной и неполной идентификации. Обсуждается идентификация КА на машине Тьюринга и систолическом дереве. Оценивается сложность последовательной и параллельной идентификации.

Задача идентификации формулируется следующим образом: задана последовательность конфигураций КА, требуется восстановить правила локальных переходов клеток.

Основу алгоритма идентификации составляет следующая последовательность шагов: выбирается начальный минимальный шаблон клеточной окрестности, выбираются пары двух последовательных конфигураций КА, для каждой клетки считываете» конфигурация окрестности в заданный момент времени и состояние данной клетки в последующий момент времени, результаты заносятся в таблицу локальных переходов. Если в процессе идентификации выясняется, что таблица описывает недетерминированные переходы клеток из состояния в состояние, то размер шаблона окрестности увеличивается и производится повторное заполнение таблицы локальных переходов.

Пусть ifX) и i?(X) оценки временной и пространственной сложности идентификации КА класса X, а ©X) и «?(Х) — оценки для полной идентификации КА класса X соответственно. Обосновываются следующие утверждения:

(1) результат идентификации КА из п клеток, каждая из которых имеет q состояний и к соседей, будет полным только если n>qk\

(2) детерминированный стационарный rf-мерный без памяти КА из п клеток, каждая из которых принимает g состояний и имеет к соседей, полностью идентифицируется машиной Тьюринга с двумя ¿-мерными лентами размера п каждая, одной рабочей лентой размера 0(дк), двумя читающими головками и одной читающей и пишущей головкой за Q(k'M/dq2k) шагов;

(3) К eCLAS идентифицируется на бинарном систолическом дереве из 0(qk) узлов и £(CLAS)=Q(fc5 log5 к).

КА классов NSET, ТОТА, INTER и АТОТ. Доказываются теоремы о сложности идентификации синхронных детерминированных d-мерных КА:

(1)ЯГОТА)= 0(£2+"V+').

(2) £iNSET)= 0(2' qk k"d (к + g2), q< к и ¿TNSF/D=0(f/ /k\),q>k,

(3) ifINTER)= 0(/2 + ft w"),

(4ЖАТОТ

k\{q-1)!

Асинхронные КА. Исследуются алгоритмы идентификации (/-мерных асинхронных детерминированных КА, клетки которых принимают q состояний и имеют окрестность размера к, по последовательности т конфигураций. Доказывается, что

(1) ¿t[ASYN_r)=i^ASYN_n)=0(fc"''qk n(k + b)m), где 6 = max{^(w)|w eQ'}, для He ASYNJh 6 = max{S(iv)|w sQ'}, для ?IeASYN_II,

(2) ¿(ASYN_I)=i(ASYN_II)= 0(kvd q21 (k + b)b),

(3) если клетки совершают переходы с задержкой не более Л, то асинхронный Л идентифицируется полностью на массово-параллельной схеме размера 0(q2k) за время 0((h + q") к2*ш).

КА с памятью. Доказывается, что У(МЕМО)=0(А:"'' q^y1 (ку + q2).

Результаты раздела изложены в работах [1,2,3,6, 12, 16, 19,21,28, стр. 57-80].

Вероятностные клеточные автоматы. Рассматриваются два варианта идентификации вероятностного КА: (1) нет априорной информации о КА, кроме размерности (GP-идентификация и PG-идентификация), (2) известно к какому классу идентифицируемый автомат принадлежит (D-идентификация). Демонстрируются способы анализа поведения КА по структуре вероятностных матриц локальных переходов. Приводится параллельная схема идентификации вероятностного КА.

D-идентификация. Обсуждаются алгоритмы идентификации вероятностных КА из п клеток, каждая из которых имеет q состояний и к соседей, по т конфигурациям (т достаточно велико для сходимости последовательности матриц стохастических переходов). Доказывается, что:

(1) f[PS)=0(mq2k к'*ш) и ),

(2) при идентификации аппроксимируется минимальный вероятностный КА,

(3) 6TPA)=0(mq2k к'*'") и «Я[РА)=0(mq1*'),

(4) ¿ШАр)=0{qk k"d (mqk + к) и ¿(DAp)=0(mqkH),

(5) Я(РЛр)=0(qk кш ((mq)2 + mqkk) и J(PAp)=0(mqH>).

GP- и РС-идентификшшя. Допустим, что класс, к которому принадлежит идентифицируемый КА Л, неизвестен в начале идентификации. Предлагается два возможных пути построения вероятностных матриц локальных переходов клеток и задержек переходов: (1) GP-идентификация: допустим, что ЛеРАр, идентифицируем Н, затем редуцируем до одного из простых классов, (2) PG-идентификация: допустим, что ?tePS, идентифицируем К, и если вычисляемая последовательность вероятностных матриц локальных переходов не сходится, то полагаем ЛеРА, и т.д. Доказывается, что

(1) Л GP-идентифицируется за время f ((тф2+т4+к)) и +к)+т),

(2) Л PG-идентифицируется за время Q(kMI*mq2k) и 0(kluqM т(Щк"г +от)>.

Результаты данного раздела изложены в работах [5,22,28, стр. 81-89].

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

(1) ^FACA-l)=0(míЛ1+"',) и <i(FACA-l)=0(m«A:,/''),

(2) tf(FACA-2)= 0(ткш n(k + m + qk*2)) и i(FACA-2)=0(m^+2).

-ID-

Результаты данного раздела изложены в работах [8 и 28, стр. 90-94].

Иерархические КА. Обсуждаются дополнительные свойства иерархических КА и представление функции локальных переходов в виде перестановки. Приводится алгоритм и оценивается его сложность. Рассматриваются примеры. Доказывается, что, если А={Ао,...,Ар} — иерархический КА из р уровней, каждая клетка автомата А имеет q состояний и 0{К) соседей, K = msx{ki\i = Q,...,p} и каждый КА Aj содержит 0(п) клеток, то S\k)=0(mn(K+q)(p+ Кш)).

Экзотические КА. Предлагаются, обсуждаются, иллюстрируются и оцениваются алгоритмы идентификации ¿-мерных КА классов STRUCA, POIN, WORDCA, SETCA из п клеток, каждая из которых имеет q состояний и к соседей. Доказывается, что

(2) И ePOINnTOTA идентифицируется как элемент POIN,

(3) Я ePOINn CLAS идентифицируется как элемент CLAS, не принадлежащий POIN,

(4) SPOINnCLAS)=0(^2+,w <?"),

(5) ¿[W0RDCA)=0(A:1/i+1 q2'11),

(6) ¿(SETCA)= 0(к1+ш 4q> q).

Результаты разделов изложены в работах [25 и 28, стр. 94-104, 321-328].

В ТРЕТЬЕЙ ГЛАВЕ обсуждаются свойства полных конфигураций одномерных детерминированных синхронных КА. Доказывается теорема о размере полной конфигурации, обосновывается схема факторизации полных конфигураций по шаблонам соседства и вычисляются множества полных конфигураций. Рассматривается разрешимость проблемы полной идентификации КА по произвольно выбранной паре его конфигураций и наследственность полных конфигураций. Решается задача преобразования произвольной конфигурации в другую специально подобранной функцией локальных переходов, проектируется, обосновывается и оценивается алгоритм определения неконструируемости произвольной конфигурации и исследуется алгебра над матрицами, связанными с глобальными преобразованиями КА.

Следующие утверждения относятся к одномерному КА класса CLAS с q клеточными состояниями, клеточной окрестностью размера к и длины п. Доказывается, что если среди конфигураций КА присутствуют полные, то п имеет следующие границы: 1.CLAS: Q(f/),2. TOTA:Q(^),3.NSET:Q(gfc +1),4. ATOT:Q(g(/c + q)\l{k + q)k\q\), 5. INTER:Q(2/+I). Показывается, что КА идентифицируется полностью по паре произвольных конфигураций при достаточно больших и; практически все полные конфигурации КА с бинарными клеточными состояниями могут быть получены конкатенациями полных конфигураций минимального размера с элементами множества клеточных состояний.

Предлагаются эффективные алгоритмы вычисления минимальных неконструируемых конфигураций. Определим вспомогательную операцию

{True И7' __w"

False,wj+s * w,"

W,w" eQ*.5=0,Конфигурация с = (q...aj неконструируема, если

выполняется одно из условий:

(1) 3wi,w2,...,w„ eQ\ Wj =^.mod„ j = n+i,...,n + k-l: f(wl)=av...,/(wj = an и лы n,j,M i+k-1 9(vv1,w.,7-i) = True для периодических границ;

(2) 3n\,w2,...,wn,w' eQ*, wt = w1, j = rn-\,...,n +k-1: f(wx) = a,,...,/(wn) = an и Л-i. n j.i+i j+a-1 Q(wi,wJ,j-i) = True дня фиксированных границ.

Доказаны теоремы о том, что

(1) задача определения неконструируемости заданной конфигурации КА решается за время 0(nqk ),

(2) для q<k<n КА имеет неконструируемые конфигурации, если он имеет по крайней мере один неконструируемый блок длины не более к,

(3) неконструируемость произвольной конфигурации КА определяется за время 0(qk ).

Исследуются отношения на Q" xQ", п е N. Пусть R:Q" х Q" —» {Qu{?}}'u{-}, где h = qk для CLAS, h = 2" -1 для NSET и h = k(q-\) для ТОТА. С использованием R определяются отношения Lc: Q" xQ" и DcQ'xQ" как Vc\c" sQ" l' Dс" <=> {R(c',c") Ф -}(вектор, описывающий детерминированную функцию локальных переходов клеток, восстанавливается, хотя, быть может, и не полностью) и c'Lc"<=>{R(c',c")'iF = (^)|SiS?1: V/ V, eQ}(KA идентифицируется полностью по

заданной паре конфигураций). Доказаны следующие свойства отношений:

(1) Vc",c" sQVLc"=>CDc",

(2) Vc\c" е Q" c'Lc" => {с1 -полная конфигурация),

(3) Vc7, с" б Q" с* Dc" => |Vx,_>' и(х)' = ¡/(у)2 => x2 = у2},

(4) Для q > 2, к > 2, п > 3, d > 1 отношения D и L иррефлексивны, нетранзитивны и антисимметричны.

По определенным выше отношениям строится три типа матриц над глобальными состояниями детерминированных одномерных КА длины и:

_/-я строка матрицы I называется пустой, если для любого / = !,...,<7": = А.. Следующие свойства характеризуют матрицу I:

(1) Число пустых строк матрицы I равно числу полных конфигураций КА, над которым

данная матрица была построена,

(2) (у'-я строка матрицы I непуста) => (V/,/' е{1,.(/,,. * X л /г

(3) Все непустые строки матрицы I попарно различны.

Матрицы О и V используются для вычисления оптимального пути клеточно-автоматного преобразования одной конфигурации в другую. При вычислении

<')V = (^W VtJ=R(с„с,), (2)D = 0D„)lW> 2>„ =

' 1, с,Щ О, (с„с,)гD'

используется операция • поточечного произведения элементов V. Строится алгебра ({Qu{?}}'lu{-},«}, где произведение двух элементов v',v" e{Qu{?}}Au{-} вычисляется следующим образом

Г?, v' = ?д v" = 1

Г- Э1е{1,...,Л} v;*?av;'*?av;*v,"

у' • v" = < v'o v"= < v', V ф ?

1 <v!° > v;=?vv;'= ?v v[ = v/' 11 ;

[ vj; v"*?

Алгебра ({Qu {?}}й <j {-},•) —коммутативный моноид порядка 1 с нулем. Пусть ц:{2и{?}}'1 —> {0,1,...,/(} — число различных глобальных переходов, представленных элементом {Qu {?}}\ |x(v) = ^ . x(vi>')> гДе X(v,>?) = ' W v, f ? и 0 в

противном случае, тогда выполняются следующие утверждения: (1) Vv'^-'eiQui?}}11 n(v'.v")>max(n(v'),n(v")), (2) Vve{Qu{?}}A l<(j.(v)<A.

Пусть для двух данных конфигураций с, и с] DtJ = 0. Можно ли преобразовать с, в Cj за конечное число шагов с использованием функций локальных переходов при

фиксированных k,q,u,n1 В общем случае задача решается вычислением по матрице D матрицы ' каждый элемент Р~ — число глобальных переходов

преобразования с, с). Вычисляется матрица длин кратчайших путей с

использованием стандартных процедур вычисления кратчайшего пути на взвешенном графе (алгоритм РАТН1). Для минимизации числа правил локальных переходов, используемых в процессе преобразований, вводится функция rftf:{Qu{7}}4 х {Qu{?}}" -»{0.....А}, = „«(^О. где

1, v;*v"av;*?AV;v?

! ' ' ,' „ (алгоритм РАТНО).

[0, V, = "V V, = "V V, = V

Пусть кратчайший путь клеточно-автоматных

преобразований конфигурации с,- в конфигурацию был вычислен по алгоритму РАТН1, а путь ,с4) - по алгоритму РАТНО. Тогда ра < ¡\ и

У+1 '^у'+г)'

Результаты данной главы изложены в работах [31 и 28, стр. 105-128,307-328 ].

В ЧЕТВЕРТОЙ ГЛАВЕ обсуждается идентификация систем дискретно-движущихся объектов, групп агентов, нейронных сетей, реакционно-диффузионных сред и взаимодействующих популяций живых организмов, а также алгоритмы проектирования массово-параллельных (в том числе нейронных и молекулярных) вычислителей и демонстрируются механизмы решения с их помощью ряда задач дискретной вычислительной геометрии.

Дискретное движение. Показывается, как восстановить правила перемещения и столкновения идеальных объектов на целочисленной решетке. Алгоритм идентификации слагается из двух этапов: трансляции моментальных снимков эволюции системы движущихся объектов в серию конфигураций КА и собственно идентификации. Оценивается сложность идентификации и рассматриваются примеры идентификации систем, подобных решеточному газу с отражателями.

Пусть задана система В абстрактных объектов, двигающихся с единичной скоростью на (/-мерной решетке размера п (время дискретно) и взаимодействующих друг с другом на расстоянии не более неотрицательного целого г в Доказывается, что

(1) В моделируется на ¿/-мерном КА, каждая клетка которого имеет 0(8'') состояний и (2г + 1)* соседей,

(2) алгоритм трансляции т бинарных глобальных состояний В в конфигурации КА имеет временную сложность 0{птЪй),

(3) В идентифицируется по набору т моментальных снимков за время 0(8Л тпки1) для к = (2г + ¡У. Результаты раздела изложены в работах [15 и 28, стр. 130-145].

Имплантация КА. Рассматриваются различные типы имплантации1, нейтральная имплантация, активный имплант — пассивный акцептор и пассивный имплант — активный акцептор. Прогнозируются последствия имплантации. Рассматривается элементарная имплантация на примере однородных двумерных нейронных сетей. Строятся иерархии имплантируемое™ и сложности имплантации. Оценивается эффективность алгоритмов активной имплантации для различных архитектур импланта. Рассматривается динамическое взаимодействие «акцептор — имплант».

По типу взаимодействия импланта (ИМ) с акцептором (АК) имплантация разбивается на два основных вида: (1) ИМ и АК не взаимодействуют, (2) ИМ распознает свойства АК. Для имплантации первого вида обосновываются критерии имплантируемости в терминах алгебраических систем. Оценивается сложность

имплантации второго вида: пусть КА К\ имплантирован в КА Л2 и каждая клетка Л2 имеет к соседей. Тогда каждая клетка-идентификатор Л1 имеет 0.(2'' к) соседей, где (1 — размерность КА.

Строятся иерархии имплантации:

1. Пусть —» — такое бинарное отношение, что УХ, У е{П8, ПА, БАр, ГЯ, ГА, ГАр}, X Ф У, X —> У означает, что для каждого элемента X е X найдется элемент У еУ, такой что X имплантируем в К. Тогда иерархия имплантируемости будет иметь вид как на Рис. 1;

2. Пусть каждая клетка КА из Г)Я, 1)Л, ОАр, ГЭ, РА и ГЛр имеет ц состояний, к соседей, максимальную задержку перехода Л, и IV градаций нечетких переходов и и>>~(У у Иуд или и> >- » Л >- ц. Пусть Тх - пространственная сложность имплантации в КА класса Хи -» — такое бинарное отношение, что X—> У, если Ту !~ТХ. Тогда задает на множестве {ОЭ, Г)Л, ОАр, Гв, ГА, КАр} следующую иерархию пространственной сложности имплантации (Рис. 2)._

05

А1

А2

АЗ

А4

Рис. 1.

Рис. 2.

Рис. 3.

Оценивается эффективность архитектур КА-ИМ, изображенных на Рис. 3 (символом • отмечены внешние клетки ИМ, показаны двусторонние связи между клетками). Пусть клетки АК принимают q состояний и имеют к соседей, а клетки ИМ — к' соседей; ИМ состоит из п клеток. Пусть Т(А,Х) — оценка временной сложности имлантации ИМ с архитектурой А в АК класса X, а I» — оценка локальной памяти клеток ИМ. Доказывается:

(1)Т(Л1, №)=0(q'(k + q")k>ld) для L=0(qktl);TH/,DA)=9(p(Jfc + qk)k"d) ,Ь=0(м/:,>), а - максимальная задержка перехода клеток АК, р = тах{а,</*},

(2)T(/li,FS)= £i(qk*\k + qk +q)),h=Q(wqkM), w -число градаций нечетких переходов клеток AK;T(/UFA)=T(,UDAF)=T(/47,FAF)=n(ú?,'+V +k + q+a)).

Предлагается два способа идентификации АК посредством ИМ, когда ИМ имеет архитектуру типа А2. В первом, А2.1, клетки ИМ обмениваются текущими результатами идентификации АК, однако описание локальных переходов клеток АК хранится в каждой клетке ИМ. Во втором, А2.2, - описание правил переходов клеток АК распределено между клетками ИМ. Доказывается ряд теорем о сложности имплантации:

1.T(A2.1,DS)=0(qkk"d(qk + к + к')) иТ\А2.1,DS)=n((^ +к + k')c¡k,ld/к'), ТИ2.7,DA)= 0(ркш(с/: +к + к')) иГ(Л2Л,1)А)= Q((qk +к + k')pk"d/к');

2.Т'(А2./,FS)=íi(qk*' !k\qk + к + к' + ?)) (L=0(wq':^)),

3.Т(А2. l,fA)=T(A2.1,DAF)=T(A2.7,FAF)= Í2(aqk(qk+k + k'+ q+a) /k')-

4. Пусть ИМ имеет архитектуру А2, вживляется А2.2, максимальная задержка переходов клеток АК равна w и время имплантации ограничено целым g, тогда:

(1)DS:i=0(?), n>(qkd-,f 'l-\

(2) DA: Ь=0(q), п > (aqkdrY"~n,

(3) FS: h=0(w), n > (qk*,d~lfdA),

(4) FA, DAF, FAf. h=0(w), n> (gq':t'íl~')'"''-";

5. Оценки сложности имплантации ИМ с архитектурой А3 такие же, как в п.2., если: (1) DS: п> qk, (2) DA: n>aqk, (3) FS: n>qk*\ (4)FA, DAr,FAf: n>gqktl;

6.Пусть n>íf,тогда

(1) ЦА4, Ш)=П(км"(\ + qk \ogq)) ,2(A4,DS)=0(qkt[),

(2) nA4,DA)=n(aku"d(\ + qk logg)), S(A4,ÜA)=0(aqk*'),

(3) ЦА4,FS)= Cl(qk(\ + (cf + q)\ogq)), S(A4,FS)=0(wqM),

(4) 7{A4,FA)= 7[A4,DAf)= 7(^(4,FAF)=CXa^l+(^ +q+a)logq)), ¿(A4,FA)= $A4,DAF)= ЩА4,FAjr)= 0(gqk*'), где — пространственная сложность имплантации.

Результаты раздела изложены в работах [28, стр. 146-172, и 25]. Распределенный интеллект. Обсуждаются способы вычисления правил локального взаимодействия агентов по наборам глобальных состояний распределенной регулярной эпистемической доксастической акциональной системы. Оценивается сложность алгоритмов. Доказывается, что

(1) система I распределенного интеллекта из п агентов, размещенных в узлах с1 -мерной целочисленной решетки, где каждый из агентов имеет к соседей, обладает информацией о не более чем р фактах и может совершить не более чем а действий, ^ = тах(р,с), идентифицируется по т моментальным снимкам за время 0(тпкш(¥2+ 5^ + 2)));

(2) I идентифицируется полностью за время 0(2"5 к"11 (З^2 + 5Цк + 2))\

(3) временная сложность идентификации консервативной I составляет 0(тл2^2 к:м").

Результаты данного раздела изложены в работах [13 и 28, стр. 173-179].

Нейронные сети. Пусть заданы паттерны активности некоторой однородной двухмерной нейронной сети. Обосновываются способы идентификации сети по заданным паттернам активности. В результате идентификации выводится локальная структура межнейронных связей.

Пусть задана последовательность моментальных снимков одиночного нейрона, растущего на планарной подложке с субстратом и фактором роста. Приведен алгоритм восстановления правил удлинения нейронных отростков и изменения направления их приращения. Доказывается, что минимальное остовное дерево планарного множества п точек вычисляется на двухмерном клеточно-автоматном процессоре размера 0{п) за время О(А) алгоритмом роста дендритного дерева, где к — максимальное число вершин в ветвях от корня дерева до листьев.

Результаты изложены в работах [2, 16, 17, 22,28, стр. 186-189].

Реакционно-диффузионные среды. Исследована идентификация реакционно-диффузионных сред И с большим числом реагентов. Получены оценка сложности:

(1) пусть задана И с г реагентами, описываемая КА класса К8ЕТ, где реагент, находящийся в некоторой клетке, взаимодействует с реагентами, содержащимися в к соседних клетках, тогда Ш идентифицируется за время (к + р2р),

(2) ПТ с г реагентами идентифицируется за время (к+ р2).

Результаты раздела изложены в работах [28, стр. 209-207, 30].

Взаимодействующие популяции. Исследованы алгоритмы идентификации систем взаимодействующих популяций живых организмов, рассмотрены варианты симбиотических отношений (протокооперация и мутуализм), конкуренция за ресурсы, системы типа "хищник — жертва", циклические трофические пути, системы "один аутотроф —два гетеротрофа" и "два аутотрофа — один гегеротроф".

Результаты данного раздела изложены в работах [3, 4, 20, 28, стр. 208-238].

Проектирование молекулярных компьютеров. Обосновываются методы проектирования молекулярных вычислителей по заданной структуре преобразований, которые требуется реализовать на создаваемом вычислительном устройстве. Проектирование параллельного молекулярного вычислителя сводится к размещению химических реакторов с учетом шаблона соседства, установлению числа реагентов и механизмов взаимодействия реагентов друг с другом. Показывается, как использовать алгоритмы идентификации КА при проектировании молекулярных компьютеров, решающих задачи построения дискретной диаграммы Вороного, дискретной выпуклой оболочки, поиска выхода из планарного лабиринта, кратчайшего пути и обработки изображений (особенности, эрозия и диляция).

Аппроксимация дискретной диаграммы Вороного. Строится реакционно-диффузионная среда Ш, способная аппроксимировать диаграмму Вороного (ДВ) узлов двухмерной целочисленной решетки (вершины и ребра ДВ представляются помеченными узлами). Пусть L - двухмерная целочисленная решетка из тхт узлов, а Р — множество выделенных узлов данной решетки, |Р| = и. Клетка Вороного узла р определяется как DVC(p) = {x eL: [х- /?|<|;с-г[ Vz еР), где |-| —расстояние между узлами в метрике Ц (£„), а дискретная ДВ: DVD(P) = U(,6P<3üi/C(/>). Доказывается, что:

(1) Ш из тх т реакторов (каждый диффузионно связан с 4 (8) ближайшими) и п + 3 реагентов аппроксимирует DVD(P) в метрике L,(L„) за время 0(т-п/ т);

(2) Щ из т х т реакторов (каждцй диффузионно связан с 4 (8) ближайшими) и 4 реагентов аппроксимирует DVD(Р) в метрике L,(L„> за время 0(т-п/т).

Пусть задано множество P = {S,,...,S„} непересекающихся подмножеств

выделенных узлов двухмерной решетки из т х т узлов. Обобщенная ДВ определяется как GD VD(Р) = Ц =р8D Vor(S,), где DVo>(Sl) = {z еЦ Va eS,Vi>еP-S, d(a,z) <d{b,z)}■

Доказывается, что

(1) GD VD (P) не может быть построена в с O(l) реагентами,

(2) Ш из тх т реакторов (каждый диффузионно связан с 4 (8) ближайшими) и п + 3 реагентов аппроксимирует GDVD (Р) в метрике L,(L,) за время 0(т-п/т).

С использованием волновых алгоритмов аппроксимации дискретной ДВ получены результаты по обращению ДВ Kor(S) планарного множества S мощности п, т.е. вычислению элементов S. Доказано, что

(1) S вычисляется по Kor(S) только тогда, когда Vor(S) имеет по крайней мере одну замкнутую клетку Вороного,

(2) задача обращения Vor(S) решается на клеточно-автоматном процессоре за время 0(п).

Результаты раздела изложены в работах [10,11, 18, 24, 26, 28, стр. 241-255].

Дискретная выпуклая оболочка. Дискретная выпуклая оболочка СН45(S) множества S узлов двухмерной целочисленной решетки размера п определяется как {(¡J): a i+b j<c, |а|,|6|<1, ceZ}.

Показывается, что Ш с п реакторами, связанными диффузионно с 8 ближайшими соседями, и двумя реагентами аппроксимирует СН45(S) за время 0(л"2).

Результаты раздела изложены в работах [29 и 28, стр. 256-261].

Планарнын лабиринт и кратчайший путь на решетке. С использованием алгоритмов идентификации строится однородная среда, решающая задачу поиска выхода из дискретного планарного лабиринта. Вычисляются структура клеточной окрестности и правила переходов клеток из состояния в состояние, включая приоритет сканирования элементов окрестности. Доказываются следующие утверждения (двухмерная решетка G имеет п узлов, КА К— п клеток):

(1) Пусть некоторые ребра G вырезаны, тогда Л, клетки которого имеют 4 соседей и 9 состояний, вычисляет кратчайший путь (КП) между парой вершин (S^DSP) на G за время О(п) и КП из заданной вершины во все остальные за время О(п) и экстрагирует путь за время 0(и2);

(2) К, клетки которого имеют 6 соседей и 5 состояний, вычисляет S^DSP за время

0(п);

(3) Пусть ребра G имеют веса из {0,..., v,to}, тогда Я, клетки которого имеет 4 соседей и 16 + 5« состояний, вычисляет S3DSP за время 0(\п) \

(4) Пусть полустепень захода каждой вершины G не превышает целого положительного к, тогда Л из п клеток, каждая из которых имеет к соседей и 0(\к) состояний, строит S^DSP на G за время 0((v + к)п) и экстрагирует S^P за время 0(пг).

Результаты раздела изложены в работах [32 и 28, стр. 261-270].

Управляемая передача информации в возбудимых средах. Идентификацией двухмерного КА, имитирующего возбудимые среды, выявлены правила локальных переходов для частной возбудимой среды, способной направленно и управляемо передавать информацию. Показано, что в этой среде существуют ограниченные паттерны, которые являются минимальными неделимыми компактными стабильными способными к безостановочному движению группами состояний возбуждения. Доказывается, что посредством одиночной стимуляции рецептивного поля паттерна достигается любое изменение направления вектора скорости и преобразование типа паттерна за конечное число шагов. Результаты данного раздела изложены в работах [30 и 35].

В ЗАКЛЮЧЕНИИ приведены основные результаты диссертационной работы, которые состоят в следующем:

I. Осуществлена классификация клеточных автоматов по признакам детерминированности ! недетерминированности, синхронности / асинхронности, структуре множества клеточных состояний и клеточной окрестности, по виду функции локальных переходов клеток. Проведен полный сравнительный анализ канонических, обобщенных, над множествами, с памятью, нечетких, вероятностных, иерархических, над словами, структурно-динамических и указывающих клеточных автоматов. Построена иерархия сложности клеточных автоматов и иерархия моделируемости клеточных автоматов одного класса на клеточных автоматах другого класса.

II. Предложены методы восстановления функции локальных переходов по набору конфигураций КА, построены и обоснованы алгоритмы идентификации для всех классов клеточных автоматов, получены оценки сложности последовательной и параллельной идентификации.

III. Исследованы алгебраические системы и ассоциированные матричные структуры над классами клеточных автоматов.

IV. Предложены методы вычисления неконструируемых конфигураций.

V. Проведено практическое внедрение теоретических результатов на примерах идентификации систем движущихся объектов, нейронных сетей, морфогенетических структур, реакционно-диффузионных сред, популяций животных и растений.

VI. Обоснованы способы идентификации эпистемических и акциональных систем распределенного интеллекта.

VII. Предложена схема автоматического проектирования молекулярных компьютеров по структуре решаемой задачи, эффективность которых исследована на задачах вычислительной геометрии и обработки изображений.

VIII. Построены массово-параллельные алгоритмы вычисления дискретной диаграммы Вороного, дискретной выпуклой оболочки и поиска кратчайшего пути на решетке.

IX. Найдена структура однородной возбудимой среды, способной к направленной управляемой передаче информации.

Основные результаты диссертации опубликованы в следующих работах:

1. Адамацкий А.И., Бронников В.А. Идентификация аддитивных клеточных автоматов.// Изв. АН СССР. Сер. Технич. кибернетика, 1989. т. 3, с. 200-205.

2. Адамацкий А.И., Бронников В.А. Об одном способе идентификации однородных нейронных сетей по набору паттернов активности.// В сб.: Проблемы нейрокибернетики (материалы IX Всесоюзн. конф. Проблемы нейрокибернетики), 1989, Ростов-на-Дону, с. 344.

3. Адамацкий А.И. Идентификация параллельных локальных процессов управляющими ОВС.// В сб. 1-й всес. конф. Однородные вычислительные среды и систолические структуры, 1990, Львов, т.З, с. 7-9.

4. Иванов С.Ф., Бронников В.А., Соловьев М.В., Адамацкий А.И. Спецпроцессор ЛОКОН: Моделирование систем с локальным взаимодействием. // В сб. 1-й всес. конф. Однородные вычислит, среды и систолические структуры, 1990, Львов, т.З, с. 75-79.

5. Адамацкий А.И. Идентификация вероятностных клеточных автоматов.// Изв. АН СССР. Сер. Технич. кибернетика, 1991, т.З, с. 95-100.

6. Адамацкий А.И., Иванов С.Ф. Локальный параллельный анализ символьных последовательностей.// В сб. Систолический Процессор. НИЦ Высокопроизводительных вычислительных систем. 1991, N б. с. 54-59.

7. Адамацкий А.И. Идентификация нестационарных асинхронных клеточных автоматов. // В сб. Систолический Процессор. НИЦ Высокопроизводительных вычислительных систем. 1991, N 6. с. 60-71.

8. Адамацкий А.И. Идентификация нечетких клеточных автоматов.// Автоматика и вычислительная техника, 1991, т.6, с. 75-80

9. Адамацкий А.И. О сложности идентификации нестационарных клеточных автоматов. // Изв. АН СССР. Сер. Технич. кибернетика, 1992, т.З, с. 74-79.

10. Адамацкий А.И. Локальное параллельное построение диаграммы Вороного.// Электронное моделирование, 1992, т. 1, с. 26-29.

11. Адамацкий А.И. Локальное параллельное построение некоторых графов с вершинами на плоскости.// Электронное моделирование. 1992, т.2, с. 24-28.

12. Адамацкий А.И. О сложности идентификации клеточных автоматов.// Автоматика и телемеханика. 1992,т.9,с. 72-86

13. Адамацкий А.И. Идентификация распределенного интеллекта.// Изв. АН СССР. Сер. Технич. кибернетика, 1993, т. 6., с. 359-369.

14. Адамацкий А.И. Сложность последовательной реализации клеточно-автоматных отображений. // Автоматика и телемеханика. 1994, т.З, с. 149-160.

15. Adamatzky A.I., Bronnikov V.A. Graphic presentation of nucleotide sequences m computer simulation oí gene evolution.// Studia Biophysics, 1989, v. 125, p. 251-255.

16. Adamatzky A.I. Neural nets identification.// In: International Conference on Neural Networks and Neural Computing, 1990, Prague, p. 1-4.

. Bronnikov V.A., Adamatzky A.I. Neural nets simulation by cellular automata with global feedback. II In: NEURONET'90, 1990, Prague, p. 58-59.

. Adamatzky A.I. Neural algorithm for constructing minimal spanning tree.// Neural Network World,

1991, v. 6, p. 335-339

. Adamatzky A.I., Bronnikov V.A., Ivanov S.F. Local parallel analysis of nucleotide sequences.// In: Modelling and Computer Methods in Molecular Biology and Genetics. Abst. of the Int.Conf., 1991, Novosibirsk, c. 237-238.

. Adamatzky A.I. Identification of natural systems with locally interconnected elements.// In: Proc.

Second Int. Conf. on Industrial and Applied Mathematics, 1991, Washington, p. 132. . Adamatzky A.I. On complexity of complex systems identification.// In: Abst. Int. Conf. on Complex

Systems: Fractals, Spin Glasses, and Neural Networks. 1991, Triest., p. 56. . Adamatzky A.I. Neural nets identification.// In: Theoretical Aspects of Neurocomputing. M. Novak

and E. Pehkan (Eds.), World Scientific, Singapur,1991, p. 79-93. . Adamatzky A.I. Identification of nonstationary cellular automata.// J. of Comput. Sci. and Technol.,

1992, v.7,N4, p. 379-382.

. Adamatzky A.I. Massively parallel algorithm for inverting Voronoi diagram.// Neural Network World,

1993, V. 5, p. 385-392.

. Adamatzky A.I. Implantation of cellular automata.// Applied Math. Computations, 1993, v.l, p. 59-72.

. Adamatzky A.I. Reaction-diffusion algorithm for constructing discrete Voronoi diagram.// Neural

Network World, v.6, 1994, p.635-643. . Adamatzky A.I. Hierarchy of fuzzy cellular automata// J. Fuzzy Sets and Systems, 1994. v. 3, p. 74-79.

. Adamatzky A.I. Identification of Cellular Automata, Taylor & Francis, London, Bristol, 1994, 337 pp.+ X pp.

. Adamatzky A.I. Computation of discrete convex hull in homogeneous automata networks.// Neural Network World, 1995, v. 3.

. Adamatzky A.I. Controllable transmission of information in the excitable media: V- medium.//

Advanced Materials for Optics and Electronis, 1995, v. 5, 145-155. . Adamatzky A.I. Nonconstructible configurations in one-dimensional cellular automata.// Applied Math. Computations, 1996, v. 3.

. Adamatzky A.I. Computation of shortest path in cellular automata// Mathematical and Computer

Modelling, 1996, v. 23, N4.. . Adamatzky A.I. Computation in living systems. A paradigm of reaction-diffusion algorithms.// ACM Symp. Theory of Computing '95. NSF Theory of Computing Program Session. White Papers. Washington, June, 1995.

. Adamatzky A.I. The unknowable knowledge. II Einstein Meets Magritte Conference. Brussel, Belgium, 1995.

Adamatzky A.I. Voronoi-Iike partition of lattice in cellular automata//Mathematical and Computer Modelling, 1996, v.23, v. 4..

. Adamatzky A.I. On the particle like waves in the discrete model of excitable media//Neural Net work World, 1996, v. 1.