Юлия геннадьевна автоматная модель одной транспортной системы в биологии

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

УДК 519.71 Гераськина Юлия Геннадьевна АВТОМАТНАЯ МОДЕЛЬ ОДНОЙ ТРАНСПОРТНОЙ СИСТЕМЫ В БИОЛОГИИ 01.01.09 дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

МОСКВА 2009

Работа выполнена на кафедре Математической теории интеллектуальных систем Механико-математического факультета Московского государствен ного университета имени М.В. Ломоносова.

Научный руководитель доктор физико-математических наук, профессор Валерий Борисович Кудрявцев Научный консультант доктор медицинских наук, профессор Александр Григорьевич Чучалин

Официальные оппоненты:

доктор физико-математических наук, профессор Александр Витальевич Чечкин (Военная академия имени Петра Великого Ракет ных войск стратегического назначения МО РФ) кандидат физико-математических наук Константин Владимирович Коляда (ООО Стальконструкция) Ведущая организация Московский Энергетический Институт (Технический университет)

Защита диссертации состоится 20 марта 2009 г. в 16 ч. 40 м. на заседа нии диссертационного совета Д.501.001.84 при Московском государствен ном университете им. М.В.Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, Московский государственный университет имени М.В. Ломоносова, Механико-математический факуль тет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико математического факультета МГУ имени М.В. Ломоносова (Главное здание, 14 этаж).

Автореферат разослан 20 февраля 2009 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических наук, профессор А.О.Иванов

Общая характеристика работы

Актуальность темы Характерной чертой науки является растущая значимость ее матема тизации, которая является одним из важнейших факторов ее комплекс ного развития. Это относится также к биологии и медицине. Одним из важных направлений в них является изучение и на его основе формали зация функционирования как отдельных органов, так и их систем. Зна чительные успехи достигнуты в этом в системе кровообращения (Guyton1, Noordergraaf2 ), работе сердца (Neumann3, Hunter4 ), печени (Celechovska5 ), почек (Paramjit6 ) и других органов7. Работы по моделированию легких (Macklem8, Saidel9 ), одних из самых важных для жизнедеятельности ор ганизма органов, начались в конце 70-х годов прошлого столетия. Акту альность изучения их функционирования с годами нарастает в виду все большего ухудшения экологической обстановки.

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

Здесь изучается функция легких, которая называется клиренсом (транспортировка вещества по легким) и состоит она в том, что в них предусмотрен механизм ресничкового типа, который и реализует эту функ A.Guyton The relationship of cardiac output and arterial pressure control, Circulation, Vol. 64, 6, 1981, pp. 1079-1088.

A.Noordergraaf Circulatory system dynamics, Academic Press, San Diego, California, 1978.

Mlcek, J. Neumann, O. Kittnar, V. Novak Mathematical Model of the Electromechanical Heart Contractile System - Regulatory Subsystem Physiological Considerations, Physiological Research, 50, 2001, 425-432.

I. J. Legrice, P. J. Hunter, B. H. Smaill Laminar structure of the heart: a mathematical model, AJP Heart and Circulatory Physiology, Vol 272, Issue 5 2466-H2476.

L. Celechovska A simple mathematical model of the human liver, Applications of mathematics, Vol. 49, No. 3, pp. 227-246, 2004.

S.Paramjit, Chandhoke, Gerald, Saidel Mathematical model of mass transport throught the kidney: eects of nephron heterogeneity and tubular-vascular organization, Annals of Biomedical Engineering, Vol. 9, pp.

263-301, 1981.

J. T. Ottesen, M.S. Olufsen, J.K. Larsen Applied mathematical models in human physiology, SIAM, P. T. Macklem Respiratory Mechanics, Annual Review of Physiology, Vol. 40, 1978, pp. 157- M. Erald, Saidel, M. Gerald, Burma Multibreath tracer species dynamics in the lung, Bulletin of Mathematical Biology, Vol. 43, pp. 1-19 Pergamon Press Ltd. 1981.

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

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

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

Структура и объем диссератации Диссертационная работа изложена на 108 страницах и состоит из вве дения и трех глав, разбитых на параграфы. Библиография включает наименований.

Научная новизна 1. Предложена автоматная модель для описания функционирования ме ханизма транспортировки вещества по легким (автоматная модель транс портировки АМТ).

2. Рассмотрен случай функционирования АМТ в чистой среде. Для соответствующего автономного автомата оценено число состояний в нем.

Описаны стартовые состояния и найдено их число. Найдена средняя глу бина диаграммы Мура АМТ, указан критерий перехода одного состояния в другое и оценено время такого перехода. Найдено время полного само очищения.

3. Рассмотрен случай функционирования АМТ в загрязненной, но ста ционарной среде, которая также является автономным автоматом. Для него решены задачи, указанные в случае чистой среды, а также решена задача описания финальных состояний и оценено их количество.

4. Рассмотрен общий случай функционирования АМТ в нестационар ной среде. Для этого автомата, который уже не является автономным, с помощью рассмотренных случаев 2. и 3. решены задачи, указанные для этих случаев, а также решена задача описания нестационарных сред, в которых модель функционирует не более чем с заданной долей допусти мой ее загрязненности. Решение последней задачи получено как в форме рекуррентно-комбинаторного представления, так и с помощью автоматно алгебраического описания типа Клини и МакНотона.

Основные методы исследования В диссертации использованы методы теории автоматов, графов, ком бинаторики, алгебры и математического анализа.

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

Апробация работы Результаты диссертации неоднократно докладывались на семинарах механико-математического факультета МГУ им. М.В. Ломоносова ”Теория автоматов” (2003-2008 гг.) и ”Кибернетика и информатика” (2003-2008 гг.) под руководством академика В.Б. Кудрявцева и на семинарах в Институте информатики университета г. Киля (Германия) в 2006-2007 гг.

