Автоматная модель одной транспортной системы в биологии тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В. ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 519.71

Гераськина Юлия Геннадьевна

АВТОМАТНАЯ МОДЕЛЬ ОДНОЙ ТРАНСПОРТНОЙ СИСТЕМЫ В БИОЛОГИИ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

ии3465308

МОСКВА - 2009

003465308

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

Научный руководитель — доктор физико-математических наук, профессор

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

Александр Григорьевич Чучалин Официальные оппоненты:

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

Ведущая организация — Московский Энергетический Институт

(Технический университет)

Защита диссертации состоится 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-х годов прошлого столетия. Актуальность изучения их функционирования с годами нарастает в виду все большего ухудшения экологической обстановки.

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

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

1 A.Guyton The relationship of cardiac output and arteria ! pressure control, Circulation, Vol. 64, 6, 1881, pp. 1079-1088.

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

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

4I. 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.

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

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

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

425-432.

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

Цель работы

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

Структура и объем диссератации

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

Научная новизна

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

2. Рассмотрен случай функционирования AMT в чистой среде. Для соответствующего автономного автомата оценено число состояний в нем. Описаны стартовые состояния и найдено их число. Найдена средняя глубина диаграммы Мура AMT, указан критерий перехода одного состояния в другое и оценено время такого перехода. Найдено время полного самоочищения.

3. Рассмотрен случай функционирования AMT в загрязненной, но стационарной среде, которая также является автономным автоматом. Для

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

4. Рассмотрен общий случай функционирования AMT в нестационарной среде. Для этого автомата, который уже не является автономным, с помощью рассмотренных случаев 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], список которых приведен в конце автореферата.

Краткое содержание работы

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

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

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

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

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

Пусть N - множество натуральных чисел, N0 = {0}- и К,

= {1,2,3,..., и I, I £ Н, считается глубиной этого 1-дерева. Считается, что ребро 1-дерева инцидентное корню, имеет глубину 1.

Каждое ребро из О-1 разделено на тг, п Е М, равных частей, называемых ресничками, и занумерованных числами г, г 6 М„, возрастающими в направлении, обратном ориентации ребра.

Каждому ребру глубины з 6 М/, приписывается два числа и 2'"■'г, где 6, г 6 N и г < 6, называемых емкостью и мерой переброса ресничек ребер глубины соответственно.

Такое 1-дерево с описанными выше параметрами Ь,г,п и I обозначается г, п, I).

С этим 1-деревом связывается некоторый процесс, который называется процессом транспортировки вещества по 1-дереву г, п, I). Он обу-

словлен рядом допущений.

Считается, что в О-1 (6, г, п, I) заданы распределения нагрузок по всем ресничкам, учитывая, что нагрузка может быть нулевой. Пусть V' — суммарная нагрузка по всем ресничкам, а V — максимально возможная суммарная нагрузка по всем ресничкам. V назовем объемом 1-дерева (легких), а V' — исходным объемом загруженности 1-дерева.

1-дерево г, п,1) с исходным объемом загруженности V' обознача-

ется /Г1 {Ь, г, п, I] V').

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

Прием ресничкой вещества, имеющего массу й, (I 6 N0 и й ^ V — V', из внешней среды внутри ребра уровня j, ] М;, осуществляется по следующему правилу (для этого правила ориентация считается обратной к заданной).

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

Б1) При нагрузке (1\, меньшей емкости первой с такой назрузкой реснички, она осуществляет прием вещества максимально возможной массы ¿2, такой что ¿2 ^ тт(21-^Ь — ¿1 ,<$), где 2емкость этой реснички.

В1) Следующая за ресничкой из Б1) принимает массу (¿3, как и в Б)), с заменой там й на й — <12.

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

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

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

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

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

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

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

В2) Если на ресничке нагрузка т и т > 2'";г, то она перебрасывает на следующую ресничку нагрузку 2и оставляет у себя нагрузку т —

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

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

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

Считается, что процесс транспортировки вещества по 1-дереву В~1{Ъ,г,п,1\У) осуществляется в дискретные моменты времени Ь= 1,2,3,...

В первый момент 1-дерево г, га,/; V') имеет заданное распределе-

ние нагрузок по его ресничкам.

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

Если в каждый момент £ = 1,2,3,... все реснички 1-дерева ,г,п,1-,У) осуществляют прием вещества нулевой массы, то такой процесс называется процессом транспортировки вещества по этому I- дереву в чистой среде. При наступлении момента в который все реснички 1-дерева -О-1 (6, г, п, /; V') впервые стали равными нулю, считается, что про-

изошло полное самоочищение этого 1-дерева.

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

Занумеруем все реснички I-дерева г, тг, I) таким образом, что рес-

ничка с номером ijk является к-ой ресничкой j-го ребра глубины г, где 1 <i<l, 1 <j< 2'-1, 1 < к < п, а нумерация ребер одной глубины идет слева направо. Тогда в каждый момент t конфигурацию нагрузки V'(t) в I-дереве D~l(b,r,n,l) можно задать набором

q(t) = (gni(i). 9И2 (t), ■■■, Qijk{t),qw-in(t)),

в котором каждая координата qijk(t) равна нагрузке реснички с номером

ijk в момент t, причем 0<qijk(t)<2l~'b и Х^ш " 4ijk(t) = V'(t).

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

Далее в параграфах этой главы изучаются свойства автомата А(Ъ, г,п,1).

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

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

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

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

Теорема 1. Имеет, место соотношение

|Q(6,n,0| = П|=1(2'-Ч>+ 1)2<~'-п.

Следствие. Справедливы следующие оценки

Ь(2'-1).П . 2(2<-i-i).n < |g(6>n>i)| < (6 + • 2t21-1-1) «.

Следствие. Имеет место log2 \Q(b,n,l)\ ж 2г при I —> оо.

§1.2 О стартовых состояниях AMT в чистой среде.

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

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

Для решения этих задач выделяются некоторые свойства состояний, которые названы sv-ceoücmeaMU при b = г и ти-свойствами при Ь > г, где v G N3 и и € N5. В первом случае состояния допускают локальную характериацию через нагрузки ресничек, а во втором она доопределяется возможным продолжением конфигураций в виде загруженных цепей. Описания этих свойств достаточно громоздки для изложения здесь, поэтому используются далее лишь условно.

Пусть S — {s„|u € N3} и М = {mv\v G N5}. Класс всех состояний q из Q(b,n,l) с s^-свойством при sv € S обозначается через К3<1, а класс всех состояний q из Q(b, п, I) с mt,-свойством при т„ 6 М — через Кт<1.

Теорема 2. При b = г выполнено

{KSl, если I = 1 и п = 2, (1)

KSl U KS2, если I = 1 и п > 2, (2)

KSl U KS2 U К3з, если I > 2 и п > 2, (3)

где KSv 0 при всех v из N3 и если j 6 {(2), (3)}, то для элементов строки {]) при v фи выполнено KSv К3и.

Теорема 3. При b > г выполнено

{Kmi, если l = 1 и n = 2, (1)

Kmi U Km2, если l = 1 и n > 2, (2) LUn5 Km„> если l>2un>2, (3)

где K^ ф 0 при всех «HiNju если j € {(2), (3)}, то для элементов строки (j) при v фи выполнено К^ <JL Кти.

Теорема 4. Имеет место

\St(b,r,n,l)\ ~ \Q(b,n,l)\ -1'

где С = при Ь = г, С = при г < b < 2г и С =

при b>2r.

Следствие. Имеет место при I —> оо:

а) |5i (6, г, п,1)| ~ |Q(b, п,1)\, если b = r,

б) \St(b,r,n,l)\ х \Q(b,n,l)\, если b>r.

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

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

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

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

Состояние q1 I-дерева D~l{b, г, п, I) переводимо в состояние q2 этого I-дерева, если для некоторого t, такого что t > 1, будет выполнено q1^) = q2. Очевидно, такое t единственное.

В состоянии q ресничка с номером ijk I-дерева D~l{b, г, п, I) при qijk > О называется характеристической ресничкой этого состояния, если для любой другой реснички с номером i'j'k' со свойством qv-yk' > 0 справедливо г' > г и при г' = i выполнено к' > к.

Пусть состояние q I-дерева D~l(b, г, п, I) имеет s характеристических ресничек с номерами iijiki, гъЗгкг, ■■■, isjskg, где s € N. Из определения характеристических ресничек вытекает, что ц = г2 = • • • = га и ki = к2 = • • • = к3, то есть все характеристические реснички состояния q принадлежат ребрам ji, jz, ..., js одной и той же глубины I-дерева, которая обозначена через г, и имеют один и тот же номер внутри ребер этой глубины, который обозначен через к. Следовательно, множество характеристических ресничек состояния q можно задать их номерами следующим образом: {ijik, ij2k,... ,ijsk}, где s G N24-1. Множество ребер, которым принадлежат характеристические реснички состояния q обозначено Js, то есть Js — • • • ,js}, а множество характеристических ресничек состо-

