Об отличимости состояний конечных автоматов

Пантелеев, Павел Анатольевич

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

Пантелеев, Павел Анатольевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2006 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Об отличимости состояний конечных автоматов»

Автореферат диссертации на тему "Об отличимости состояний конечных автоматов"

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

Пантелеев Павел Анатольевич

ОБ ОТЛИЧИМОСТИ СОСТОЯНИЙ КОНЕЧНЫХ АВТОМАТОВ

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

АВТОРЕФЕРАТ

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

МОСКВА - 2006

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

Научный руководитель:

доктор физико-математических наук, профессор А.С. Подколзин.

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

доктор физико-математических наук, профессор М.М. Глухов; кандидат физико-математических наук Х.А. Мадатян.

Ведущая организация:

Московский энергетический институт (технический университет).

Защита диссертации состоится 16 июня 2006 года в 16 часов 15 минут на заседании диссертационного совета Д.501.001.84 в Московском государственном университете им. М.В. Ломоносова по адресу 119992, ГСП-2, Москва, Ленинские горы, МГУ, Механико-математический факультет, аудитория 14-08.

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

Автореферат разослан 16 мая 2006 года.

Ученый секретарь диссертационного совета Д.501.001.84 в МГУ доктор физико-математических наук, профессор " / В.Н. Чубариков

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

Актуальность темы.

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

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

Проблема тестирования конечных автоматов изучалась многими авторами, и в этой области получены математические результаты, имеющие как теоретическое, так и прикладное значение. Самые ранние работы в этой области датируются еще пятидесятыми годами прошлого столетия. В статье1 Э. Мура "Умозрительные эксперименты с последовательностными машинами" впервые формально определяется понятие эксперимента с автоматами, имеющее центральное значение в области тестирования конечных автомат тов. В этой же работе автор получает ряд оценок сложности некоторых видов экспериментов, а также показывает их достижимость. Более систематическое изучение сложностных характеристик экспериментов с автоматами было проведено А. Гиллом2.

Дальнейшее изучение экспериментов было проведено М.Н. Соколовским3,4, который получил асимптотику функции Шеннона длины простого условного диагностического эксперимента для всех состояний автомата, а также достаточно точные оценки для подмножеств состояний. Он также первым обозначил связь между диагностическими экспериментами и сложностью порождения элементов в полугруппах5.

Еще в работе Мура1 была получена верхняя оценка длины условного установочного эксперимента. Нижнюю оценку для него, совпадающую с

1 Moore E.F. Gedanken-experiments on sequential machines. Ц Automats Studies, 1956, p. 129-153[русский перевод см. "Автоматы" (сб. статей), 1956, ИЛ, с. 179-210].

2Гилл А. Введение в теорию конечных автоматов. // Наука, 1966, 272 с.

я Соколове кий М.Н. О диагностических экспериментах с автоматами. // Кибернетика, Ж, 1971, с. 44-49.

4Соколовский М.Н. Оценки длины диагностического слова конечного автомата. // Кибернетика, №2, 1976, с. 16-21.

5Соколовский М.Н. Сложность порождения подстановок и эксперименты с автоматами // Методы дискретного анализа в теории кодов и схем, вып. 29, 1976, с. 68-86

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА С.-Петербург

_ОЭ 200 СахМ€

верхней, получил A.A. Карацуба8, а также, независимо от него, Т. Хиббард7. Последний автор также получил точную оценку для безусловного установочного эксперимента.

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

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

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

вКарацуба A.A. Решение одной задачи из теории конечных автоматов. // УМН, 1960, т.15, вып. 3, с. 157-159.

THibbard Т.Н. Least upper bounds on minimal terminal state experiments for two classes of sequential madones. // J Assoc. Сотр., 1961, №4, p. 601-612[русский перевод cu. "Кибернетический сборник"(новая серия), 1966, вып. 2, с. 7-23].

*Aho A.V., Dahbura А.Т., Lee D., and M. Umlt Uyar An Optimization Technique for Protocol Conformance Test Generation Based on UIO Sequences and Rural Chinese Postman Tours. // IEEE Transactions on Communications, 1991, 39(11), p. 1604-1815.

eLee D. and Yannakakis M. Principles and Methods of Testing Finite State Machines - A Survey. // Proceedings of The IEEE, 1996, v. 84, n. 8, p. 1090-1123.

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

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

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

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

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

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

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

Цель работы.

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

Методы исследования.

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

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

Результаты работы являются новыми и заключаются в следующем:

1. Получены точные значения функции Шеннона длины Я-отличающего и /с-отличающего слова для пары состояний автомата в классе всех автоматов с не более чем п состояниями.

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

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

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

Теоретическая и практическая ценность.

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

Апробация работы.

Результаты работы докладывались и обсуждались на следующих семинарах Механико-матеметического факультета МГУ: семинар "Теория автоматов", под руководством академика В.Б. Кудрявцева (2004, 2005, 2006), семинар 'Элементы кибернетики" под руководством профессора Подколзина А. С. (2004, 2005, 2006), семинар "Математические вопросы кибернетики" под руководством академика О.Б. Лупанова (2005), на 13-ой международной конференции "Проблемы теоретической кибернетики" в г. Казань (2002), на 14-оЙ международной конференции "Проблемы теоретической кибернетики" в г. Пенза(2005), на VIII Международном семинаре "Дискретная математика и ее приложения" в Москве(2004).