Они докладывались также на следующих конференциях: между народная конференция по теоретической кибернетике (Пенза, 2005г.), конференции молодых ученых механико-математического факультета МГУ им. М.В. Ломоносова (Москва, МГУ им.Ломоносова, 2005 и 2006 гг.), конференция молодых исследователей института пульмоноло гии РАМН (Москва, ГКБ № 57, 2005г.), международные научные конфе ренции студентов, аспирантов и молодых ученых ”Ломоносов” (Москва, МГУ им.Ломоносова, 2005, 2006, 2007 и 2008 гг.), школа-симпозиум ”Био информатика в медицине” в рамках XV-го юбилейного Национально го Конгресса по болезням органов дыхания (Москва, Российская Ака демия Государственной Службы, 2005г.), международная конференция ”Дискретные модели в теории управляющих систем” (Москва, МГУ им.Ломоносова, 2006г.), научные конференции ”Ломоносовские чтения” (Москва, МГУ им.Ломоносова, 2006, 2007 и 2008 гг.), международ ная конференция ”Интеллектуальные системы и компьютерные науки” (Москва, МГУ им.Ломоносова, 2006г.), третья научная конференция сту дентов и аспирантов кафедры Математической теории интеллектуаль ных систем механико-математического факультета МГУ (Москва, МГУ им.Ломоносова, 2007г.).

Публикации по теме диссертации Основные результаты диссертации опубликованы в одиннадцати ста тьях [1][11], список которых приведен в конце автореферата.

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

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

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

Все эти свойства имеют прозрачную интерпретацию на языке автоматов и в этой главе получают исчерпывающее описание в автоматных терминах.

Легкие представляются полным дихотомическим ориентированным к корню деревом, которое называется I-деревом и обозначается D1, со сле дующими параметрами.

Пусть N - множество натуральных чисел, N0 = {0} N, Nk = {1, 2, 3,..., k} и l, l N, считается глубиной этого I-дерева. Счи тается, что ребро I-дерева D1, инцидентное корню, имеет глубину 1.

Каждое ребро из D1 разделено на n, n N, равных частей, называе мых ресничками, и занумерованных числами i, i Nn, возрастающими в направлении, обратном ориентации ребра.

Каждому ребру глубины j, j Nl, приписывается два числа 2lj b и 2lj r, где b, r N и r b, называемых емкостью и мерой переброса рес ничек ребер глубины j, соответственно.

Такое I-дерево D1 с описанными выше параметрами b, r, n и l обозна чается D1 (b, r, n, l).

С этим I-деревом связывается некоторый процесс, который называется процессом транспортировки вещества по I-дереву D1 (b, r, n, l). Он обу словлен рядом допущений.

Считается, что в D1 (b, r, n, l) заданы распределения нагрузок по всем ресничкам, учитывая, что нагрузка может быть нулевой. Пусть V сум марная нагрузка по всем ресничкам, а V максимально возможная сум марная нагрузка по всем ресничкам. V назовем объемом I-дерева (легких), а V исходным объемом загруженности I-дерева.

I-дерево D1 (b, r, n, l) с исходным объемом загруженности V обознача ется D1 (b, r, n, l;

V ).

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

Прием ресничкой вещества, имеющего массу d, d N0 и d V V, из внешней среды внутри ребра уровня j, j Nl, осуществляется по сле дующему правилу (для этого правила ориентация считается обратной к заданной).

А1 ) Если нагрузка реснички равна ее емкости, то прием вещества не осуществляется.

Б1 ) При нагрузке d1, меньшей емкости первой с такой назрузкой рес нички, она осуществляет прием вещества максимально возможной массы d2, такой что d2 min(2lj b d1, d), где 2lj b - емкость этой реснички.

В1 ) Следующая за ресничкой из Б1 ) принимает массу d3, как и в Б1 ), с заменой там d на d d2.

Г1 ) Оставшаяся масса вещества опускается до следующей реснички с большим номером в ребре, для которой не выполняется условие А1 ). Она осуществляет прием вещества по правилу В1 ) или Б1 ).

Д1 ) Если ресничка в рассматриваемом ребре является последней, не удовлетворяющей условию А1 ), то оставшаяся масса вещества делится по полам (если число нечетное, то та из частей, которая на единицу больше другой, опускается на левое ребро, при условии, что реснички поддерева, инцидентного этому ребру, могут принять это вещество, в противном слу чае оставшееся вещество передается правому ребру);

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

Е1 ) Процесс, описываемый позициями А1 ) Д1 ), начинается с ребра, которое инцидентно корню.

Переброс ресничкой вещества осуществляется на соседнюю ресничку с меньшим номером внутри ребра уровня j, j Nl, по такому правилу.

А2 ) Если следующая ресничка имеет не нулевую нагрузку, то переброс с реснички не осуществляется.

Б2 ) Если нагрузка реснички не превосходит ее меры переброса 2lj r и не выполнено условие А2 ), то перебрасывается на следующую вся нагрузка реснички и считается, что ее нагрузка становится равной нулю.

В2 ) Если на ресничке нагрузка m и m 2lj r, то она перебрасывает на следующую ресничку нагрузку 2lj r и оставляет у себя нагрузку m 2lj r.

Если ресничка в ребре последняя, то переброс нагрузки осуществляется по правилам А2 ), Б2 ), В2 ).

Г2 ) Если ребро инцидентно корню, то переброс с наименьшей по номеру реснички осуществляется в среду по правилам Б2 ) и В2 ) в предположении, что среда играет роль реснички с нулевой нагрузкой.

Д2 ) Если ребро не инцидентно корню, то есть его вершина инцидентна следующему ребру, то нагрузка с наименьшей по номеру реснички этого ребра передается наибольшей по номеру ресничке другого ребра по прави лам А2 ), Б2 ), В2 ).

Считается, что процесс транспортировки вещества по I-дереву D (b, r, n, l;

V ) осуществляется в дискретные моменты времени t = 1, 2, 3,...

В первый момент I-дерево D1 (b, r, n, l;

V ) имеет заданное распределе ние нагрузок по его ресничкам.

Ко второму моменту осуществляется прием вещества массой d(1) по правилам А1 ) E1 ), и затем осуществляется переброс нагрузок с реснички на ресничку во всем I-дереве или выброс в среду в соответствии с прави лами А2 ), Б2 ), В2 ), Г2 ), Д2 ). А если подается масса d, не превосходящая объема I-дерева, то та ее часть, которая не осела на ресничках, выбрасы вается в среду.

Если в каждый момент t = 1, 2, 3,... все реснички I-дерева D (b, r, n, l;

V ) осуществляют прием вещества нулевой массы, то такой процесс называется процессом транспортировки вещества по этому I- де реву в чистой среде. При наступлении момента t, в который все реснички I-дерева D1 (b, r, n, l;

V ) впервые стали равными нулю, считается, что про изошло полное самоочищение этого I-дерева.