яния q обозначено Mq(i, к, Js).

Величина Vq(t), равная Qijk(t)> называется объемом со-

стояния q(t).

Состояние меньшего объема не переводимо в состояние большего объема. Поэтому рассматривается задача о переводимости состояний q1 в ql из Q(b,n, I) в случае, когда Vqi > Vqi.

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

В случае, когда Vqi > 0 и Vq2 = 0, задача о переводимости этих состояний легко решается. В этом случае q2 — q', и, очевидно, qx переводимо в Я2-

Далее решается задача о переводимости состояния ql в состояние q2 в случае, когда Vqi > 0 и Vqi > 0.

Теорема 5. Если {gSg2} С Q(b,n,l), q2 St(b,r,n,l), Vq\ = Vqi, Vq\ > 0, Vqi > 0, jVqi(iuku JSl) и Afq2(i2, к2, Js2) — множества характеристических ресничек состояний ql и q2, соответственно, то q1 переводимо в q2 точно тогда, когда выполнены следующие условия:

а) ¿1 > ¿2 и при ¿1 = ¿2 имеет место k\ > к2,

б) gx((zi - г2)п + кх - к2 + 1) = q2.

Теорема 5 решает задачу о переводимости двух любых состояний ql в q2 из Q(b, п, I) в случае, когда объемы этих состояний равны. Далее рассматривается та же задача в случае, когда объемы этих состояний различны, то есть Vgl > Vgl.

Главная идея решения этой задачи заключается в том, чтобы найти момент t = t(ql,q2), такой что > Vqi и — Vq2- Если в момент t

будет выполнено Vqi ¡¡^ = Vq-t, то используется теорема 5 для решения этой

задачи. Если же в момент t выполняется V^i^ < Vq2, то заключается, что qx не переводимо в q2.

Теорема б. Если {g\g2} С Q{b,n,l), q2 £ St{b,r,n,l), Vqi > V?, Vqi > 0, Уф > 0, ki,JSl), k, Js) uNqi(i)(i~t) k~t, JSl) — множества харак-

теристических ресничек состояний q1, q2 и ^(t), соответственно, mo g1 переводимо в q2 точно тогда, когда выполнены следующие условия:

а) УчЧ*) =

б) ц > i и при ц = i имеет место А;г- > к,

в) q1(t + [ц - г)п + fcj -к) = q2.

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

Вводится функция L(b, г, n, I, V') для I-дерева D~l (6, г, п, /; V'), которая равна наибольшему из времен, за которое происходит полное самоочищение D~l{b, г, п, V') при произвольном начальном распределении загрузки V этого I-дерева. Эту функцию обычно называют сложностной функцией Шеннона.

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

1) если (2г - 1)Ьп < V' < V, то L{b,r,n,l,V') =];K2ni ~ 1)-'

2) если 0 < V' < {21 - 1 )Ъп, то г) при г = 1 имеем:

а) если V' < Ьп, то

б) если bn < V <bn + (l - 1 )п, то

L(b, 1, n, I, V') = V + п{1 + b - 1) - 1;

в) если V' >Ъп + {1 — 1)п, то

, тгл f если = 1 и hz = 1,

L(b,r,n,l,V J = < / \

|д1^[+(Ь-Жп('-*з+1)-Лз)+пЧ| иначе-,

гг) при r > 1 имеем:

а) если V' < nl, то L(b, г, п, I, V') = V' + nl — 1;

б) если V' > nl, то

г/г , тт f l^MMH-1). еми = 1 и Л3 = 1, L(b,r,n,l,V) = < / ЬГ \

иначе;

где

= 1 + Р - +1)], Лз -

bhi — V'-nl- {2l~k* - 1 )(Ь - l)n - 21~кз(Ь - l)(n - h3) + 1.

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

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

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

! у

Lcp.{b, г, п, I) = — ■ L(b, г, п, I, V').

V'=\

Пусть L(b,r,n,l) — msx.i<v'<v L(b,r,n, I, V'), то есть L(b,r,n,l) равна минимально достаточному времени, за которое происходит полное самоочищение I-дерева D~l(b,r,n,l) при произвольной его загрузке V'. Так как дольше всех будет очищаться полностью загруженное I-дерево, то из теоремы 7 следует, что L{b,r,n,l) =}^[(2nl — 1).

Теорема 8. Для L^b, г, п,1) выполнено

Lcp.(b,r,n,l) ~ 2при I —*• оо.

Следствие. L^b, г, п, I) ~ L(b, г, п, I) при I -* оо.

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

В этой главе процесс транспортировки вещества по легким представим некоторым конечным автоматом Aa(b, г, п, I) со входом. Входной алфавит автомата Aa(b, г, п, I) состоит только из одной буквы а, где а £ Ny, то есть

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

Далее в параграфах этой главы изучаются свойства автомата Аа(Ъ,г,п,1).

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

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

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

Пусть Fin(b, г, п, I, а) — множество финальных состояний автомата Aa(b,r,n,l).

Через q* обозначено состояние автомата Aa(b, г, п, I), при котором все реснички, кроме реснички с номером 111, имеют нагрузки, равные своей емкости, а ресничка с номером 111 имеет нагрузку 21~1(Ь — г).

При а > 2,-1г автомат Aa[b, г, п, I) имеет только одно состояние, которое переходит в себя, и оно совпадает с q*. Таким образом, если а > 2,-1г, то Fin(b,r,n,l,a) = {<7*}.

При а < 2i-1r все финальные состояния описываются так.

Теорема 9. Для q из Q(b, п, I) при а < 21-1г выполнено q е Fin(b, г, n, I, а) точно тогда, когда для q одновременно выполнены следующие условия:

а) <7ш < 2l~l(b — г) при а = 2i_1r и qm — 0 при а < 21~1г,

б) для любого номера ijk, такого 4moijk ф 111, ijk ф Ijn npuj € N2i-i и q^f. = 0, при k < п имеет место %(k+i) = 0, а при к — п имеет место Q(i+i)j'i = Q(i+i)j"i = 0, где ребра j' и j" уровня г + 1 инцидентны ребру j уровня i.

Теорема 10. Если а < 21~1г, то log2\Fin(b,r,n,l,a)\ х 21 при I —+ оо.

Следствие. Диаграмма Мура автомата Аа{Ь, г, n, I) предсталяет собой дерево при а > 2г_1г и лес при а < 2'_1г.

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

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

Входная буква а при заданных I и b представимав виде а = k-2l~lb+k', где к' < 2Если а > 2l~lr, то к > 0 при b > г и к > 0 при b = г.