Публикации.

Основное содержание диссертации опубликовано в 7 работах, список которых приведен в конце автореферата [1-7].

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

Диссертация состоит из введения, трех глав и списка литературы. Текст диссертации изложен на 101 странице. Список литературы содержит 25 наг именований.

Содержание работы

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

Приведем основные понятия и обозначения, используемые в работе.

Обозначим через N, No и R — множество натуральных, неотрицательных целых и действительных чисел соответственно. Пусть также [n, m] = {i £ N I п < г < т}. Запись к \ п обозначает, что к является делителем га. Обозначим через НОД(тг,т), НОК(п,т) — наибольший общий делитель и наименьшее общее кратное чисел пит соответственно.

Пусть /(тг), д(п) — две положительные вещественные функции от натурального аргумента. Через /(n) ~ д(п) будем обозначать асимптотическое равенство f(n) и д(п), т.е.

Нп, /(П) 1

lim —г-г = 1.

п-юо д{п)

Через /(п) < д(п) будем обозначать утверждение

ййМ^.

п-*ао д{п)

Рассмотрим конечное непустое множество Е, которое мы будем называть алфавитом, а его элементы символами. Словом длины I над Е назовем ¿-элементную последовательность а(1)а(2)... а(1) символов из Е. Обозначим длину слова а через |о|. Определим конкатенацию aß двух слов а = а(1)... а(1) и ß = ¿(1)... Ь(тп) как слово а(1)... a(l)b( 1)... b(m). Легко видеть, что множество всех слов над Е образует полугруппу относительно операции конкатенации. Доопределим эту полугруппу до моноида, добавив пустое слово А такое, что а А = Аа = а для всех слов а. Положим |Л| = 0. Обозначим через Е* множество всех слов (включая пустое) над Е. Пусть а = а(1)а(2)... а(1). Обозначим символом а]т слово а(1)а(2)... а(т), где 1 < т < I. Положим а]о = Л. Пусть а € Е*, тогда полагаем а" = (ха „ . а,

п G N. Считаем, что а0 = Л.

Под конечным детерминированным автоматом Мили (в дальнейшем автоматом) будем понимать объект 21 = (A,Q, В,<р,ф), где A, Q, В — конечные непустые множества, называемые, соответственно, входным алфавитом, алфавитом состояний и выходным алфавитом, а <р :Q х A—* Q к ■ф : Q х А —» В — функции переходов и выходов.

Автомат можно представлять себе как абстрактное вычислительное устройство работающее в дискретном времени t = 1,2— В каждый момент времени t устройство находится в состоянии q(t) € Q, на его вход подается a(f) € Л, а на выходе появляется b(t) € В. Функционирование этого устройства задается следующей системой соотношений:

Г q(t + l) = <p(q(t),a(t)), m

\b(t) = mt)Mt))- {)

Если зафиксировать начальное состояние автомата q( 1) = q, а на его вход подать последовательность a(l)a(2).. .a(í), то из системы (1) однозначно определяется соответствующая выходная последовательность 6(1)6(2)... b(l) и последовательность состояний q(l)q(2)... q(l + 1).

Введем следующие обозначения:

а( 1)... а(1)) = 6(0, ±{q, a(l)... a(l)) = 6(1)... 6(Z), <p{q,a(l)...a(Q) = q(l + 1), <p(q,a(l)...a(l)) = f(l)...q(l + 1).

Положим также ifi(q, Л) - Л, ip(q, Л) = q. Пусть Q' С Q и a € А*, тогда обозначим через ip(Q', а) множество {<p(q, а) \ q е Q1}.

Автоматом без выхода назовем объект 21 = (A, Q, <р), который отличается от обычного автомата тем, что у него нет выходного алфавита и функции выходов. Функции <p(q, а) и <p(q, а) определяются как у обычного автомата.

Назовем состояния qi, q2 автомата 21 = (A, Q, В, <р, ф) отличимыми, если существует входное слово а € А* такое, что V'i(9i,Q!) Ф ^OftiЕсли такого слова не существует, то скажем, что состояния q\, — неотличимы. Автомат приведенный, если все его состояния попарно отличимы. Будем говорить, что слово а склеивает состояния qi, q2, если ip(qi,a) = <p(q2,a).

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

Пусть S — некоторое непустое множество и на нем задана функция сложности I: S —> No. Определим сложность класса как

L(S) = max ¿(а).

Например, возьмем в качестве 5 — множество К,„ всех автоматов с не более чем п состояниями. Положим

1(Щ = шах яи

где /(21, дг) — минимальная длина отличающего слова для <7ь ф в автомате 21 = (А, <5, В, <р, ф) и 0, если ф, дг неотличимы. Тогда, согласно теореме Мура об отличимости, Ь(К,„) = п — 1.

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

В параграфе 1.1 рассматривается понятие Я-отличимости состояний. Рассмотрим конечный автомат 21 = (А, В, <р, ф). Зададим на множестве его выходных символов В рефлексивное и симметричное отношение Я, которое будет интерпретироваться нами как отношение неразличимости выходных символов с точки зрения внешнего наблюдателя. Например, если считать, что на множестве В задана метрика р, то, зафиксировав некоторое положительное е > 0, можно определить Я как отношение е-близости:

хЯу р(х, у) < е.

Очевидно, что так определенное Я действительно рефлексивное и симметричное отношение. Покажем, что и любое рефлексивное и симметричное отношение является отношением е-близости для некоторых р и е. Действительно, пусть К — произвольное рефлексивное и симметричное отношение на В. Рассмотрим метрику на В, заданную следующим образом:

0, когда 61 = 62

р(61,62) = когда 61 Ф 62, Ъ\Шц

1, когда 61 Ф 62, не &1Я&2

Легко видеть, что р действительно метрика и они вместе с е = | задают

Я.

Продолжим отношение Я на множество слов одинаковой длины. Скажем, что аЯр, где а = а(1)а(2)... а(1) и /? = 6(1)6(2)... 6(/), если а(г)Я6(г), г — 1,1. Пусть Кв — множество автоматов с выходным алфавитом В. Зафиксируем Я и рассмотрим автоматы 21ь212 с входным алфавитом А и выходным В.

Определение. Назовем состояния ^ автомата 21^и <72 автомата 21г Я-отличимьши словом а 6 А*, если не верно, что "ф^дх, а)(#2' • Состояния q\ и <72 называются Н-отпличимыми, если существует входное слово, которое их Я-отличает. В противном случае будем говорить, что <71 и дг И-неогпличимы.

Пусть (211,212, ^ъ <72) — минимальная длина входного слова, Я-отличающего состояния 91 и <72 автоматов Щ и 212 и 0, если такого слова нет. Положим

¿я(Я1, а2) = тах/д(а1,а2,91,(?2).

вьй

В случае, если Я = Щ = 212 вместо ¿д(21,21) будем писать 1д(01). Обозначим через /С® — множество автоматов с выходным алфавитом В и с не более чем п состояниями. Определим по описанной выше схеме функции Шеннона ЬЯ(К$) и Ья(К2 х К*) так:

£,«(£*) = так/д(21),

М^п х О = я гл(а1,1а2),

т.е. — минимальная длина Я-отличающего слова в худшем слу-

чае на всех парах Я-отличимых состояний <71 и д2 у всех автоматов 21 с п состояниями, а х АС^) — аналогичная функция для двух автоматов

спит состояниями. Заметим, что = х = 0, если

Я = В х В, поскольку у любого автомата не будет Я-отличимых состояний. Поэтому в дальнейшем полагаем, что Лф В х В.

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

/г-в\ I я — 1, когда Я - транзитивно ) — < „(„_!) , 0

I ' 2 когда л - нетранзитивно

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

1) х К^) = п + тп — 1, когда Я - транзитивно;

2) х /С®) ~ пт, когда Я - нетранзитивно, п, т —» оо.