Под распределением нагрузки V I-дерева D1 (b, r, n, l;

V ) понимается любое из возможных распределений нагрузок всех его ресничек таких, что суммарный объем их нагрузок равен V. Ясно, что V V, где V - объ ем I-дерева D1 (b, r, n, l) и V = 2l1 bnl. Такие распределения называются конфигурациями нагрузки V по ресничкам I-дерева D1 (b, r, n, l).

Занумеруем все реснички I-дерева D1 (b, r, n, l) таким образом, что рес ничка с номером ijk является k-ой ресничкой j-го ребра глубины i, где 1 i l, 1 j 2i1, 1 k n, а нумерация ребер одной глубины идет слева направо. Тогда в каждый момент t конфигурацию нагрузки V (t) в I-дереве D1 (b, r, n, l) можно задать набором q(t) = (q111 (t), q112 (t),..., qijk (t),..., ql2l1 n (t)), в котором каждая координата qijk (t) равна нагрузке реснички с номером l ijk в момент t, причем 0 qijk (t) 2li b и l2 n qijk (t) = V (t).

Пусть в процессе транспортировки конфигурации нагрузки V (t) в каж дый момент t изменяются по правилам A2 ) Д2 ). Тогда процесс транспор тировки можно представить некоторым конечным автономным автоматом A(b, r, n, l) с одним финальным состоянием [1]. Состояниями этого автома та являются конфигурации нагрузок V (t) в I-дереве D1 (b, r, n, l), которые называются также состояниями этого I-дерева, а законы перехода из одного состояния в другое считаются указанными выше.

Далее в параграфах этой главы изучаются свойства автомата A(b, r, n, l).

§1.1 О количестве состояний АМТ.

Если B некоторое множество, то |B| означает его мощность.

Понятие состояния I-дерева не зависит от параметра r, а полностью определяется параметрами b, n, l и распределением вещества по его рес ничкам. Учитывая отмеченную независимость понятия состояния I-дерева от r, обозначим через Q(b, n, l) множество состояний I-дерева D1 (b, r, n, l), полагая далее, что n 1.

Возникает задача нахождения величины |Q(b, n, l)|, решение которой доставляет следующее утверждение.

Теорема 1. Имеет место соотношение i |Q(b, n, l)| = l (2li b + 1)2 ·n.

i= Следствие. Справедливы следующие оценки l l l l b(2 1)·n · 2(2 l1)·n |Q(b, n, l)| (b + 1)(2 1)·n · 2(2 l1)·n.

2l при l.

Следствие. Имеет место log2 |Q(b, n, l)| §1.2 О стартовых состояниях АМТ в чистой среде.

Диаграмма Мура для автомата A(b, r, n, l) образует частичный порядок по отношению к переходу от одного сотояния в другое и допущением того, что финальное состояние никуда не переходит. Тогда последнее является наименьшим элементом этого порядка, в нем есть максимальные элементы и, вообще говоря, нет наибольшего элемента. Максимальный элемент этого частичного порядка называется стартовым состоянием. Оно характеризу ется тем, что оно переходит в какое-то состояние, а в него не переходит ни одно сотояние, то есть оно не имеет предшественников.

Следующими задачами будут выяснение того, какие состояния из Q(b, n, l) являются стартовыми и нахождение их количества. Свойство со стояния из Q(b, n, l) быть стартовым зависит от параметра r, а потому для множества всех стартовых состояний из Q(b, n, l) вводится обозначе ние St(b, r, n, l).

Для решения этих задач выделяются некоторые свойства состояний, которые названы sv -свойствами при b = r и mu -свойствами при b r, где v N3 и u N5. В первом случае состояния допускают локальную характериацию через нагрузки ресничек, а во втором она доопределяет ся возможным продолжением конфигураций в виде загруженных цепей.

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

Пусть S = {sv |v N3 } и M = {mv |v N5 }. Класс всех состояний q из Q(b, n, l) с sv -свойством при sv S обозначается через Ksv, а класс всех состояний q из Q(b, n, l) с mv -свойством при mv M через Kmv.

Теорема 2. При b = r выполнено Ks1, если l = 1 и n = 2, (1) Ks1 Ks2, если l = 1 и n 2, (2) St(b, r, n, l) = Ks1 Ks2 Ks3, если l 2 и n 2, (3) где Ksv = при всех v из N3 и если j {(2), (3)}, то для элементов строки (j) при v = u выполнено Ksv Ksu.

Теорема 3. При b r выполнено Km1, если l = 1 и n = 2, (1) Km1 Km2, если l = 1 и n 2, (2) St(b, r, n, l) = vN5 Kmv, если l 2 и n 2, (3) где Kmv = при всех v из N5 и если j {(2), (3)}, то для элементов строки (j) при v = u выполнено Kmv Kmu.

Теорема 4. Имеет место |St(b, r, n, l)| C 1, |Q(b, n, l)| (2l1 )2 ·r·b l 2l1 r 2b где C = 2l1 b+1 при b = r, C = при r b 2r и C = (2l1 b+1)2 2l1 b+ при b 2r.

Следствие. Имеет место при l :

а) |St(b, r, n, l)| |Q(b, n, l)|, если b = r, б) |St(b, r, n, l)| |Q(b, n, l)|, если b r.

§1.3 О переводимости состояний АМТ в чистой среде.

Диаграмма Мура автомата A(b, r, n, l) является ориентированным к корню q деревом. В состояние q, которое называется финальным, перехо дят все остальные состояния. Финальному состоянию соответствует такая конфигурация дерева легких, при которой нагрузки всех ресничек I-дерева D1 (b, r, n, l) равны нулю.

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

Пусть I-дерево D1 (b, r, n, l) находится в состоянии q. Тогда через q(t) обозначено состояние этого I-дерева в момент t, полагая, что в первый момент оно находится в состоянии q, то есть q(1) = q.

Состояние q 1 I-дерева D1 (b, r, n, l) переводимо в состояние q 2 это го I-дерева, если для некоторого t, такого что t 1, будет выполнено q 1 (t) = q 2. Очевидно, такое t единственное.