Пусть D~x{b,r,n,l) — неполное поддерево I-дерева D~l(b,r,n,l), такое что оно имеет глубину ]£[ в случае, когда либо п не делит к нацело, либо п делит к нацело и при этом к' = 0, или глубину £ + 1, когда либо п делит к нацело и к' > 0, либо к — 0. При этом количество ресничек на последнем (нижнем) уровне этого поддерева равно либо к — [£] • п, если к' — 0, либо £_[£]. n +1, если к' > 0.

Это неполное поддерево г, n, I) загружается таким образом, как

если бы к полностью пустому этому поддереву применился один шаг процесса транспортировки в стационарной загрязненной среде подачей на вход буквы а, где а > 21~хг. Поддерево D~l(b,r,n,l), загруженное таким образом, обозначается D~l{b, г, п, I).

Итак, при а > 2г_1г и b — гдля D~l{b,r,n,l) выполнено: ресничка с номером 111 имеет нулевую нагрузку, все остальные реснички кроме, быть может, самых нижних ресничек имеют нагрузки, равные своим емкостям, а суммарная нагрузка по всем нижним ресничкам равна к'.

При а > 2г-1г и 6 > г для D~l(b,r,n,l) выполнено: если к — 0, то ресничка с номером 111 имеет нагрузку а — 2i~1r, а если к > 0, то ресничка с номером 111 имеет нагрузку 21~1{Ь — г) и все остальные реснички кроме, быть может, самых нижних ресничек имеют нагрузки, равные своим емкостям, а суммарная нагрузка по всем нижним ресничкам равна к'.

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

Состояние q из Q{b,n, I) при b = г обладает:

— Sa-свойством, если при данном q для поддерева D~l{b, г, п, I) 1-дерева D_1(6,r-,n,/) выполнено D~l{b,r,n,l) < D~1(6,r,n, I);

— Si-свойством, если при данном q выполнено qni > 0.

Состояние q из Q(b, п, I) при b > г обладает:

— та-свойством, если при данном q для поддерева D~l{b, г, п, I) I- дерева D~l(b,r,n,l) выполнено D~l(b,r,n,l) < D~l(b,r,n,l).

Класс всех состояний из Q(b,n,l) с яа-свойством обозначен через KSo, класс всех состояний из Q(b,n,l) с si-свойством обозначен через К^, а класс всех состояний из Q(b,n, I) с та-свойством — через КШа.

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

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

1) Если а > 2l~lr, то имеет место:

а) St(b, r,n,l,a) — KSa U St(b, r, n, l) при b = r,

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

2) Если а < 21-1 г, то имеет место:

а) St(b, г, п, I, а) — Кщ U St(b, г, n, i) при Ь = т,

б) St(b, г, га, о) = £¿(6, г, га, I) при Ь> г.

При этом KSa ф 0, K-Sl ф 0, Кта ф 0, KSa £ St(b,r,n,l), Кта <£ St{b,r,n,l) иКь £ St(b,r,n,l).

Теорема 12. Имеет место при I —► оо:

aj St(b,r,n,l,a) ~ Q(b,n,l), если b = r, б) St(b, г, га, /, а) х га, если Ь> г.

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

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

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

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

Теорема 13. Если а > 2l~1r, {д1,?2} С Q(b,n,l), q2 ф q*a и q2 (f: St(b,r,n,l,a), то q1 переводимо в q2 точно тогда, когда выполнены следующие условия: а) Vq2 > Vgl,

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

Следствие 2. В диаграмме Мура автомата Аа(Ь,г,п,1) все состояния из <3(Ь,п,1), имеющие одинаковый объем, имеют путь до д* одинаковой длины.

По следствию из теоремы 10 диаграмма Мура автомата Аа(Ь,г,п,1) при а > 21-1г является деревом, глубина которого считается глубиной 0(Аа(Ь, г, п, /)) этой диаграммы.

Следствие 3. Если а > 2'"1г, то С(Аа(Ь,г,п,1)) =]:2'ДЬГ-Ггг) [•

Далее рассматривается случай, когда 0 < а < 21~1г. По следствию из теоремы 10 в этом случае диаграмма Мура автомата Аа(Ь,г,п,1) представляет собой лес, финальные состояния которого образуют множество Рт(Ь,г,п,1,а). В связи с этим возникает задача о переводимости ц из <2(6, п, I) в д* из Пп(Ь, г, п, I, а).

Цепь с номером г (цепи 1-дерева г, п, I), идущие от листа до кор-

ня, занумерованы слева направо) обозначается С», где г 6 1.

Рассматривается некоторое состояние д 1-дерева 0~1(Ь, г, п, I). Конфигурация нагрузок цепи С^ (ее состояние) в этом состоянии обозначается Яц-

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

Финальным состоянием изолированной цепи С*, находящейся в состоянии д^, называется такое ее состояние д^(Т), что для любого í > 0 выполнено + Ь) = Яа(Т).

Пусть Тр. - время перехода изолированной цепи С* 1-дерева находящегося в состоянии д(2), в финальное состояние.

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

Теорема 14. Если 0 < а < 2 ,_1г, д 6 <3(6, п, I) ид* £ Пп(Ь, г, п, I, а), тод переводимо в д* точно тогда, когдад(Т) = ц*а, гдеТ — тахс;,гбК2!_1 7^+2-

Теорема 14 для диаграммы Мура автомата Аа(Ь,г,п,1) при 0 < а < 2'"V дает описание всех деревьев, корнями которых являются элементы множества Пп(Ь, г, п, I, а).

Решение задачи о переводимости двух любых состояний д1 и д2 из <2(6, п,/) автомата Аа(Ь, г, п, I) при 0 < а < 2(_1г доставляет следующее утверждение.

Теорема 15. Если 0 < а < 21~1г, {^д2} С <2(6, п,/), то д1 переводимо в д2 точно тогда, когда существует натуральное Т из отрезка [1; шахс^ег^!-! ТЦ, + 2], такое что дг(Т) = д2.

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

Теорема 16. Если 0 < а < 2'-1г, то G(Aa{b, г, п, /)) = 2In -

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

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

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

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

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

Здесь рассматривается I-дерево г, n, Z), функционирующее в пе-

ременной по загрязнению во времени среде.

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

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

Таким образом, так же как и первых двух главах, процесс транспортировки вещества по I-дереву D_1(6, г, n,Z) в загрязненной нестационарной среде можно представить некоторым конечным уже неавтономным автоматом A(b,r,n, I), множество состояний которого совпадает с множеством

In—2

Ж

-4.

Q(b, n,l), с входным алфавитом {0,1,2,..., V} и следующей функцией перехода состояний: если в момент t автомат Л(b, г, n, I) находится в состоянии q и на вход в этот момент подается буква a(t), то в диаграмме Мура автомата Aa^(b, г, п, I) то состояние <?', в которое переходит q, является тем состоянием, в которое перейдет автомат Л(Ь, г, тг, I) из q под воздействием буквы a(f), то есть q(t + 1) = q'.

Таким образом, диаграмма Мура автомата Л{Ь, г, n, I) является "склейкой" диаграмм Мура автоматов в стационарных средах.

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

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

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

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

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

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

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

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