В параграфе 1.2 рассматривается понятие ^-отличимости состояний. Пусть а = а(1)...о(0, /? — 6(1)...Ь(0- Обозначим через рн(а,/3) число позиций г € {1,2,..., 1} в которых о(г) / Ь(г).

Определение. Назовем состояния 91, дг автомата 21 к-отличимыми словом а, если рн(1р(дх,а), 1/>(дг,&)) ^ А, т.е. соответствующие выходные слова отличаются не менее чем в Л позициях. Будем говорить, что два состояния к-отличимы, если существует слово, которое их к-отличает. Если такого слова нет, то скажем, что состояния к-неотличимы.

Пусть ¿*(21,41,42) — минимальная длина Л-отличающего их слова для 41,42 и 0, если такого слова нет; /*г(21) — максимальное значение (21,41,42) на всех парах состояний автомата 21. Рассмотрим функцию Шеннона

Ьк(К,„) = шах** (21). Теорема 1.3. Имеет место равенство

Ьк(1Сп) = п-1 + (к-1:)^=Д

В параграфе 1.3, как естественное обобщение ^-отличимости, рассматривается понятие (¿-отличимости.

Определение. Назовем два состояния и-отличимыми, если они к-отличимы для любого к € N.

Возникает задача определить для какого минимального к у автомата с ^ п состояниями ^-отличимость двух состояний влечет их (¿-отличимость.

Теорема 1.4. Если состояния 41,42 автомата 21 из ¡Сп ¡-отличимы и I >

, то они и-отличимы. Теорема 1.5. Существует автомат с п состояниями, у которого есть два "("-1) - отличимых состояния, не являющиеся ш - отличимыми. * В параграфе 1.4 исследуются так называемые решетчатые автоматы,

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

жества целочисленной решетки. Часть параметров таких автоматов подается на выход и называется наблюдаемыми параметрами, а все остальные параметры — скрытыми. Таким образом, множеством выходных символов у них также является некоторое подмножество целочисленной решетки. Если считать два выходных символа г-близкими, г 6 N. когда их компоненты отличаются не более чем на г, то возникает задача об г-отличимости двух состояний такого автомата. Легко видеть, что эта задача является частным случаем задачи об Я-отличимости, (параграф 1.1), рассматриваемой для подкласса решетчатых автоматов, где Я — отношение е-близости для метрики р специального вида на множестве выходных символов и е = г.

Определение. Назовем к-мерной целочисленной щ х ... х щ-решеткой с началом в точке х° = (ж®,..., х°) € Zk множество

= {(хь • ■ •, хн) € Ък | х°{ < < х\ + щ, г = М}.

Рассмотрим класс автоматов с множеством состояний функция выходов которых имеет вид ф({х\,..., х*), а) = (хъ ...,хт), 2 < то < к. Введем на множестве выходов Z£J.....^ метрику

р(х,у) = так \х{-у{\,

Х = (Х1,...,Хт),У- (Уъ---,Ут)-

Если зафиксировать натуральное число г, то вместе с метрикой р оно определяет на множестве рефлексивное и симметричное отношение е-близости Я, где е = г. Рассмотрим функцию Шеннона для длины й-отличающего слова для класса .Д£'™.1Пк. Теорема 1.6. Имеет место соотношение

при Пи.. . ,Пк,Г —► оо.

Если считать, что выполняется щ = Пг = ... = п* и

Ьг(п, к, т) = ЬР1Г(А%™.1Пк),

где п = п\ • «2 •... • Пк — число состояний автомата, то получим, что

Ьг(п, к, т) х гт • п2~т/к при п, г -> оо.

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

Глава 2 посвящена изучению отличимости состояний при искажении информации на входе.

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

Множество слов Бк = {ах,...,а*} назовем к-отпличающим множеством для <7х и если:

1. Каждое слово а< € Я* отличает состояния ф, ф.

2. Никакое собственное начало слов а, € не отличает состояния <71, <72.

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

Определение. Сложностью ¿-отличающего множества 5* = {qi, • ■ •, а*} назовем величину

l(S*)-¿М, ¿=1

а высотой

h{Sk) = max Ы-

Пусть для состояний <7i, qi автомата 21 существует fc-отличающее множество. Обозначим через ¿£(<71, <72) и h^{q\,q-i) — наименьшую сложность и высоту, соответственно, fc-отличающего множества для q\, Cfc и 0 если такого множества не существует. Введем две функции Шеннона

l(n,k)= тах 4(?ь<й)> ae^n.ij.ij

h(n,k)= max /i&fabfc).

,91,92

где максимум берется по всем автоматам 21 € /С„ и парам q\, их состояний.

Теорема 2.1. Справедливы следующие равенства:

ft(n, А) = fc(n — 1).

Пусть в автомате 21 существуют два состояния <71, <72 такие, что любое входное слово длины I отличает их. Обозначим через ¿я(<71,92) минимальное такое / и 0 если такого I не существует. Введем функцию Шеннона следующим образом

= „ max ¿51(91,92),

где максимум берется по всем автоматам 21 е Кп и парам их состояний

Теорема 2.2. Имеет место равенство 1(п) = "fr*"1?.

Определение. Рассмотрим автомат 21 = (A,Q, В,<р,1р). Назовем два его состояния qi,q2 k-кратно отличимыми словом а, если они отличимы любым словом с/, где />#(<о*) ^ fc. Два состояния qi, 92 k-кратно отличимы, если существует слово, которое их fc-отличает. Если такого слова нет, то qi, <72 называются к-кратно неотличимыми. Очевидно, что 0-кратная отличимость совпадает с обычной отличимостью состояний.

Пусть для состояний дх, ф автомата 21 существует й-кратно отличающее слово. Обозначим через (21, <71,(72) длину минимального такого слова и О если его не существует. Рассмотрим следующую функцию Шеннона:

~ „ и?8* Чг,

где максимум берется по всем автоматам 21 € Кп и парам <71, <72 их состояний.

В общем случае задача оказалась достаточно трудной и пока удалось получить некоторые оценки логарифма величины Ьк(К.„).

Теорема 2.3. Имеет место:

кп2

п < 1о§2 £*(£„) < — при п -> оо, к > 0.

Если ограничиться случаем к = 1, то справедлива более точная верхняя оценка.

Теорема 2.4. Имеет место 1пЬ1(/С„) < п1пп при п > 1.

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

Теорема 2.5. Имеет место 1пЬк(К.2:П,2) > ч/пЬш при п —> оо.

Определение. Два состояния д\, автомата 21 называются и-кратно отличимыми, если они Л-кратно отличимы для любого к > 0.

Теорема 2.6. Если два состояния <71, дг автомата 21 € Кп к-кратно отличимы, где к ^ то они ш-кратно отличимы. Теорема 2.7. Для каждого целого п, п > 2, существует автомат 21 е £п такой, что для любого к 6 {0,1,..., — 1} найдется пара состояний <71, которая к-кратно отличима, но не (к + 1)-кратно отличима.

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

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

Как показывает следующая теорема класс С кратно-приведенных автоматов в точности удовлетворяет нашим требованиям.

Теорема 2.8. Если автомат 21 кратно-приведенный, тпо все его состояния и -кратно отличимы.

Следствие 2.1. Если для автомата 21 € Кп существует слово, к-кратно отличающее все пары его различных состояний и к > 0, то всегда найдется такое слово длины не более (к + 1)=^.

Обозначим через Сп — множество кратно-приведенных автоматов с не более чем п состояниями. Рассмотрим для этого класса функцию Шеннона Lk(Cn) /г-кратной отличимости двух состояний.

Теорема 2.9. Имеет место равенство

Глава 3 посвящена изучению сложности безусловных диагностических экспериментов с автоматами.

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

Определение. Простым безусловным диагностическим экспериментом (далее п.б.д.э.) для Q! назовем такое слово а, что для любых двух различных состояний q\,qi&Q выполнено ip(qi,a) ф ip(q2,a).

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

Теорема 3.1. Если у автомата 21 е К.„ существует п.б.д.э. для к-элементного подмножества состояний Q1, то всегда существует такой эксперимент а, где |а| < (jheo(Vkink) П) fc 00j < n/2.

В тоже время в работе4 приводится пример автомата с п состояниями, у которого для некоторого fc-элементного подмножества состояний, к < п/2, минимальная длина п.б.д.э. есть Таким образом теорема 3.1 дает

асимптотику логарифма функции Шеннона 1о(п, к) для сложности п.б.д.э. для fc-элементного подмножества состояний, у автомата с п состояниями

при п, к —> оо и к/п —> а, где a G (0,1/2). Действительно, поскольку log2 С* = /Гг(а)п + о(п), при этих условиях, то

log2Ь(п,к) ~ Я2(а)п, где Яг (а) = —a log2 а — (1 - а) log2(l - а) — двоичная энтропия.

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

Публикации автора по теме диссертации.

1. Пантелеев П.А. Об отличимости состояний автоматов. // Дис- , кретная математика, 2003, т. 15, вып. 3, с. 76-90.

2. Пантелеев П.А. Об отличимости состояний решетчатых автоматов. // Интеллектуальные системы, 2005, т. 8, с. 529-542.

3. Panteleev P.A. On distinguishability of states of automata. // Discrete ' Mathematics and Applications, 2003, vol. 13, num. 4, p. 355-370.

4. Пантелеев П.А. О некоторых обобщениях понятия отличимости состояний автомата. // Тезисы докладов XIII международной конференции "Проблемы теоретической кибернетики", Казань, 27-31 мая 2002, ч. 2, с.

141. '

5. Пантелеев П.А. О модификации отличимости состояний автомата. // Тезисы докладов V международного конгресса по математическому моделированию, 2002, с. 203. '

6. Пантелеев П.А. Обобщенные эксперименты с автоматами. // Тезисы докладов VIII международного семинара "Дискретная математика и ее приложения", 2004, с. 144.

7. Пантелеев П.А. Об отличимости автоматов при искажениях на входе. I/ Тезисы докладов XIV международной конференции "Проблемы теоретической кибернетики", Пенза, 23-28 мая 2005, с. 114.

I Í V t

I !

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

МГУ им. М.В. Ломоносова.

Подписано в печать Л?. 65. ОВ

Формат 60 х 90 1 /16. Усл. печ. л. /,0

Тираж 100 экз Заказ /§

Л0&6А

№11506

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Пантелеев, Павел Анатольевич

Введение

1 Отличимость состояний при искажениях на выходе

1.1 Я-отличимость. 1.2 А;-отличимость

1.3 ^-отличимость.

1.4 Решетчатые автоматы .*.

2 Отличимость состояний при искажениях на входе

2.1 Отличимость множеством слов.

2.2 А;-кратная отличимость.

2.3 ^-кратная отличимость.

2.4 Кратно-приведенные автоматы.

3 Сложность безусловных диагностических экспериментов

3.1 Оценка сложности безусловного диагностического эксперимента.

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

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

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

Проблема тестирования конечных автоматов изучалась многими авторами, и в этой области получены математические результаты, имеющие как теоретическое, так и прикладное значение. Самые ранние работы в этой области датируются еще пятиде-) сятыми годами прошлого столетия. В статье Э. Мура "Умозрительные эксперименты с последовательностными машинами" [9] впервые формально определяется понятие эксперимента с автоматами, имеющее центральное значение в области тестирования конечных автоматов. В этой же работе автор получает ряд оценок сложности некоторых видов экспериментов, а также показывает их достижимость. Более систематическое изучение сложностных характеристик экспериментов с автоматами было проведено А. Гиллом[11]. Им впервые были получены оценки длин различных видов диагностических экспериментов.

Дальнейшее изучение диагностических экспериментов было проведено М.Н. Соколовским[16, 17], который получил асимптотику функции Шеннона длины простого условного диагностического эксперимента для всех состояний автомата, а также достаточно точные оценки для подмножеств состояний. Он также первым обозначил связь между диагностическими экспериментами и сложностью порождения элементов в полугруппах [18].

Еще в работе Мура[9] была получена верхняя оценка длины условного установочного эксперимента. Нижнюю оценку для него, совпадающую с верхней, получил А.А. Карацуба[12], а также, независимо от него, Т. Хиббард[5]. Последний автор также получил точную оценку для безусловного установочного эксперимента.

В последнее время эксперименты с автоматами находят практическое применение в задаче тестирования коммуникационных протоколов, используемых при построении локальных сетей, а также сети Internet [1, 8]. Коммуникационный протокол представляет собой набор правил, регламентирующих процесс обмена информацией в сети. Он описывается некоторым формальным документом, называемым стандартом. У стандарта может быть несколько программных реализаций. Стандарт протокола и его реализации моделируются конечными автоматами. Задача тестирования реализации протокола заключается в проверке того, что она удовлетворяет данному стандарту, т.е. в построении тестового эксперимента для данного стандарта в классе всех возможных его реализаций.

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

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

Обозначим через N, No и R — множество натуральных, неотрицательных целых и действительных чисел соответственно. Пусть также [п, т] = {г 6 N [п ^ i ^ га}. Запись к \ п обозначает, что к является делителем п. Обозначим через НОД(п, т), НОК(п, т) — наибольший общий делитель и наименьшее общее кратное чисел пит соответственно.

Пусть /(п), д(п) — две положительные вещественные функции от натурального аргумента. Через /(n) ~ д(п) будем обозначать асимптотическое равенство f(n) и д(п), т.е.

Иш Щ = 1. п~*оо д[п)

Через f(n) < g(n) будем обозначать утверждение

Рассмотрим конечное непустое множество £, которое мы будем называть алфавитом, а его элементы символами. Словом длины I над £ назовем Z-элементную последовательность а(1)а(2). а(1) символов из Е. Обозначим длину слова а через |а|. Определим конкатенацию а(3 двух слов а = а(1). а{1) и (3 = 6(1). Ь(т) как слово а(1). a(l)b(l). Ь(т). Легко видеть, что множество всех слов над Е образует полугруппу относительно операции конкатенации. Доопределим эту полугруппу до моноида, добавив пустое слово А такое, что аА = Аск = а для всех слов а. Положим |А| = 0. Обозначим через Е* множество всех слов (включая пустое) над Е. Пусть а = а(1)а(2). а(1). Обозначим символом а]т слово а(1)а(2). а(т), где 1 ^ т ^ /. Положим си]о = А. Пусть а € £*, тогда полагаем ап = р?а?.<%, пб N. Считаем, что а0 = А.

Под конечным детерминированным автоматом Мили (в дальнейшем автоматом) будем понимать объект 21 = (A,Q,B,ip,il')), где A, Q, В — конечные непустые множества, называемые, соответственно, входным алфавитом, алфавитом состояний и выходным алфавитом, а р : Q х А —> Q и ф \ Q х А—+ В — функции переходов и выходов.

Автомат можно представлять себе как абстрактное вычислительное устройство (рис. 1) работающее в дискретном времени t = 1,2 — В каждый момент времени t устройство находится в состоянии q{t) £ Q, на его вход подается a(t) € Л, а на выходе появляется b(t) G В. Функционирование этого устройства задается следующей системой соотношений: п

7(1).•<?(/ + !) а(1).а(1) Q b(l).b(l)

Рис. 1. q(t+l) = <p(q(t),a(t)), m b(t)=mt)Mt))

Если зафиксировать начальное состояние автомата q(l) = q, а на его вход подать последовательность а(1)а(2). a(Z), то из системы 1 однозначно определяется соответствующая выходная последовательность 6(1)6(2). Ь{1) и последовательность состояний q(l)q(2).q(l + l).

Введем следующие обозначения: ф(д, а( 1). аЩ) = НО, Ш а(1) • • • о(0) = К1) • • • К1), p(q, а(1). а(/)) = q(l + 1), <p(q, а(1). a(Q) = q( 1) .q(l+ 1).

Положим также ip(q,h) = Л, tp{q,k) = g. Пусть Q' С Q и a € А*, тогда обозначим через ip(Q',a) множество Mq,<x) \ qeQ'}.

Автоматом без выхода назовем объект 21 = (A, Q,<p), который отличается от обычного автомата тем, что у него нет выходного алфавита и функции выходов. Функции <p(q, а) и <p(q, а) определяются как у обычного автомата.

Для задания автомата часто будет использоваться графический язык диаграмм Мура. Диаграмма Мура для автомата 21 = (A,Q,B,<p,ip) это ориентированный граф вершинами которого являются состояния из Q. Для каждой вершины q £ Q и вход

Рис. 2. ного символа а £ А проводится ребро (рис. 2а) из q в q' = <£>(#, а), помеченное парой (а, Ъ), где Ъ = ip(q, а).

Если для некоторого состояния q функция ^(д, а) = Ъ для всех a € А, то символ Ъ из пометок ребер выходящих из q перемещаем в q (рис. 2Ь).

Назовем состояния q\, 52 автомата 01 = (A,Q,B,(p,i/>) отличимыми, если существует входное слово a G А* такое, что ipi(qi, а) ф (<72, а). Если такого слова не существует, то скажем, что состояния qi, <72 — неотличимы. Автомат приведенный, если все его состояния попарно отличимы. Будем говорить, что слово а склеивает состояния q\, 52, если ip{qi,a) = (p(q2,a).

Пусть S — некоторое непустое множество и на нем задана функция сложности I : S —>• No- Определим сложность класса как

L(S) = maxl(s).

Например, возьмем в качестве S — множество /Сп всех автоматов с не более чем п состояниями. Положим

2t)= max /(21,01,02), где /(2l,gi,02) — минимальная длина отличающего слова для 01,02 в автомате 2t = (A,Q, В,(р,ф) и 0, если 01,02 неотличимы. Тогда, согласно теореме Мура об отличимости[9], L(JCn) = п — 1.

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

Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

Основные результаты диссертации опубликованы в работах [19]-[25].

Диссертация состоит из введения, трех глав и библиографии. Она изложена на 101 страницах, библиография содержит 25 наименований. Нумерация теорем и лемм в каждой главе своя.

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

Глава 1

Отличимость состояний при искажениях на выходе

1.1 ^-отличимость

Лемма 1.1. Если 21 € R — рефлексивное и симметричное отношение на В, qo и qo' — два произвольных R-отличимых состояния автомата 21, то существует слово а, R-отличающее

I I ^ п(п— 1) их и такое, что |о;| ^ v 2 '.

Доказательство. Пусть а = а(1)а(2). а(1) — кратчайшее слово, -R-отличающее состояния qo и qo'. Определим две последовательности qo,qi,., qi-i и qd, qi,., q\-\ следующим образом: q{ — (p(q0, a(l)a(2). а(г)), g/ = (p(q0', a(l)a(2). а(г)), г = 1, Z — 1.

Легко видеть, что минимальная длина входного слова, Rотличающего состояния qi,q'i, есть I — г. Действительно, слово а(г + 1 )а(г + 2).а(1) .R-отличает состояния qi,q[ и, если бы существовало слово (3, $3\ < I — г, также Л-отличающее эти состояния, то слово а(1)а(2). a(i)(3 Д-отличало бы состояния qo,q'o и имело бы длину меньшую I. Это противоречит выбору слова а. Очевидно, что все пары в последовательности {q0, qo}, {qi, q$,., {qi-i, qi-i} различны, поскольку они имеют различные минимальные длины 72-отличающих слов. Следовательно I не превосходит числа неупорядоченных пар из множества Q, т.е. I ^ nin~1) Лемма доказана.

Теорема 1.1. Имеет место в j п — 1, когда R - транзитивно п(п2 ^, когда R - иетранзитивно

Доказательство. Пусть 21 G и R — произвольное рефлексивное и симметричное отношение на В. Если R — транзитивно, то оно — отношение эквивалентности на В, разбивающее его на классы эквивалентности В\,В2,. ,Bk, k ^ 2. Рассмотрим автомат 21 = (A,Q, B,(p,ip), где Q — множество состояний 01, В = {Bi, В2,., Вк} и Tp{q, а) = В{, когда a) G Д. Очевидно, что состояния q, q' автомата 21 jR-отличимы словом а точно тогда, когда они отличимы этим словом в автомате 21. Тогда согласно теореме Мура[9] минимальная длина отличающего слова в автомате 21 не больше п — 1 и получаем неравенство Lr(JC^) ^ п — 1. Рассмотрим автомат 21 = ({0}, {q1, q2,., qn}, В, ip, яр) с заданным отношением эквивалентности R на множестве его выходных символов, и пусть не верно, что b\Rb2, где bi,b2 6 В. Диаграмма Мура этого автомата изображена на рис. 1.1. Из нее видно, что

Рис. 1.1. для состояний q1 и q2 минимальная длина ^-отличающего слова равна п — 1. Таким образом, мы доказали, что если R — транзи-тивно, то Lr{K,B) = п — 1.

Пусть теперь R — нетранзитивно. Установим, что Lr{K*) = В силу леммы 1.1 получаем LR{K%) ^

Докажем, что можно построить автомат 21 G /С^, у которого существуют два Д-отличимых состояния q\, qi такие, что минимальная длина Д-отличающего их слова равна . Тем самым покажем, что Lr{1C= .

Для этого рассмотрим автомат1 21 = ({0,1 },Q, В,(р,ф), где Q = {q°, q1,., <?п-1}, функция выходов мы определим позднее, а функция переходов определяется следующим образом: = modn; vta"-1^) = q°, ¥>(<?', o) = q\i Ф n- 1. Диаграмма Мура для этого автомата приведена на рис. 1.2.

Упорядочим всевозможные пары состояний автомата 21. Пусть Qrs = Wi qs+k~r mod "}, где n — 2k, в случае четного п, и п = 2к+1 в случае нечетного п, и fc = [|].

1Этот автомат впервые был рассмотрен в работе [4] для получения нижней оценки синхронизирующего слова о

• Если п = 2к, то порядок следующий:

Q°0 = {q°,qkh Q°i = {q\qk+1}, Ql-i = {qk~\ qn~1},

Ql = {q\qk~1}, Q\ = {q\qkh QLi = qk~2h

Q2o = {q°,qk~2}, Q\ = {q\qk~1}, Ql-i = {qn~\ qk~3},

Qt^iq^q1}, Q\~l = {q\q2}, Qkn~-\ = {q^1, q°}■

• Если n = 2k + 1, то порядок следующий:

Q°o = {q°,qk}, Q°i = {q\qk+1h • QU = {«Г1,**"1}, Ql = {q\qk~1}, Q\ = {q\qk}, QU = {q^1, qk~2},

Qo'1 = Q\~l = {q\q2}, Qkn-\ = {qn-\qQ}.

Рассмотрим таблицу 1.1: к п = 2к

Q ¥>№,0)

QI-г = QJ <38

Qkn-\ = {<in-\<?} fa0} QS"1

Qrn-i = {qn-\qk-r~l}\ 0 < г < к - 1 QS

QUr-i = {ik+r-\<f-l}\ 0 < г < п — к ^fc+r-l Qk+r

Qrs,s ^ п— 1,к + г — 1; n~\iQrs Qrs+1 п = 2к + 1

Q i)

Q°k = {q\qn-1} Qk+l

Qt i = {qn~\q°} fa0} Qo~'

Qn-i = {9n"1,9fc~r~1}; 0 < r < A; - 1 05

0<r<n — /г — 1 (y— 1

Ф + n-l£Qrs

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Пантелеев, Павел Анатольевич, Москва

1. Aho A.V., Dahbura A.T., Lee D., and M. Umit Uyar

2. An Optimization Technique for Protocol Conformance Test Generation Based on UIO Sequences and Rural Chinese Postman Tours. // IEEE Transactions on Communications, 1991, 39(11), p. 1604-1615.

3. Babai L., Seress A. On the diameter of Cayley graphs of the symmetric group. // Journal of Combinatorial Theory Series A, 1988, v. 49 n. 1, p. 175-179.

4. Babai L., Seress A. On the diameter of permutation groups. / / European Journal of Combinatorics, 1992, v. 13 n. 4, p. 231-243.

5. Cerny J. Poznamka к homogenym eksperimentom s konechnymi automatami. // Math.-Fyz. Cas., 1964, v. 14, p. 208-215.

6. Hibbard Т.Н. Least upper bounds on minimal terminal state experiments for two classes of sequential machines. // J. Assoc. Сотр., 1961, №4, p. 601-612русский перевод см. "Кибернити-ческий сборник"(новая серия), 1966, вып. 2), с. 7-23].

7. Holzmann G.J. Design and validation of protocols: a tutorial. // Computer Networks and ISDN Systems, 1993, v. 25, p. 9811017.

8. Landau E. Uber die Maximalordnung der Permutationen gegebenes Grades. // Archiv der Math, und Phys., 1903, p. 92103.

9. Lee D. and Yannakakis M. Principles and Methods of Testing Finite State Machines A Survey. // Proceedings of The IEEE, 1996, v. 84, n. 8, p. 1090-1123.

10. Moore E.F. Gedanken-experiments on sequential machines. // Automata Studies, 1956, p. 129-153русский перевод см. "Автоматы" (сб. статей), 1956, ИЛ, с. 179-210].

11. Shah S. An inequality for the arithmetical function g(x). //J. Ind. Math. Soc. 3, 1938, p. 316-318.

12. Гилл А. Введение в теорию конечных автоматов. // Наука, 1966, 272 с.

13. Карацуба А.А. Решение одной задачи из теории конечных автоматов. // УМН, 1985, т.15, вып. 3, с. 157-159.

14. Кудрявцев В.Б., Подколзин А.С., Ушчумлич Ш.М.

15. Введение в теорию абстрактных автоматов. // Изд-во МГУ, 1985, 174 с.

16. Кудрявцев В.В., Алешин С.В., Подколзин А.С. Элементы теории автоматов. // Изд-во МГУ, 1985, 320 с.

17. Прахар К. Распределение простых чисел. // Изд-во "Мир", 1967, 513 с.

18. Соколовский М.Н. О диагностических экспериментах с автоматами. // Кибернетика, №6, 1971, с. 44-49.

19. Соколовский М.Н. Оценки длины диагностического слова конечного автомата. // Кибернетика, №2, 1976, с. 16-21.

20. Соколовский М.Н. Сложность порождения подстановок и эксперименты с автоматами. // Методы дискретного анализа в теории кодов и схем, вып. 29, 1976, с. 68-86.

21. Работы автора по теме диссертации

22. Пантелеев П.А. Об отличимости состояний автоматов. // Дискретная математика, 2003, т. 15, вып. 3, с. 76-90.

23. Пантелеев П.А. Об отличимости состояний решетчатых автоматов. // Интеллектуальные системы, 2005, т. 8, с. 529542.

24. Panteleev P. A. On distinguishability of states of automata. // Discrete Mathematics and Applications, 2003, vol. 13, num. 4, p. 355-370.

25. Пантелеев П.А. О некоторых обобщениях понятия отличимости состояний автомата. // Тезисы докладов XIII международной конференции "Проблемы теоретической кибернетики", Казань, 27-31 мая 2002, ч. 2, с. 141.

26. Пантелеев П.А. О модификации отличимости состояний автомата. // Тезисы докладов V международного конгресса по математическому моделированию, 2002, с. 203.

27. Пантелеев П.А. Обобщенные эксперименты с автоматами. // Тезисы докладов VIII международного семинара "Дискретная математика и ее приложения", 2004, с. 144.

28. Пантелеев П.А. Об отличимости автоматов при искажениях на входе. // Тезисы докладов XIV международной конференции "Проблемы теоретической кибернетики", Пенза, 23-28 мая 2005, с. 114.