В состоянии q ресничка с номером ijk I-дерева D1 (b, r, n, l) при qijk называется характеристической ресничкой этого состояния, если для лю бой другой реснички с номером i j k со свойством qi j k 0 справедливо i i и при i = i выполнено k k.

Пусть состояние q I-дерева D1 (b, r, n, l) имеет s характеристических ресничек с номерами i1 j1 k1, i2 j2 k2,..., is js ks, где s N. Из определе ния характеристических ресничек вытекает, что i1 = i2 = · · · = is и k1 = k2 = · · · = ks, то есть все характеристические реснички состояния q принадлежат ребрам j1, j2,..., js одной и той же глубины I-дерева, ко торая обозначена через i, и имеют один и тот же номер внутри ребер этой глубины, который обозначен через k. Следовательно, множество характе ристических ресничек состояния q можно задать их номерами следующим образом: {ij1 k, ij2 k,..., ijs k}, где s N2i1. Множество ребер, которым принадлежат характеристические реснички состояния q обозначено Js, то есть Js = {j1, j2,..., js }, а множество характеристических ресничек состо яния q обозначено Nq (i, k, Js ).

2li Величина Vq(t), равная l n k=1 qijk (t), называется объемом со i=1 j= стояния q(t).

Состояние меньшего объема не переводимо в состояние большего объе ма. Поэтому рассматривается задача о переводимости состояний q 1 в q 2 из Q(b, n, l) в случае, когда Vq1 Vq2.

Задача о переводимости состояний q 1 в q 2 в случае, когда Vq1 = 0 и Vq2 = 0, тривиальна, так как q 1 и q 2 равны и совпадают с финальным состоянием q, которое переводимо в себя за любое время.

В случае, когда Vq1 0 и Vq2 = 0, задача о переводимости этих состо яний легко решается. В этом случае q 2 = q, и, очевидно, q 1 переводимо в q2.

Далее решается задача о переводимости состояния q 1 в состояние q 2 в случае, когда Vq1 0 и Vq2 0.

Теорема 5. Если {q 1, q 2 } Q(b, n, l), q 2 St(b, r, n, l), Vq1 = Vq2, Vq1 0, / Vq2 0, Nq1 (i1, k1, Js1 ) и Nq2 (i2, k2, Js2 ) множества характеристиче ских ресничек состояний q 1 и q 2, соответственно, то q 1 переводимо в q точно тогда, когда выполнены следующие условия:

а) i1 i2 и при i1 = i2 имеет место k1 k2, б) q 1 ((i1 i2 )n + k1 k2 + 1) = q 2.

Теорема 5 решает задачу о переводимости двух любых состояний q 1 в q из Q(b, n, l) в случае, когда объемы этих состояний равны. Далее рассмат ривается та же задача в случае, когда объемы этих состояний различны, то есть Vq1 Vq2.

Главная идея решения этой задачи заключается в том, чтобы найти момент t = t(q 1, q 2 ), такой что Vq1 (t1) Vq2 и Vq1 (t) Vq2. Если в момент t будет выполнено Vq1 (t) = Vq2, то используется теорема 5 для решения этой задачи. Если же в момент t выполняется Vq1 (t) Vq2, то заключается, что 1 q не переводимо в q.

Теорема 6. Если {q 1, q 2 } Q(b, n, l), q 2 St(b, r, n, l), Vq1 Vq2, Vq1 0, / Vq2 0, Nq1 (i1, k1, Js1 ), Nq2 (i, k, Js ) и Nq1 (t) (it, kt, Jst) множества харак теристических ресничек состояний q, q 2 и q 1 (t), соответственно, то q переводимо в q точно тогда, когда выполнены следующие условия:

а) Vq1 (t) = Vq2, б) it i и при it = i имеет место kt k, 1 в) q (t + (it i)n + kt k) = q.

§1.4 О функции Шеннона процесса полного самоочищения и о глубине диаграммы Мура АМТ в чистой среде.

Вводится функция L(b, r, n, l, V ) для I-дерева D1 (b, r, n, l;

V ), которая равна наибольшему из времен, за которое происходит полное самоочище ние D1 (b, r, n, l;

V ) при произвольном начальном распределении загрузки V этого I-дерева. Эту функцию обычно называют сложностной функцией Шеннона.

Теорема 7. Функция L(b, r, n, l, V ) в зависимости от соотношений па раметров b, r, n, l и V принимает следующие значения:

b 1) если (2l 1)bn V V, то L(b, r, n, l, V ) =] r [(2nl 1);

2) если 0 V (2l 1)bn, то i) при r = 1 имеем:

а) если V bn, то если l = 1 и n =] Vb [, V + b(n 1), L(b, 1, n, l, V ) = 2V ] Vb [+nl 1, иначе;

б) если bn V bn + (l 1)n, то L(b, 1, n, l, V ) = V + n(l + b 1) 1;

в) если V bn + (l 1)n, то bh если k3 = 1 и h3 = 1, ] 2l1 [+2b(nl1), L(b, r, n, l, V ) = bh [+(b1)(n(lk3 +1)h3 )+nl 2, иначе;

2 ] lk ii) при r 1 имеем:

а) если V nl, то L(b, r, n, l, V ) = V + nl 1;