Объем загруженности I-дерева D~l(b,r, п, I; V'), равный где

О < 6 < 1, называется предельным порогом загруженности этого I- дерева. Далее пишется 5V вместо считая, что SV € N.

Пусть Ат — множество всех слов ат, где a(t) € Ny U {0} при t € Nm, на котором вводится отношение частичного порядка полагая ат < а'т, если a(t) < a'(t) для всех t из Nm.

Для I-дерева D~l{b, г, п, I; V') слово ат из Ат называется допустимым, если при подаче на него буквы a(t) из ат в каждый момент времени t все-

гда выполнено a(t)+V'(t) ^ 8V, где V'(t) — объем загруженности I-дерева Г>-1(Ь, г, n, i; V7) в момент t, t £ Nm. Такое слово называется предельно допустимым для I-дерева D_1(b, г, п, I; V'), если не существует допустимого слова а'т из Ат такого, что а'т ^ ат и а'т Ф ат.

оо

Пусть А* = (J Ат, а Аи — множество всех сверхслов (то есть слов бес-

т=1

конечной длины) of = а(1)а(2)... a(t)..где a(t) е No, на котором вводится отношение частичного порядка полагая of ^ а'ш, если a(t) ^ a'(t) для всех t из N.

Для I-дерева D~l{b, г, п, I] V') сверхслово of из А" называется допустимым, если при подаче на него буквы a(t) из of в каждый момент времени t всегда выполнено a(t)+V'(t) ^ 5V. Такое сверхслово называется предельно допустимым для I-дерева D~l(b, г, п, /; V), если не существует допустимого сверхслова а'" из Аш такого, что а,и} > of и а!ш ф of.

Ясно, что предельно допустимые сверхслова существуют. Например, сверхслово (5V — V')8V5V ...SV... при 6V ^ г является предельно допустимым.

Более того, можно показать, что для всякого допустимого сверхслова cf найдется предельно допустимое а'ш такое, что of < a'w.

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

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

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

Теорема 17. Слово а(1)а(2)... a{t)... а(т) при т > 1 является предельно допустимым для дерева D~l(b,r,n,l]V') точно тогда, когда для него выполнены следующие рекуррентные соотношения: а) для t = 1 выполнено

( [2i-1r, ¿V], если V' — О, , , I {0} U [21-1r, 5V - У], если «(1) = 0 и V' > 0, a(lj 6 [0, ¿К - У], если t/(l) ^ 2г_1г,

[2'-iг - г)(1), 5V - У], если 0 < w(l) < 2,"1г;

б) для всех £ = 2,..., т — 1 имеет место

t-i

[О, SV-V-J2 в(») + 2'_1гА;(«)], если v(t) >

[2'"V - w(t), SV-V'- £ а(г) + г'"1^«)],

если О < u(t) < 2г~'г,

o(t) G <

{0} U [2l-lr,ÔV - V' ~ a(») + 2l~lrk{t)},

если v(t) = 0 и V'(t) ф 0,

[2'-^; SV-V'- £ a(i) + 21-ггЩ)],

i=l

если v(t) = 0 и V'(t) = 0, где k( 1) = 0, k(t) = k{t — 1) +p(t — 1), причем

Для предельно допустимого слова ат его буква а(£) называется максимально возможной, если после подачи вещества объема а(£) в 1-дерево £>-1(&, г, п,V7) в этот момент времени общий объем нагрузки V'(t) данного I-дерева будет в точности равен 5V.

Понятие максимально возможной буквы распространяется на предельно допустимые сверхслова. Буква Ь € К, сверхслова называется максимально возможной, если после подачи вещества объема а(£) в 1-дерево г, п, 1\ V') в этот момент времени общий объем нагрузки V'(t) данного 1-дерева будет в точности равен 6У.

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

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

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

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

{

0, если v(t - 1) = 0,a(t - 1) = 0 и V'(t -1)^0,

1, иначе]

в) для £ = т выполнено а(т) = ¿V — V' — J2 + 21~1гк(т).

f=i

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

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

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

а) для t = 1 выполнено

Íp'-V.JV], если V' = О,

{0} U [2l~lr, 5V - V'}, если v{l) = 0 и V' > О,

[O.áV-V], если v{l) > 21~\

[2l~lr - и(1), SV - V'], если 0 < w(l) < 2l~lr\

б) для всех t = 2,..., m — 1 имеет место

[0,5К - V' -Еа(г) + 2l~lrk{t) - 1], если v(t) > 2l~lr, i=1

[2г_1г - v(t), SV -V' - f¿ а(г) + 2l~lrk{t) - 1], ¿=i

если 0 < v(t) < 2l~1r,

{0} U [2¡-V, ¿V-V- £ a(i) + tf-VfcCt) - 1], ¿=i

.если v{t) = 0 uV'(t) t¿0,

[21-1r, ÔV - - ¿ a(i) + 2l~lrk{t) - 1], ¿=i

если v(t) = 0« V'(t) = 0, где k( 1) = 0, k(t) = k(t — 1) +p{t — 1), причем

a(t) € <

p(t- 1)

■íí

если v{t -l) = 0,a(¿-l) = 0u V"(í - 1) ф 0,

иначе;

t-i

ej для t — m выполнено a(m) — ÓV — V — J2 a(i) + 2г 1rk(m).

i=i

Пусть Р(Ь, г, <5, К') — множество всех минимальных предельных префиксов для 1-дерева £>-1(6, г,тг, V) с предельным порогом загруженности 6V, а 5(6, г, 6V — 21_1г) — множество всех минимальных предельных суффиксов для 1-дерева D~1(b,r,n,i,6V — 21_1г) с предельным порогом загруженности 5V.

Вводится операция конкатенации • над словами и сверхсловами. Если ат €Е А*, а ¡3 е A* U Аш, то выражение ат ■ /3 будет определять слово или сверхслово, получаемое приписыванием к ат последовательно справа всех букв из (3.

Если С С Л*, a D С A* U Аы, то полагается С ■ D = |J а • (3.

аеС PeD

Через Рт(Ь, г, 6, V') обозначено множество всех минимальных предельных префиксов длины т для I-дерева D_1(6, г, п, I; V') с предельным порогом загруженности 8V, а через Sm(b,r,5,SV — 2i_1r) — множество всех минимальных предельных суффиксов длины то для 1-дерева D~l{b,r,n,l\ 5V — 2г_1г) с предельным порогом загруженности SV.

Пусть

оо

5(6, г, 5, SV - 2l~1r) = U&(Ь, Г, 6,5V - 2l~lr), i=2

оо

P{b,r,5y) = {JP%rAV')-¿==2

Пусть е — пустое слово, для которого считаются выполненными для любого А из 5(6, г, д, 5V — 2г_1г) соотношения е • А = А • е = А. Полагается, что е GS{b,г, 6, SV -2'-^).

Распространяется операция А* и Аш на случай произвольного множества В С А* в предположении, что В* состоит из всех слов, являющихся конкатенациями слов из В, а Вш — из всех сверхслов, получаемых последовательным приписыванием слов из В.

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

Теорема 19. Имеет место

QD-t(Ь, r,n,l, SV, V') = Р(6, г, S, V') ■ (5(6, г, 6, SV — 2l~lr) ■ {е, 2г_1г})* U

U (5(6, г, б, SV - 2(_1г) • {е, 21~1г}У.

Следствие 1. Мощность множества всех предельно допустимых сверхслов для I-дерева D~l(b, г, п, l\ V') континуальна.

Пусть Tp_i(JV, 6, г, п, I, V') — множество всех предельно допустимых слов длины т для I-дерева D~1(b,r,n,i,V')>.Q^i(6V,b,r,n,l,V') — множество всех допустимых слов длины т для I-дерева D-1(6, г, п, l\ V).

Следствие 2. Для ат из Ат выполнено ат G Qp-i(6V, b, г, п, I, V') точно тогда, когда существует ßm из T^(SV, b, г, п, I, V'), что ат < ßm.

Пусть Q^^SV, b, г, п, I, V') — множество всех допустимых сверхслов для I-дерева D~l(b, г, п, I; V) и b, г, п, I, V') — множество всех пре-

дельно допустимых сверхслов для этого 1-дерева.

Следствие 3. Для аи из Аш выполнено аш € Q^).i(SV,bir,n,l,V') точно тогда, когда существует из b, г, п, I, V'), что аи ^ ßu.

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

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

Через Qi)-i(6V,b,r,n,l,V') обозначено множество всех допустимых слов для I-дерева £)_1(Ь,г, п,/; У), а через Тц-л{5У,Ь,г,п,1,У) - множество всех предельно допустимых слов для I-дерева D~l{b, г, п, I; V').

Теорема 20. Множества Qd-i(SV, b, г, п, I, V) и То-1 (SV, b, г, n, l, V') регулярны, а множества QwD-i{SV,b, г,n,l,V') uT£-i{SV,b,r,n,l,V') обще-регулярны.

Теорема 21. Для \T^(5V, b, г, п, /, V')| выполнены следующие соотношения:

а) если 5V < 2!~1г, то }T%-i{öV,b,r,n,l,V')\ = 1,

б) если SV > 21~1г, то log2\T^1(SV,b,r,n,l,V')\ х то при 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.

Издательство ЦПИ при механико-математическом факультете МГУ имени М. В. Ломоносова

Подписано в печать О5.02,09 Формат 60x90 1/16. Усл. печ. л./5 Тираж /00 экз. Заказ 09

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета

Введение

1 АМТ в чистой среде

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

1.2 О стартовых состояниях АМТ.

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

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

2 АМТ в загрязненных стационарных средах

2.1 О финальных состояниях АМТ.

2.2 О стартовых состояниях АМТ.

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

3 АМТ в загрязненных нестационарных средах

3.1 О свойствах диаграммы Мура АМТ.

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

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

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

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

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

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

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

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

Работа состоит из трех глав.

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

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

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

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

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

Основным итогом первой главы является решение перечисленных выше задач.

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

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

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

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

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

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

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

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

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

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

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

Пусть N - множество натуральных чисел, No = {0}UN, = {1,2,3,., к] и Z, I £ N, считается глубиной этого I-дерева. Считается, что ребро 1-дерева D-1, инцидентное корню, имеет глубину 1.

Каждое ребро из D~x разделено на n, п £ N, равных частей, называемых ресничками, и занумерованных числами г, г € Nn, возрастающими в направлении, обратном ориентации ребра.

Каждому ребру глубины j, j G N/, приписывается два числа 2и 2l~ir, где b, г е N и г < Ь, называемых емкостью и мерой переброса ресничек ребер глубины j, соответственно.

Такое I-дерево D~l с описанными выше параметрами b, г, п и I обозначается -D-1(6, г, п, /).

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

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

I-дерево D~l{b, г, п, I) с исходным объемом загруженности V' обозначается D~l{b,r,n,l\V').

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

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

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

Бх) При нагрузке меньшей емкости первой с такой назрузкой реснички, она осуществляет прием вещества максимально возможной массы с/г, такой что К uim(2l~:>b — di,d), где - емкость этой реснички.

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

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

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

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

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

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

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

В2) Если на ресничке нагрузка тит> 2 то она перебрасывает на следующую ресничку нагрузку 2и оставляет у себя нагрузку т — 2

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

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

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

Считается, что процесс транспортировки вещества по 1-дереву jг, n,/; V) осуществляется в дискретные моменты времени 1,2,3,.

В первый момент I-дерево D~~l{b, г, п, I; V') имеет заданное распределение нагрузок по его ресничкам.

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

Если в каждый момент t = 1,2,3,. все реснички I-дерева D~1(b,r,n,l',V/) осуществляют прием вещества нулевой массы, то такой процесс называется процессом транспортировки вещества по этому I- дереву в чистой среде. При наступлении момента t, в который все реснички I-дерева D~1(b, г, п, I; V') впервые стали равными нулю, считается, что произошло полное самоочищение этого I-дерева.

Под распределением нагрузки V' I-дерева -D1(6, г, n, Z; V') понимается любое из возможных распределений нагрузок всех его ресничек таких, что суммарный объем их нагрузок равен V'. Ясно, что V' < V, где V - объем I-дерева D*1^, г, п, /) и V = 2l~1bnl. Такие распределения называются конфигурациями нагрузки V' по ресничкам I-дерева -D1(6, г, п,/).

Занумеруем все реснички I-дерева D~l{b, г, n, I) таким образом, что ресничка с номером ijk является к-ой ресничкой j-го ребра глубины г, где 1 < г < I, 1 < j < 2г1, 1 < к < п, а нумерация ребер одной глубины идет слева направо. Тогда в каждый момент t конфигурацию нагрузки V'(t) в I-дереве D~l(b, г, п,1) можно задать набором q(t) = (gill(*), 9112 W, • ■ •, Qijk(t),., qi2'-in(t)) , в котором каждая координата qijk(t) равна нагрузке реснички с номером ijk в момент £, причем 0<qijk(t) <21~гЬ и Хлп П Qijk(t) — V'(t).

Пусть в процессе транспортировки конфигурации нагрузки V'(t) в каждый момент t изменяются по правилам Л г) — Дг)- Тогда процесс транспортировки можно представить некоторым конечным автономным автоматом г, п, /) с одним финальным состоянием [21]. Состояниями этого автомата являются конфигурации нагрузок V'(t) в I-дереве D~1(b, г, п, /), которые называются также состояниями этого I-дерева, а законы перехода из одного состояния в другое считаются указанными выше.

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

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

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

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

Возникает задача нахождения величины |<3(6, п, /)|, решение которой доставляет следующее утверждение.

Теорема 1. Имеет место соотношение

Q^nJ)\=Ul1(2l-ib+lf~1-n.

Следствие. Справедливы следующие оценки

6(2'-1).п . 2&-1-1).п < |Q(b>njQ| < (Ь+ l)(2'-D-n . 2(2'-/-1).п

Следствие. Имеет место log2 |Q(b, п,1)\ ж при I —> оо.

О стартовых состояниях АМТ в чистой среде.

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

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

Для решения этих задач выделяются некоторые свойства состояний, которые называются Sv-свойствами при 6 = г и ти-свойствами при b > г, где v £ N3 и и £ N5. В первом случае состояния допускают локальную характериацию через нагрузки ресничек, а во втором она доопределяется возможным продолжением конфигураций в виде загруженных цепей (их описание см. на стр. 30 — 36).

Пусть S = {svk £ N3} и М = {mv\v £ N5}. Класс всех состояний q из Q(b,n,l) с «„-свойством при sv £ S обозначается через KSv, а класс всех состояний q из Q(b, п, I) с mv-свойством при mv бМ - через Kmv.

Теорема 2. При b = г выполнено п >2, (3) где KSv Ф 0 при всех v из N3 и если j £ {(2), (3)}, то для элементов строки (j) при v фи выполнено KSv К$и.

Теорема 3. При b> г выполнено

St(b, г, п,/) = < Kmi U Кт2, если I = 1 и п > 2, (2) I LUn5 Kmv, если 1>2ип>2, (3) где Kmv Ф 0 при всех v из N5 и если j £ {(2), (3)}, то для элементов строки (j) при v фи выполнено Kmv Кти.

Теорема 4. Имеет место

1) (2)

Кт1, если I = 1 и п = 2, (1)

С<

St{b,r,n,l)\ \Q(b,n,l)\

1, где С = ^ при Ъ > 2г. w4+i) пРи b = г, С — ffi-i&i)* npur < b < 2г и С =

W~4>+1

Следствие. Имеет место при I —> оо: а) \St(b,r,n,l)\ ~ \Q(b,n, /)|, если Ь = г, б) г, п, х \Q(b,n, 1)\, если Ь> г.

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

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

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

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

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

В состоянии q ресничка с номером ijk I-дерева г, п, I) при qijk > О называется характеристической ресничкой этого состояния, если для любой другой реснички с номером i'j'k' со свойством qvyy > 0 справедливо г' > г и при г' — г выполнено к' > к.

Пусть состояние q I-дерева D~l{b,r,n,l) имеет s характеристических ресничек с номерами i\j\k\, 1232^2, isjsks, где s G N. Из определения характеристических ресничек вытекает, что = г'2 = • • • = is и ki = к2 = • • • = ks, то есть все характеристические реснички состояния q принадлежат ребрам ji, J2, • • -, js одной и той же глубины I-дерева, которая обозначена через г, и имеют один и тот же номер внутри ребер этой глубины, который обозначен через к. Следовательно, множество характеристических ресничек состояния q можно задать их номерами следующим образом: {ij\k,ij2k,. ,ijsk}, где s € N2»'-!. Множество ребер, которым принадлежат характеристические реснички состояния q обозначено Js, то есть Js — {j\1 j'2,. ,js}, а множество характеристических ресничек состояния q обозначено J\fq(i, k,Js)

Величина Vq(t), равная называется объемом состояния q(t).

Очевидно, что состояние меньшего объема не переводимо в состояние большего объема. Поэтому рассматривается задача о переводимости состояний ql в q2 из Q(b, п, /) в случае, когда Vqi >Vq2.

Задача о переводимости состояний ql в q2 в случае, когда Vqi — 0 и Vf = 0, тривиальна, так как q1 и q2 равны и совпадают с финальным состоянием q*, которое переводимо в себя за любое время.

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

Далее решается задача о переводимости состояния ql в состояние q2 в случае, когда Vqi > 0 и Vq2 > 0.

Теорема 5. Если {qx,q2} С Q(b,n,l), q2 $ St(b,r,n,l), Vqi = Vqi, Vqi > 0, Vq2 > 0, Nqi(ii,ki,JSl) и Л/^2(г*2, Js2) ~~ множества характеристических ресничек состояний q1 и q2, соответственно, то q1 переводимо в q2 точно тогда, когда выполнены следующие условия: а) Ч > Ч и при i\ — имеет место k\> к2, б) q\{ii - г2)п + к1-к2 + 1) = q2.

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

Главная идея решения этой задачи заключается в том, чтобы найти момент t = i(g\<?2), такой что > Vq2 и VqX@ < Vq2. Если в момент t будет выполнено Vqiф = Vq2, то используется теорема 5 для решения этой задачи. Если же в момент t выполняется < Vq2, то заключается, что q1 не переводимо в q2. Нахождение t описывается на стр. 48.

Теорема 6. Если {ql,q2} С Q{b,n,l), q2 £ St(b,r,n,l), Vqi > Vq2, Vqi > 0, Vqi > 0, Afqi(ii, ki, JSl), Nqi{i, k,Js) uAfqi^(iti ki, JSi) — множества характеристических ресничек состояний q1, q2 и q1(t), соответственно, mo q1 переводимо в q2 точно тогда, когда выполнены следующие условия: а) Vql{t) = V42> б) ц > г и при ц — г имеет место > к, в) q1(t+ (ц - г)п + k~t - к) = q2.

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

Введем функцию L(b,r,n,l,V') для I-дерева D~l{b,r,n,l\V'), которая равна наибольшему из времен, за которое происходит полное самоочищение D~1(b, г, п, /; V') при произвольном начальном распределении загрузки V' этого I-дерева. Эту функцию обычно называют сложностной функцией Шеннона.

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

1) если (21 - 1 )Ьп <V'<V, то L(b, г, п, /, V') =]%2nl - 1);

2) если 0 < V < (21 - 1 )Ьп, то г) при г = 1 имеем: а) если V' < Ъп, то

V' + b(n — 1), если I = 1 и п =]т[

L(6,l,n,/, V')

Ь I'

2Vf—]¥r[+nl — 1, иначе; б) если bn <V' <bn + (I — 1 )п, то

L(b, 1, п, I, V') = V' + п{1 + b - 1) - 1; в) если V' > bn+ (I — 1 )п, то

-^[+2b(ni-i), если к3 = 1 и h3 = 1, L(b,r,n, I, V ) — < f b. \ ii) при г > 1 имеем: а) если V' < nl, то L(b, г, п, I, V') = V' + nl — 1; б) если V' > nl, то

Tf. . f l^:[+2]|l(ni-i), если /г3 = 1 и Л3 = 1,

L(b,r,n:l,V ) = < / ь, \ t2(l?=fe:t+C^[-i)(»('-*3+i)-As)+ri/-|Jl иначе-, где l + + 1)1, = nH^-jS^lg^l+l,

ЬЛз = V -nl- (21~к* - 1)(6 - 1)п - 2^(6 - 1)(п - Лз) + 1.

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

Следствие. G(A(b,r,n,l)) ~ 1)

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

1 J^

Lap. (b,r,Tl,l) = — • ЦЬ, г, п, V').

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

Теорема 8. Для выполнено

Lcp.(b, г, п, I) ~ тгрм / —> оо.

Следствие. L^ (b, r, n, I) ~ L(6, r, n, l) при I —> oo.

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

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

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

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

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

Главными задачами этого параграфа являются описание всех финальных состояний автомата Ла(6, г, п, для каждого а из Nv и указание их числа.

Пусть Fm(6, г, п, а) — множество финальных состояний автомата Аа{Ь, г, п,1).

Через q* обозначено состояние автомата Aa(b,r:n,l), при котором все реснички, кроме реснички с номером 111, имеют нагрузки, равные своей емкости, а ресничка с номером 111 имеет нагрузку 21~1{Ь — г).

При а > 2l~lr автомат г, n, I) имеет только одно состояние, которое переходит в себя, и оно совпадает с q*. Таким образом, если а > 21~гг, то Fin(b, r,nj,a) = {4*}.

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

Теорема 9. Для q из Q(b, п, I) при а < 2l~lr выполнено q 6 Fin(b, г, п, а) точно тогда, когда для q одновременно выполнены следующие условия: a) qui < 2l~l(b — г) при а = 2l~lr и qm = 0 ггри а < 2г-1г; б) для любого номера ijk, такого что ijk ф 111, ijk -ф Ijn при j £ N2«-i и qijk = 0, при к <п имеет место <?{j(fc+i) — О, а при к — п имеет место <7(i+i)yi = <7(j+i)j"i = 0; где ребра j' uj" уровня i +1 инцидентны ребру j уровня i.

Теорема 10. Если а < 2l~lr, то log2\Fin(b, г, п, l,a)| х 21 при I —> оо.

Следствие. Диаграмма Мура автомата Aa(b, г, п, Г) предсталяет собой дерево при а > 2г-1г и лес при а < 2l~lr.

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

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

Входная буква а при заданных I и b представима в виде а = k-2l~lb+kf, где к' < 21~1Ь. Если а > 2то /с > 0 при 6 > г и к > 0 при b = г.

Пусть D~l(b, г, n, — неполное поддерево I-дерева г, n, Z), такое что оно имеет глубину в случае, когда либо п не делит А нацело, либо п делит /с нацело и при этом к' = 0, или глубину | + 1, когда либо п делит к нацело и к' > 0, либо к — 0. При этом количество ресничек на последнем (нижнем) уровне этого поддерева равно либо к — • п, если к' = 0, либо к - [£] • п + 1, если к' > 0.

Это неполное поддерево D~1(6, г, n, I) загружается таким образом, как если бы к полностью пустому этому поддереву применился один шаг процесса транспортировки в стационарной загрязненной среде подачей на вход буквы а, где а > 21~1г. Поддерево D~l(b,r,n,l), загруженное таким образом, обозначается D~l(b, г, п, I).

Таким образом, при а > 2l~lr и b = г для D~l(b,r,n,l) выполнено: ресничка с номером 111 имеет нулевую нагрузку, все остальные реснички кроме, быть может, самых нижних ресничек имеют нагрузки, равные своим емкостям, а суммарная нагрузка по всем нижним ресничкам равна к'.

При а > 2l~lr и b > г для D~x(b, г, п,1) выполнено: если к = 0, то ресничка с номером 111 имеет нагрузку а — 2z1r, а если к > 0, то ресничка с номером 111 имеет нагрузку 21~г(Ь — г) и все остальные реснички кроме, быть может, самых нижних ресничек имеют нагрузки, равные своим емкостям, а суммарная нагрузка по всем нижним ресничкам равна к'.

Загруженное некоторым образом поддерево D~l(b, г, п, /) 1-дерева Z>—1(6, г, 71, /), находящегося в некотором состоянии g, поресничково меньше загружено, чем D~x{b,г,п,Г) (обозначение г,n,I) < D~l(b,r,n,l)), если нагрузка хотя бы одной реснички поддерева D~l(b, г, п, I) 1-дерева D~~l(b, г, тг, I) в состоянии q меньше соответствующей ей реснички поддерева D~l(b, г, тг, Г) этого 1-дерева.

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