б) если V nl, то bh если k3 = 1 и h3 = 1, b ] 2l1 r [+2] r [(nl1), L(b, r, n, l, V ) = bh ] lk [+(] r [1)(n(lk3 +1)h3 )+nl 2, иначе;

b 3r где nl(2lk3 1)(b1)n h3 = n] V V nl k3 = 1 + [l log2 ( (b1)n + 1)], [+1, 2lk3 (b1) bh3 = V nl (2lk3 1)(b 1)n 2lk3 (b 1)(n h3 ) + 1.

Как отмечалось выше, диаграмма Мура автомата A(b, r, n, l) является деревом, глубина которого считается глубиной G(A(b, r, n, l)) этой диаграм мы.

b Следствие. G(A(b, r, n, l)) =] r [(2nl 1).

Далее находится среднее значение по всем функциям L(b, r, n, l, V ) для всевозможных загрузок V, то есть величина V Lcp. (b, r, n, l) = · L(b, r, n, l, V ).

V V = Пусть L(b, r, n, l) = max1V V L(b, r, n, l, V ), то есть L(b, r, n, l) рав на минимально достаточному времени, за которое происходит полное са моочищение I-дерева D1 (b, r, n, l) при произвольной его загрузке V. Так как дольше всех будет очищаться полностью загруженное I-дерево, то из b теоремы 7 следует, что L(b, r, n, l) =] r [(2nl 1).

Теорема 8. Для Lcp. (b, r, n, l) выполнено b Lcp. (b, r, n, l) 2n] r [l при l.

Следствие. Lcp. (b, r, n, l) L(b, r, n, l) при l.

Во второй главе формализация механизма транспортировки вещества по легким из первой главы распространяется на случай загрязненной ста ционарной во времени среды.

В этой главе процесс транспортировки вещества по легким представим некоторым конечным автоматом Aa (b, r, n, l) со входом. Входной алфавит автомата Aa (b, r, n, l) состоит только из одной буквы a, где a NV, то есть он является автономным. На вход такого автомата могут подаваться как слова, так и сверхслова.

Далее в параграфах этой главы изучаются свойства автомата Aa (b, r, n, l).

§2.1 О финальных состояниях АМТ в загрязненных стацио нарных средах.

Состояние q из Q(b, n, l) называется финальным для автомата Aa (b, r, n, l), если оно переходит только в себя.

Главными задачами этого параграфа являются описание всех финаль ных состояний автомата Aa (b, r, n, l) для каждого a из NV и указание их числа.

Пусть F in(b, r, n, l, a) множество финальных состояний автомата Aa (b, r, n, l).

Через qa обозначено состояние автомата Aa (b, r, n, l), при котором все реснички, кроме реснички с номером 111, имеют нагрузки, равные своей емкости, а ресничка с номером 111 имеет нагрузку 2l1 (b r).

При a 2l1 r автомат Aa (b, r, n, l) имеет только одно состояние, которое переходит в себя, и оно совпадает с qa. Таким образом, если a 2l1 r, то F in(b, r, n, l, a) = {qa }.

При a 2l1 r все финальные состояния описываются так.

Теорема 9. Для q из Q(b, n, l) при a 2l1 r выполнено q F in(b, r, n, l, a) точно тогда, когда для q одновременно выполнены следующие условия:

а) q111 2l1 (b r) при a = 2l1 r и q111 = 0 при a 2l1 r, б) для любого номера ijk, такого что ijk = 111, ijk = ljn при j N2l и qijk = 0, при k n имеет место qij(k+1) = 0, а при k = n имеет место q(i+1)j 1 = q(i+1)j 1 = 0, где ребра j и j уровня i + 1 инцидентны ребру j уровня i.

Теорема 10. Если a 2l1 r, то log2 |F in(b, r, n, l, a)| 2l при l.

Следствие. Диаграмма Мура автомата Aa (b, r, n, l) предсталяет собой дерево при a 2l1 r и лес при a 2l1 r.

§2.2 О стартовых состояниях АМТ в загрязненных стацио нарных средах.

Состояние q из Q(b, n, l) называется стартовым для автомата Aa (b, r, n, l), если в него не переходит ни одно из состояний множества Q(b, n, l).

Входная буква a при заданных l и b представима в виде a = k ·2l1 b+k, где k 2l1 b. Если a 2l1 r, то k 0 при b r и k 0 при b = r.

Пусть Da (b, r, n, l) неполное поддерево I-дерева D1 (b, r, n, l), такое k что оно имеет глубину ] n [ в случае, когда либо n не делит k нацело, либо n k делит k нацело и при этом k = 0, или глубину n + 1, когда либо n делит k нацело и k 0, либо k = 0. При этом количество ресничек на последнем k (нижнем) уровне этого поддерева равно либо k [ n ] · n, если k = 0, либо k k [ n ] · n + 1, если k 0.

Это неполное поддерево Da (b, r, n, l) загружается таким образом, как если бы к полностью пустому этому поддереву применился один шаг про цесса транспортировки в стационарной загрязненной среде подачей на вход буквы a, где a 2l1 r. Поддерево Da (b, r, n, l), загруженное таким обра зом, обозначается Da (b, r, n, l).

Итак, при a 2l1 r и b = r для Da (b, r, n, l) выполнено: ресничка с номером 111 имеет нулевую нагрузку, все остальные реснички кроме, быть может, самых нижних ресничек имеют нагрузки, равные своим емкостям, а суммарная нагрузка по всем нижним ресничкам равна k.

При a 2l1 r и b r для Da (b, r, n, l) выполнено: если k = 0, то рес ничка с номером 111 имеет нагрузку a 2l1 r, а если k 0, то ресничка с номером 111 имеет нагрузку 2l1 (b r) и все остальные реснички кро ме, быть может, самых нижних ресничек имеют нагрузки, равные своим емкостям, а суммарная нагрузка по всем нижним ресничкам равна k.

Загруженное некоторым образом поддерево Da (b, r, n, l) I-дерева D1 (b, r, n, l), находящегося в некотором состоянии q, поресничково меньше 1 загружено, чем Da (b, r, n, l) (обозначение Da (b, r, n, l) Da (b, r, n, l)), если нагрузка хотя бы одной реснички поддерева Da (b, r, n, l) I-дерева D1 (b, r, n, l) в состоянии q меньше соответствующей ей реснички поддере ва Da (b, r, n, l) этого I-дерева.

Состояние q из Q(b, n, l) при b = r обладает:

sa -свойством, если при данном q для поддерева Da (b, r, n, l) I-дерева D1 (b, r, n, l) выполнено Da (b, r, n, l) Da (b, r, n, l);

1 s1 -свойством, если при данном q выполнено q111 0.

Состояние q из Q(b, n, l) при b r обладает:

ma -свойством, если при данном q для поддерева Da (b, r, n, l) I- де рева D1 (b, r, n, l) выполнено Da (b, r, n, l) Da (b, r, n, l).

1 Класс всех состояний из Q(b, n, l) с sa -свойством обозначен через Ksa, класс всех состояний из Q(b, n, l) с s1 -свойством обозначен через Ks1, а класс всех состояний из Q(b, n, l) с ma -свойством через Kma.

Пусть St(b, r, n, l, a) множество стартовых состояний I-дерева D (b, r, n, l) в стационарной среде с входным алфавитом {a}, где a NV.

Теорема 11. Справедливы положения:

1) Если a 2l1 r, то имеет место:

а) St(b, r, n, l, a) = Ksa St(b, r, n, l) при b = r, б) St(b, r, n, l, a) = Kma St(b, r, n, l) при b r.

2) Если a 2l1 r, то имеет место:

а) St(b, r, n, l, a) = Ks1 St(b, r, n, l) при b = r, б) St(b, r, n, l, a) = St(b, r, n, l) при b r.

При этом Ksa =, Ks1 =, Kma =, Ksa St(b, r, n, l), Kma St(b, r, n, l) и Ks1 St(b, r, n, l).

Теорема 12. Имеет место при l :

а) St(b, r, n, l, a) Q(b, n, l), если b = r, б) St(b, r, n, l, a) Q(b, n, l), если b r.

§2.3 О переводимости состояний АМТ в загрязненных стаци онарных средах и о глубине диаграммы Мура АМТ.

Здесь рассматривается задача переводимости друг в друга состояний автомата Aa (b, r, n, l).

Понятие переводимости состояний в загрязненной среде аналогично случаю чистой среды.

По следствию из теоремы 10 при a 2l1 r автомат Aa (b, r, n, l) имеет только одно финальное состояние qa. В этом случае решение проблемы переводимости доставляет следующее утверждение.

Теорема 13. Если a 2l1 r, {q 1, q 2 } Q(b, n, l), q 2 = qa и q 2 St(b, r, n, l, a), то q 1 переводимо в q 2 точно тогда, когда выполнены / следующие условия:

а) Vq2 Vq1, V 2 V б) q 1 (] a2l1 r [+1) = q 2.

q q Следствие 1. Любое состояние q из Q(b, n, l) автомата Aa (b, r, n, l) в случае, когда Vq Vqa, переходит в qa за время 1, в противном случае за Vqa V время ] a2l1qr [.

Следствие 2. В диаграмме Мура автомата Aa (b, r, n, l) все состояния из Q(b, n, l), имеющие одинаковый объем, имеют путь до qa одинаковой длины.

По следствию из теоремы 10 диаграмма Мура автомата Aa (b, r, n, l) при a 2l1 r является деревом, глубина которого считается глубиной G(Aa (b, r, n, l)) этой диаграммы.

l Следствие 3. Если a 2l1 r, то G(Aa (b, r, n, l)) =] 2 a2l1 r [.

(bnlr) Далее рассматривается случай, когда 0 a 2l1 r. По следствию из теоремы 10 в этом случае диаграмма Мура автомата Aa (b, r, n, l) пред ставляет собой лес, финальные состояния которого образуют множество F in(b, r, n, l, a). В связи с этим возникает задача о переводимости q из Q(b, n, l) в qa из F in(b, r, n, l, a).

Цепь с номером i (цепи I-дерева D1 (b, r, n, l), идущие от листа до кор ня, занумерованы слева направо) обозначается Ci, где i Nl1. Рассматривается некоторое состояние q I-дерева D1 (b, r, n, l). Конфи гурация нагрузок цепи Ci (ее состояние) в этом состоянии обозначается qci.

Цепь I-дерева D1 (b, r, n, l), функционирующая отдельно от этого I- де рева, называется изолированной цепью.

Финальным состоянием изолированной цепи Ci, находящейся в состо янии qci, называется такое ее состояние qci (T ), что для любого t 0 вы полнено qci (T + t) = qci (T ).

q Пусть TCi - время перехода изолированной цепи Ci I-дерева D1 (b, r, n, l), находящегося в состоянии q(2), в финальное состояние.

q Рекуррентно определяемая величина TCi здесь в явном виде не приво дится из-за громоздкости ее представления.

Теорема 14. Если 0 a 2l1 r, q Q(b, n, l) и qa F in(b, r, n, l, a), то q q переводимо в qa точно тогда, когда q(T ) = qa, где T = maxCi,iN2l1 TCi +2.

Теорема 14 для диаграммы Мура автомата Aa (b, r, n, l) при 0 a 2l1 r дает описание всех деревьев, корнями которых яв ляются элементы множества F in(b, r, n, l, a).

Решение задачи о переводимости двух любых состояний q 1 и q 2 из Q(b, n, l) автомата Aa (b, r, n, l) при 0 a 2l1 r доставляет следующее утверждение.

Теорема 15. Если 0 a 2l1 r, {q 1, q 2 } Q(b, n, l), то q 1 перево димо в q 2 точно тогда, когда существует натуральное T из отрезка q [1;

maxCi,iN2l1 TCi + 2], такое что q 1 (T ) = q 2.

По следствию из теоремы 10 диаграмма Мура автомата Aa (b, r, n, l) при 0 a 2l1 r представляет собой лес. Наибольшая глубина дерева из всех деревьев леса называется глубиной этой диаграммы и обозначается G(Aa (b, r, n, l)).

ln Теорема 16. Если 0 a 2l1 r, то G(Aa (b, r, n, l)) = 2ln 4.

b ]r[ В третьей главе формализация транспортировки из предыдущих глав распространяется на случай загрязненной переменной во времени среды.

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

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

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

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

§3.1 О свойствах диаграммы Мура АМТ в загрязненных нестационарных средах.

Здесь рассматривается I-дерево D1 (b, r, n, l), функционирующее в пе ременной по загрязнению во времени среде.

Переменная среда кодируется словами m = a(1)a(2)... a(t)... a(m) из алфавита {0, 1, 2,..., V }, где буква a(t) - количество вещества, которое поcтупает в I-дерево в момент t.

Конфигурации I-дерева D1 (b, r, n, l) под воздействием входных букв будут меняться по правилам А1 Д2, описанным в первой главе.

Таким образом, так же как и первых двух главах, процесс транспорти ровки вещества по I-дереву D1 (b, r, n, l) в загрязненной нестационарной среде можно представить некоторым конечным уже неавтономным авто матом A(b, r, n, l), множество состояний которого совпадает с множеством Q(b, n, l), с входным алфавитом {0, 1, 2,..., V } и следующей функцией пе рехода состояний: если в момент t автомат A(b, r, n, l) находится в состоя нии q и на вход в этот момент подается буква a(t), то в диаграмме Мура автомата Aa(t) (b, r, n, l) то состояние q, в которое переходит q, является тем состоянием, в которое перейдет автомат A(b, r, n, l) из q под воздействием буквы a(t), то есть q(t + 1) = q.

Таким образом, диаграмма Мура автомата A(b, r, n, l) является ”склей кой” диаграмм Мура автоматов в стационарных средах.

Диаграмма Мура такого автомата A(b, r, n, l) представляет собой ори ентированный, вообще говоря, не древовидный граф со следующими свой ствами:

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

б) граф не сильно связный, так как стартовые состояния не переводимы друг в друга;

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