Sa-свойством, если при данном q для поддерева 1(6, г, п, /) 1-дерева -D1(6, г, п, I) выполнено D~l(b,r,n,l) < D~l{b,r,n,l)\ si-свойством, если при данном q выполнено дш > 0.

Состояние g из Q(b, п, Z) при & > г обладает: та-свойством, если при данном q для поддерева D~1(6,r,n,/) I- дерева D~x(b, г, п, I) выполнено D~1(6, г, n, Z) <3 D~x(b, г, n, Z).

Класс всех состояний из Q{b,n,l) с за-свойством обозначен через KSa, класс всех состояний из Q(b:n,i) с si-свойством обозначен через К^, а класс всех состояний из Q(&, п, /) с 7Па-свойством — через Кта.

Пусть St(b,r,n,l,a) — множество стартовых состояний 1-дерева Z)-1(&, г, 71, /) в стационарной среде с входным алфавитом {а}, где а £ Ny.

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

1) Если а > 2l~lr, то имеет место: а) St(b,r,n,l,a) = KSa U St(b,r,n,l) при b — r, б) St{b, r, n, a) = jFfma U ££(&, r, n, /) npu 6 > r.

Если а < 2г-1г; то имеет место: а) St(b, г, п, /, а) = К-§х U St(b, г, n, I) при b — г, б) St(b, г, 71, а) = ^(6, г, п, I) при Ь> г.

При этом К3а ф 0, Hf5l ^ 0, 0, £ St{b,r,nJ),

Кта £ St(b,r,n, I) и K-Sl <£ St(b,r,n,l).

Теорема 12. Имеет место при I —> оо; а) St(b, г, п, I, а) ~ Q(b, п, I), если Ъ — г, б) 3t(b, r,n,l,a) Q(b, n, l), если b> г.

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

Здесь рассматривается задача переводимости друг в друга состояний автомата Аа(Ь, г, п, /).

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

По следствию из теоремы 10 при а > 2l~lr автомат Л0(6, г, п, I) имеет только одно финальное состояние q*. В этом случае решение проблемы переводимости доставляет следующее утверждение.

Теорема 13. Если а > 2l~lr, {ql,q2} С Q(b,n,l), q2 ф q*a и q2 ф St(b} г, п, /,а), то ql переводимо в q2 точно тогда, когда выполнены следующие условия: a) Vq2 > Vqh

Следствие 1. Любое состояние q из Q(b,n,l) автомата Аа(Ь,г, п, I) в случае, когда Vq>Vq*, переходит в q* за время 1, в противном случае — за вРемя

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

Следствие 3. Если a > 2то G(Aa(b,r,n,l))

Далее рассматривается случай, когда 0 < a < 2l~lr. По следствию из теоремы 10 в этом случае диаграмма Мура автомата Аа(Ь, г, п,1) представляет собой лес, финальные состояния которого образуют множество Fin(b,r,n,l,a). В связи с этим возникает задача о переводимости q из Q(b,n,l) в q*a из Fin(b,r,n,l,a).

Цепь с номером i (цепи I-дерева D~l(b, г, n, I), идущие от листа до корня, занумерованы слева направо) обозначается Сгде i е N2j-i.

Рассматривается некоторое состояние q I-дерева D~l(b,r,n,l). Конфигурация нагрузок цепи С; (ее состояние) в этом состоянии обозначается

Цен

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

Финальным состоянием изолированной цепи Снаходящейся в состоянии qCi) называется такое ее состояние q^ (Т), что для любого t > 0 выполнено qc. (T + i) = qCi (Т).

Пусть Т^. - время перехода изолированной цепи С\ 1-дерева D~~l{b, г, п, /), находящегося в состоянии д(2), в финальное состояние.

Рекуррентно определяемая величина Tjj описывается в леммах 2.3.1 и 2.3.2 (см. стр. 78).

Теорема 14. Если 0 < а < 2l~1r, q <G Q(b, п, I) uq*a G Fin(b, r, n, /, a), mo q переводимо в q* точно тогда, когда q(T) = q*, где T — тахс^еп^ Tq.+2.

Теорема 14 для диаграммы Мура автомата Aa(b: г, n, I) при О < а < 21~1г дает описание всех деревьев, корнями которых являются элементы множества Fin(b, г, п, I, а).

Решение задачи о переводимости двух любых состояний q1 и q2 из Q(6, п,£) автомата Аа(Ъ, г, п, I) при 0 < а < 21~гг доставляет следующее утверждение.

Теорема 15. Если 0 < а < 2l~lr, {ql,q2} С Q(b,n,l), mo q1 переводимо в q2 точно тогда, когда существует натуральное Т из отрезка [1; maxcilZ-€N2,i Tq + 2L такое что ql{T) — q2.

По следствию из теоремы 10 диаграмма Мура автомата Ла(Ь, г, n, I) при 0 < а < 21~1г представляет собой лес. Наибольшая глубина дерева из всех деревьев леса называется глубиной этой диаграммы и обозначается G(Aa(b, г, п, I)).

Теорема 16. Если 0 < а < 2l~ V, то G(Aa(b, г, п, /)) = 21п - ^

4.

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

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

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

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

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

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

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

Объем загруженности I-дерева г, п, /; V7), равный }5V[, где

О < S < 1, называется предельным порогом загруженности этого I- дерева. Далее пишется 6V вместо считая, что 6V £ N.

Пусть Ат — множество всех слов ат = а(1)а(2). а(т), где a(t) G Ny U {0} при t Е Nm, на котором вводится отношение частичного порядка полагая ат < а'т, если a(t) < a'(t) для всех t из Nm.

Для I-дерева D~l{b, г, п, I; V) слово am из Лт называется допустимым, если при подаче на него буквы а(£) из ат в каждый момент времени t всегда выполнено a(t) + V'(t) ^ 6V, где — объем загруженности I- дерева D~l{b, г, п, /; V7) в момент £ G Nm. Такое слово называется предельно допустимым для I-дерева D~1(b, г, п, /; V7), если не существует допустимого слова а'т из Ат такого, что а'т ^ ат и a/m ^ am. оо

Пусть А* = (J а — множество всех сверхслов (то есть слов бес

771—1 конечной длины) аш — a(l)a(2). a(t)., где a(t) G No, на котором вводится отношение частичного порядка полагая ^ если a(t) ^ a'(t) для всех £ из N.

Для I-дерева -D1(6, г, тг, У) сверхслово а" из Аш называется допустимым, если при подаче на него буквы a(t) из аш в каждый момент времени t всегда выполнено a(i)+V (t) ^ 5V. Такое сверхслово называется предельно допустимым для I-дерева D~l{b, r,n,l\ V'), если не существует допустимого сверхслова a/UJ из Аш такого, что a,UJ ^ аш и ф aw.

Ясно, что предельно допустимые сверхслова существуют. Например, сверхслово (SV — V')SV6V . 5V . при 6V ^ г является предельно допустимым.

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

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

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

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

Теорема 17. Слово а(1)а(2). a(t). а(т) при т > 1 является предельно допустимым для дерева D~l{b,r,n,l\V') точно тогда, когда для него выполнены следующие рекуррентные соотношения: а) для t = 1 выполнено о(1) е < ti-\5V], если V' — О,

0} и [2l~lr,SV - V'], если и(1) = 0 и У > О,

0,- V'], если v(l) ^ 2l~lr,

2l~lr - v(l),<5V - V'], если 0 < v(l) < 2 б) для всех t = 2,., т — 1 имеет место a(t) 6 < i—1

0,<Л/ - V' - £ а(г') + 2l~lrk{t)}, если v(t) > г—1

2l~lr - v(t),SV Ф) + ^l~lrk{t)l i=1 если 0 <v(t) < 2l~lr. t-1

0} U [2Z-V, SV-V'-Y, Ф) + 2l~lrk{t)], i=l если = 0 и ф 0,

2'-V, SV-V-J2 a(i) + ^гВД], t=i если г;(£) = 0иУ'(4)= 0, где k( 1) = 0, k(t) = — 1) +p(t — 1), причем