г) множество стартовых состояний этой диаграммы совпадает с множе ством стартовых состояний автомата A(b, r, n, l) в чистой среде, то есть с множеством St(b, r, n, l);

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

В связи с описанным выше оказываются решенными такие задачи, как время наискорейшего перехода в стабилизацию I-дерева D1 (b, r, n, l) под воздействием входных слов и, более того, время наискорейшего перехода в стабилизацию I-дерева D1 (b, r, n, l) при произвольных словах при задан ном подалфавите.

§3.2 О допустимых входных словах и сверхсловах для АМТ в загрязненных нестационарных средах.

Объем загруженности I-дерева D1 (b, r, n, l;

V ), равный ]V [, где 0 1, называется предельным порогом загруженности этого I- дерева. Далее пишется V вместо ]V [, считая, что V N.

Пусть Am множество всех слов m, где a(t) NV {0} при t Nm, на котором вводится отношение частичного порядка, полагая m m, если a(t) a (t) для всех t из Nm.

Для I-дерева D1 (b, r, n, l;

V ) слово m из Am называется допустимым, если при подаче на него буквы a(t) из m в каждый момент времени t все гда выполнено a(t)+V (t) V, где V (t) объем загруженности I- дерева D1 (b, r, n, l;

V ) в момент t, t Nm. Такое слово называется предельно до пустимым для I-дерева D1 (b, r, n, l;

V ), если не существует допустимого слова m из Am такого, что m m и m = m.

Пусть A = Am, а A множество всех сверхслов (то есть слов бес m= конечной длины) = a(1)a(2)... a(t)..., где a(t) N0, на котором вво дится отношение частичного порядка, полагая, если a(t) a (t) для всех t из N.

Для I-дерева D1 (b, r, n, l;

V ) сверхслово из A называется допусти мым, если при подаче на него буквы a(t) из в каждый момент времени t всегда выполнено a(t)+V (t) V. Такое сверхслово называется предельно допустимым для I-дерева D1 (b, r, n, l;

V ), если не существует допустимо го сверхслова из A такого, что и =.

Ясно, что предельно допустимые сверхслова существуют. Например, сверхслово (V V )V V... V... при V r является предельно до пустимым.

Более того, можно показать, что для всякого допустимого сверхслова найдется предельно допустимое такое, что.

Множество A = A A называется множеством квазислов. Понятия допустимости и предельной допустимости распространяются на квазисло ва.

Здесь главным является описание всех квазислов, как допустимых, так и не допустимых.

Пусть v(t) нагрузка реснички с номером 111 в момент t.

Теорема 17. Слово a(1)a(2)... a(t)... a(m) при m 1 является предель но допустимым для дерева D1 (b, r, n, l;

V ) точно тогда, когда для него выполнены следующие рекуррентные соотношения:

а) для t = 1 выполнено l [2 r, V ], если V = 0, {0} [2l1 r, V V ], если v(1) = 0 и V 0, a(1) [0, V V ], если v(1) 2l1 r, l [2 r v(1), V V ], если 0 v(1) 2l1 r;

б) для всех t = 2,..., m 1 имеет место [0, V V t1 a(i) + 2l1 rk(t)], если v(t) 2l1 r, i= l1 t [2 r v(t), V V a(i) + 2l1 rk(t)], i= если 0 v(t) 2l1 r, t a(t) {0} [2l1 r, V V a(i) + 2l1 rk(t)], i= если v(t) = 0 и V (t) = 0, t l [2 r, V V a(i) + 2l1 rk(t)], i= если v(t) = 0 и V (t) = 0, где k(1) = 0, k(t) = k(t 1) + p(t 1), причем 0, если v(t 1) = 0, a(t 1) = 0 и V (t 1) = 0, p(t 1) = 1, иначе;

t a(i) + 2l1 rk(m).

в) для t = m выполнено a(m) = V V i= Для предельно допустимого слова m его буква a(t) называется мак симально возможной, если после подачи вещества объема a(t) в I-дерево D1 (b, r, n, l;

V ) в этот момент времени общий объем нагрузки V (t) дан ного I-дерева будет в точности равен V.

Понятие максимально возможной буквы распространяется на предель но допустимые сверхслова. Буква a(t), t N, сверхслова, называется максимально возможной, если после подачи вещества объема a(t) в I-дерево D1 (b, r, n, l;

V ) в этот момент времени общий объем нагрузки V (t) дан ного I-дерева будет в точности равен V.

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

Суффиксы предельно допустимых квазислов, последняя буква которых является максимально возможной, называются предельными суффиксами.

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

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

Ясно, что если каждый префикс сверхслова допустим, то это сверхслово является допустимым.

Теорема 18. Все минимальные предельные префиксы и суффиксы длины m, m 1, являются предельно допустимыми словами a(1)a(2)... a(t)... a(m) длины m, где a(t) определяются рекуррентно так:

а) для t = 1 выполнено l [2 r, V ], если V = 0, {0} [2l1 r, V V ], если v(1) = 0 и V 0, a(1) [0, V V ], если v(1) 2l1 r, l [2 r v(1), V V ], если 0 v(1) 2l1 r;

б) для всех t = 2,..., m 1 имеет место [0, V V t1 a(i) + 2l1 rk(t) 1], если v(t) 2l1 r, i= l1 t [2 r v(t), V V a(i) + 2l1 rk(t) 1], i= если 0 v(t) 2l1 r, t a(t) {0} [2l1 r, V V a(i) + 2l1 rk(t) 1], i= если v(t) = 0 и V (t) = 0, t l [2 r, V V a(i) + 2l1 rk(t) 1], i= если v(t) = 0 и V (t) = 0, где k(1) = 0, k(t) = k(t 1) + p(t 1), причем 0, если v(t 1) = 0, a(t 1) = 0 и V (t 1) = 0, p(t 1) = 1, иначе;

t a(i) + 2l1 rk(m).

в) для t = m выполнено a(m) = V V i= Пусть P (b, r,, V ) множество всех минимальных предельных пре фиксов для I-дерева D1 (b, r, n, l;

V ) с предельным порогом загруженно сти V, а S(b, r,, V 2l1 r) множество всех минимальных предельных суффиксов для I-дерева D1 (b, r, n, l;

V 2l1 r) с предельным порогом загруженности V.

Вводится операция конкатенации · над словами и сверхсловами. Если A, а A A, то выражение m · будет определять слово или m сверхслово, получаемое приписыванием к m последовательно справа всех букв из.

Если C A, а D A A, то полагается C · D = ·.

C D Через P m (b, r,, V ) обозначено множество всех минимальных пре дельных префиксов длины m для I-дерева D1 (b, r, n, l;

V ) с предель ным порогом загруженности V, а через S m (b, r,, V 2l1 r) мно жество всех минимальных предельных суффиксов длины m для I-дерева D1 (b, r, n, l;

V 2l1 r) с предельным порогом загруженности V.

Пусть l S i (b, r,, V 2l1 r), S(b, r,, V 2 r) = i= P i (b, r,, V ).

P (b, r,, V ) = i= Пусть e пустое слово, для которого считаются выполненными для любого из S(b, r,, V 2l1 r) соотношения e · = · e =. Полагается, что e S(b, r,, V 2l1 r).

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

Пусть D1 (b, r, n, l, V, V ) множество всех предельно допустимых квазислов для I-дерева D1 (b, r, n, l;

V ).

Теорема 19. Имеет место ) = P (b, r,, V ) · S(b, r,, V 2l1 r) · {e, 2l1 r} D1 (b, r, n, l, V, V S(b, r,, V 2l1 r) · {e, 2l1 r}.

Следствие 1. Мощность множества всех предельно допустимых сверх слов для I-дерева D1 (b, r, n, l;

V ) континуальна.

m Пусть TD1 (V, b, r, n, l, V ) множество всех предельно допустимых слов длины m для I-дерева D1 (b, r, n, l;

V ), Qm1 (V, b, r, n, l, V ) мно D жество всех допустимых слов длины m для I-дерева D1 (b, r, n, l;

V ).

Следствие 2. Для m из Am выполнено m Qm1 (V, b, r, n, l, V ) точно D тогда, когда существует m из TD1 (V, b, r, n, l, V ), что m m.

m Пусть Q 1 (V, b, r, n, l, V ) множество всех допустимых сверхслов D для I-дерева D1 (b, r, n, l;

V ) и TD1 (V, b, r, n, l, V ) множество всех пре дельно допустимых сверхслов для этого I-дерева.

Следствие 3. Для из A выполнено Q 1 (V, b, r, n, l, V ) точно D тогда, когда существует из TD1 (V, b, r, n, l, V ), что.

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

§3.3 Об автоматной представимости допустимых входных слов и сверхслов для АМТ в загрязненных нестационарных сре дах.

Через QD1 (V, b, r, n, l, V ) обозначено множество всех допустимых слов для I-дерева D1 (b, r, n, l;

V ), а через TD1 (V, b, r, n, l, V ) - множе ство всех предельно допустимых слов для I-дерева D1 (b, r, n, l;

V ).

Теорема 20. Множества QD1 (V, b, r, n, l, V ) и TD1 (V, b, r, n, l, V ) ре гулярны, а множества Q 1 (V, b, r, n, l, V ) и TD1 (V, b, r, n, l, V ) обще D регулярны.

m Теорема 21. Для |TD1 (V, b, r, n, l, V )| выполнены следующие соотноше ния:

а) если V 2l1 r, то |TD1 (V, b, r, n, l, V )| = 1, m б) если V 2l1 r, то log2 |TD1 (V, b, r, n, l, V )| m при m.

m Благодарности Я выражаю глубокую благодарность своему научному руководите лю академику Кудрявцеву Валерию Борисовичу за научное руководство, постановку задач и помощь в работе, академику Чучалину Александру Григорьевичу за консультации и обсуждение работы. Я также благодарю коллектив кафедры Математической теории интеллектуальных систем за творческую атмосферу, способствующую исследовательской работе.

Работы по теме диссертации [1] Гераськина Ю. Г. Об одной автоматной модели в биологии. Дискрет ная математика 2007, Т. 19, вып. 3, стр. 122-139.

[2] Гераськина Ю. Г. О стартовых состояниях автоматной модели легких в чистой среде. Дискретная математика 2008, Т. 20, вып. 3, стр. 119- 135.

[3] Гераськина Ю. Г. Модель самоочищения легочных структур. Интел лектуальные системы 2002-2003, Т. 7, вып. 1-4, стр. 41-54.

[4] Гераськина Ю. Г. Модель процесса дыхания живых организмов. Интел лектуальные системы 2004, Т. 8, вып. 1-4, стр. 429-456.

[5] Гераськина Ю. Г. Об автоматной модели самоочищения легких. Ма териалы IX Международной конференции ”Интеллектуальные системы и компьютерные науки” 2006, стр. 92-95.

[6] Гераськина Ю. Г. О времени самоочищения легочных структур в допу стимых средах. Сборник статей молодых ученых факультета ВМиК МГУ 2006, вып. 3, стр. 50-54.

[7] Гераськина Ю. Г. Об одной модели функционирования легких. Интел лектуальные системы 2007, Т. 11, вып. 1-4, стр. 161-170.

[8] Yu. G. Geraskina One automaton model in biology. Discrete Mathematics and Applications 2007, Vol. 17, Num.4, pp. 375-394.

[9] Гераськина Ю. Г. О переводимости состояний автоматной моде ли легких в чистой среде. Научный вестник ”Ломоносов” 2008, вып. 1, стр. 146 - 154.

[10] Гераськина Ю. Г. Автоматная модель транспортировки вещества по легким в загрязненных стационарных средах. Интеллектуальные системы 2008, Т. 12, вып. 1-2, стр. 151-179.

[11] Yu. G. Geraskina On start states of an automaton model of lung in pure environment. Discrete Mathematics and Applications 2008, Vol. 18, Num.5, pp. 517-534.