О, если v{t -l)=0,a(f-l)=0u V(t - 1) ^ 0, p(t - 1) =

1, иначе; t-1 ej для t = m выполнено a{m) ~ 8V — V — Ф) + ^ lrk(m). г=1

Для предельно допустимого слова ат его буква a(t) называется максимально возможной, если после подачи вещества объема a(t) в I-дерево D~l{b,r,n,l\V') в этот момент времени общий объем нагрузки V'(t) данного I-дерева будет в точности равен 8V.

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

D~1(b1 r, n, Z; V') в этот момент времени общий объем нагрузки V'(t) данного I-дерева будет в точности равен 8V.

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

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

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

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

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

Теорема 18. Все минимальные предельные префиксы и суффиксы длины т, т > 1, являются предельно допустимыми словами а(1)а(2). a(t). а(т) длины т, где a{t) определяются рекуррентно так: а) для t = 1 выполнено tf-WtSV], еслиУ = О,

0} U [2l-\ 5V - V'], если v(l) = 0 и V' > 0,

О^У-У], если г>(1) > 21~\

2l~lr - v(l), 5V - V'l если 0 < v(l) < 2

Л-1 a(l) £ < б) для всех t = 2,., т — 1 имеет место t-1 a(t) 6 <

О, SV - V' - £ а(г) + 2f"Vfc(t) - 1], еа/m v(t) ^ 21~\ г=1

2Z~V - v(t), w — v' — Yl Ф) + г1-1^© -1], i—1 если О < v(t) < 2l~1r,

0} U [2l~lr, SV-V'- £ а(г) + 21'1rk{t) - 1], 1 если v(t) = О и V'(t) ф О, t-1

2l-\ 5V-V-Y1 а{г) + У^гкф - 1], г=1 если v(t) = О и V'(t) = О, где к{ 1) = 0, kit) — k(t — 1) +p(t — 1), причем

О, если v(t -l) = 0,e(t-l) = 0u V'(t — 1)фО,

Pit - 1) =

1, иначе; t-1 в) для t = т выполнено а{т) = SV — V' — ]Г) а (г) + 2 гк(т). г—1

Пусть Р(Ь, г, <5, V') — множество всех минимальных предельных префиксов для I-дерева D~l{b, г, n,l- V') с предельным порогом загруженности SV, а 5(6, г, (5V — 21~1г) — множество всех минимальных предельных суффиксов для I-дерева г, n,l]5V — 2l~lr) с предельным порогом загруженности SV.

Вводится операция конкатенации • над словами и сверхсловами. Если am е Л*, а /3 G Л* U Аш, то выражение ат • (3 будет определять слово или сверхслово, получаемое приписыванием к ат последовательно справа всех букв из (3.

Если С С Л*, a Z) С Л* U Л"7, то полагается С • D = (J аес peD

Через Pm(6, г, <5, V) обозначено множество всех минимальных предельных префиксов длины т для I-дерева г, п, V) с предельным порогом загруженности 6V, а через 5т(6, г, — 2l~1r) — множество всех минимальных предельных суффиксов длины т для I-дерева D-1(6, г, n, Z; 5V — 21~1г) с предельным порогом загруженности <5V. Пусть оо

5(6, г, 6,6V - = IJ 5г'(6, г, 5V - 2l~lr), г=2 оо г=2

Пусть е — пустое слово, для которого считаются выполненными для любого Л из

5(6, г, 6V — 2/1г) соотношения е • Л = Л • е = Л. Полагается, чтое е S(b,r,5,5V — 2l~1r).

Распространяется операция А* и Аш на случай произвольного множества В С А* в предположении, что В* состоит из всех слов, являющихся конкатенациями слов из В, а Вш — из всех сверхслов, получаемых последовательным приписыванием слов из В.

Пусть г, n, Z, <5V, V) — множество всех предельно допустимых квазислов для I-дерева D~l{b, г, ?г, Z; V7).

Теорема 19. Имеет место г, те, Z, <5V, V') = P(6, r, 6, V) • (5(6, r, (J, - ^"V) • {e, 2l~lr})* U

U (5(6, r, 5, SV - 2l~lr) • {e, 2l-lr}f .

Следствие 1. Мощность мнооюества всех предельно допустимых сверхслов для /- дерева D~l(b,r,n,l-,V') континуальна.

Пусть Tqi((!>V, 6, г, n, Z, V) — множество всех предельно допустимых слов длины т для I-дерева D~l(b, г, те, Z; V), Q1g-1(SV,b,r}n}l,V') — множество всех допустимых слов длины тег для I-дерева D~l{b, г, те, Z; V).

Следствие 2. Для ат из выполнено ат G Q^-i (6V, 6, г, те, Z, К') точно тогда, когда существует (5т из TpL^SV, 6, г, те, Z, У), -что ^ /Зт.

Пусть Qp-tldV, 6, г, те, Z, V) — множество всех допустимых сверхслов для I-дерева D"1 (6, г, те, Z; V) и (JV, 6, г, те, Z, У') — множество всех предельно допустимых сверхслов для этого 1-дерева.

Следствие 3. Для аш из Аш выполнено аш € Q'f).1(dVi b, г, те, Z, V') точно тогда, когда существует из г, те,/, V'), что аш <

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

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

Через QD-i(5V,b,r,n,l,V') обозначено множество всех допустимых слов для 1-дерева D~1(b,r,n,l]V'), а через TD-i(6V}b,r,n,l,V') - множество всех предельно допустимых слов для 1-дерева D~l{b, r,n,l; V').

Теорема 20. Множества Qi)-i(5V,b,r,n,l,V') и T£>-i(SV,b,r,n,l,V') регулярны, а множества Qp-^SV, b,r,n,l: V') и г, те,/, V') обще-регулярны.

Теорема 21. Для fT^.! (5V, Ь, г, те, V) | выполнены следующие соотношения: а) еслидУ < 2l~lr, то \T™^(5V,b,r,n,l,V')\ = 1, б) если 6V > 2l~lr, то log2\T^.i(6V, 6, г, те,/, х гп при тоо.

Основные результаты работы опубликованы в статьях [15] — [25].

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

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

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

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

2. J. T. Ottesen, M.S. Olufsen, J.K. Larsen Applied mathematical models in human physiology, SI AM, 2004.

3. P. T. Macklem Respiratory Mechanics, Annual Review of Physiology, Vol. 40, 1978, pp. 157-184.

4. 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.

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

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

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

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

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

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

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

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

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

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

15. 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.