Универсальное тестирование в частных классах автоматов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Пономаренко, Александр Владимирович

• Пономаренко, Александр Владимирович
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Пономаренко, Александр Владимирович

ВВЕДЕНИЕ.

ГЛАВА 1. ПОСТАНОВКА ЗАДАЧ ДИССЕРТАЦИОННОГО ИССЛЕДОВАНИЯ. ИССЛЕДОВАНИЕ НОВОЙ КЛАССИФИКАЦИИ АВТОМАТОВ. ВЫБОР ПОДКЛАССОВ ДЛЯ ИССЛЕДОВАНИЯ МИНИМИЗАЦИИ УНИВЕРСАЛЬНОГО ТЕСТИРОВАНИЯ.

1.1. Постановка задач минимизации универсальных тестов.

1.2. Описание используемой классификации конечных детерминированных автоматов.

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

1.4. Некоторые замечания о выборе классов для исследования.

ГЛАВА 2. МИНИМИЗАЦИЯ УНИВЕРСАЛЬНЫХ ТЕСТОВ В ИССЛЕДУЕМЫХ ПОДКЛАССАХ.

2.1. Исследование структуры универсальных тестов.

2.2. Построение двух вариантов универсальных тестов для исследования

2.3. Сокращение универсальных тестов в выбранных подклассах.

2.4. Минимальные универсальные тесты в подклассе линейных (4,2,2) -автоматов.

ГЛАВА 3. УНИВЕРСАЛЬНОЕ ТЕСТИРОВАНИЕ КОМПОНЕНТЫ СТРУКТУРНОГО АВТОМАТА.

3.1. Общие положения структурной теории автоматов.

3.2. Задача тестирования компоненты структурного автомата.

3.3. Трансляция универсального теста в последовательной композиции автоматов.

Введение диссертации (часть автореферата) на тему «Универсальное тестирование в частных классах автоматов»

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

В современных информационных технологиях конечные автоматы являются моделью для многих компонентов аппаратного и программного обеспечения: программное обеспечение, используемое для разработки и проверки цифровых схем; лексические анализаторы стандартных компиляторов; программное обеспечение для сканирования (поиск заданных слов, фраз и других шаблонов) больших текстовых массивов, таких как наборы Web-cтpaниц; программное обеспечение для проверки различного рода систем с конечным числом состояний (протоколы связи или защищенной передачи информации).

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

Впервые, автоматы, как абстрактные модели нейронных сетей, были введены в 1943 году в работе Мак-Калокка и Питтса [1]. В дальнейшее автоматы неоднократно использовались для описания нейронных сетей [2].

Определение конечного детерминированного автомата как совокупности пяти объектов: А = (8,Х,У,8Д), где Б, X и У - конечные непустые множества, а 8 и X (функции переходов и выходов соответственно) - отображения вида: 8:8 х X -» 8 и А,: 8 х X -> У, введено в работе [3]. Такой тип автоматов получил название автоматы типа Мили. Другой основной тип конечных детерминированных автоматов - автоматы типа Мура введены в работе [4]. Конечный автомат типа Мура есть пятерка: объектов: А = (8,Х, У,8, ц), где 8, X и У-конечные непустые множества, а 8 и ц, (функции переходов и отметок состояния соответственно) - отображения вида: 8:8хХ-»8 и ц:8-»У. Равносильность двух этих типов автоматов показана во многих работах, например в работе [5]. Из работы Э. Мура [4] берет начало теория экспериментов с автоматами. В дальнейшем теория конечных автоматов и экспериментов с автоматами получила развитие во многих работах зарубежных и отечественных авторов (см., например [6 - 18]).

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

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

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

1) Диагностическая задача. Задано:

- А = (Б, X, У, 8, X) - известный конечный детерминированный автомат;

- 80 с 8 - подмножество допустимых начальных состояний. Требуется:

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

Ув е БоХУб' е 80|){в Ф в'-> ЯГ(в,р) * .

2) Установочная задача. Задано:

- А = (8,Х, У,8Д) - известный конечный детерминированный автомат;

- 80 с 8 - подмножество допустимых начальных состояний. Требуется:

- построить эксперимент, позволяющий установить автомат А в известное конечное состояние, т. е. найти реХ*, которое удовлетворяет предикату (Ув^' е 80){5*(з,р) Ф 5*(б',р) -» (в, р) Ф А,*(б',р)} .

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

Эдвард Ф. Мур в 1956 г. в работе [4] показал, что существует решение установочной задачи с помощью простого безусловного эксперимента, предложил метод решения установочной задачи и нашел оценку длины эксперимента. Поиск решения предлагается осуществлять путем построения установочного дерева.

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

В 1962 году в работе [6] Артур Гилл свел задачу распознавания автомата в конечном семействе автоматов к установочной задаче. Задача распознавания автомат представляет собой определение (с точностью до изоморфизма), минимальной формы автомат путем проведения эксперимента.

На практике, часто возникает задача распознавания автомата, о котором известно, что он принадлежит к определенному конечному семейству автоматов, т.е. необходимо определить, каким из автоматов семейства а = {А;}м, где А! =(8|,Х,У,8!Д1)- конечный детерминированный автомат, является автомат А = (БД, У, 5, X). Решение этой задачи может быть найдено приложением такого слова р е X*, которое удовлетворяет предикату е 1)0/5 е ^о/з' е *} -> Х](з,р) * Х]@,р)}.

Критерием существования решения этой задачи является то, что семейство автоматов должно образовывать исключительный класс - ни одно состояние автомата А} недолжно быть эквивалентно никакому состоянию автомата Ар для любых [ ф], т. е. выполняется условие:

VI,] е 1)0/8 6 ЗДУз' е * } -> (Зи 6 Х*)Х](8,и) Ф и)}

Решение задачи распознавания автомата, предложенное А. Гиллом, сводится к замене семейства автоматов а = {А!}1-б1, где А1 =(81,Х,У,5|Д!), расщепляемым конечным детерминированным автоматом а-СиадУ.и^и*!). в который каждый автомат семейства входит как е1 1еI ¡€1 изолированный подавтомат, и решению для этого расщепляемого автомата установочной задачи методом Мура. А. Гиллом из оценки Мура для установочной задачи получена оценка длины 1 простого безусловного эксперимента для решения задачи распознавания автомата в семействе автоматов: 1 < (2п -1)(№1 -1), где п - максимальное число состояний автоматов семейства и N - число автоматов в семействе.

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

В 1981-1982 годах на международных конференциях Твердохлебовым В. А. [19,20] был предложен метод универсального решения задачи распознавания автомат в заданном семействе автоматов.

Универсальным тестом в классе К(Х, п) семейств сравнимых конечных детерминированных автоматов с памятью по объему не превосходящих п состояний будем называть слово р е X*, которое для каждого семейства этого класса, удовлетворяющего условию исключительности, удовлетворяет условию: (VI, j е 1)(\/з е ^ХУэ' е вр^ * ] -> А,|(в,р) * ^(в'.р)}.

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

В дальнейших работах Твердохлебова В. А. с 1982 г. по 2005 г. (см., например [21-23]) продолжено исследование универсальных тестов - найдены оценки длины и методы построения универсальных тестов. Итоговые результаты работ по универсальному тестированию конечных детерминированных автоматов приведены в работе [23].

В работах Твердохлебовым В.А. были получены следующие результаты.

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

2) Найдена оценка длины универсального теста: |р| < |Х|П +п1 + п2 + п - 2.

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

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

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

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

1. Функционирование системы в работоспособном состоянии, когда управление осуществляется в штатном режиме.

2. Контроль исправности состояния системы и принятие решение о возможности дальнейшей эксплуатации.

3. Диагностирование системы, т. е. локализация дефекта возникшего в системе по месту или функции.

4. Ремонт системы - восстановление ее работоспособности с первоначальной функциональностью.

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

6. Частичное восстановление системы - восстановление с ухудшением ее характеристик и функциональных возможностей.

7. Вывод системы из эксплуатации.

Взаимосвязь описанных выше этапов приведена на рис. 1.

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

Точка 1 - точка начала контрольных процедур определяется:

- расчетным путем, во время проектирования системы;

- появлением в работе системы явных дефектов;

- срабатыванием аварийной сигнализации и т.д.

Для выполнения процедур контроля используется некоторый тест р^Х*, направленный на выявление конкретного класса дефектов р1={{А1,11,61,»{А|2}|2е,2,.,{А^}1ке1к} - множество подмножеств автоматов, распознаваемых на слове р| е X*, жестко зависящим от распознаваемого класса дефектов методом Мф) (Решение задачи распознавания автомата по А. Гиллу). Любое слово из символов входного алфавита может рассматриваться как тест для системы, поэтому множество тестов бесконечно.

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

Подобное описание является устоявшимся представлением жизненных циклов сложных систем и отражено в работах многих авторов (см., например,

25-29]). Недостатком такого подхода является то, что тест pi е X* строиться методом М(Р;), зависящим от конкретного подкласса дефектов е1, '{А|2 }\2€12.{А(к }|ке1к}» и не может быть использования для проверки системы на другие неисправности. Поэтому изменение выбранного подкласса неисправностей (как во время проектирования системы, так и во время ее эксплуатации) требует нового применения метода для построения нового теста.

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

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

При универсальном тестировании в процедурах контроля и диагностирования используется тест реХ*- универсальный тест, на котором распознаются все распознаваемые классы дефектов ^, методом М(тах|8|,|Х|), зависящим только от мощности входного алфавита и глубины памяти технической системы. Универсальное тестирование повышает надежность и эффективность управления системой в работоспособном состоянии. Повышение надежности осуществляется за счет замены наборов частных тестов (тестов, ориентированных на конкретное подмножество неисправностей) общим тестом, предельно расширяющим анализируемое множество неисправностей. Это позволяет увеличить продолжительность этапов эксплуатации системы и уменьшить количество этапов контроля и диагностирования. Эффективность управления повышает за счет сокращения временных интервалов для контроля и диагностирования на этапе эксплуатации системы, и за счет упрощения разработки процедур контроля и диагностирования на этапе проектирования системы.

Как было замечено ранее, значительным недостатком универсальных тестов, предложенных В. А. Твердохлебовым, явилась их большая длина. Так, например, по полученной оценки, универсальный тест для относительно простой дискретной технической системы с объемом памяти 25 и четырьмя двоичными входами имеет длину 2 * Ю1270символов.

В диссертации предлагается новый подход к построению универсальных тестов, основанный на использовании специфических свойств диагностируемых систем, исследуется возможность сокращения универсального теста в некоторых специфических классах автоматов. Для выделения классов автоматов используется предложенная Твердохлебовым В. А. в работах [29,30] в 2003-2004 годах классификация автоматов по свойствам их функций переходов и выходов, основанная на фундаментальной классификации Поста для функций алгебры логики. Исследование сокращения оценки длины универсального теста выполнено в подклассах класса (4,2,2) -автоматов: линейных; самодвойственных; монотонных; линейных и самодвойственных; линейных и монотонных; монотонных и самодвойственных; линейных, самодвойственных и монотонных автоматов.

Диссертационная работа состоит из трех глав основного текста.

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

Во второй главе проводиться выбор двух вариантов универсальных тестов, которые используются для исследования сокращения оценки длины универсального теста в подклассах линейных; самодвойственных; монотонных; линейных и самодвойственных; линейных и монотонных; монотонных и самодвойственных; линейных, самодвойственных и монотонных (4, 2, 2) -автоматов. Дополнительно исследована структура универсальных тестов, показано, что по структуре они совпадают с последовательностями де Брюина. Доказаны леммы, позволяющие представлять последовательности де Брюина в двоичном алфавите функциями алгебры логики, полином Жегалкина которых имеет достаточно простую структуру. Сокращение универсальных тестов выполнено двумя методами: суффиксное и префиксное сокращение. Полученные оценки сформулированы в виде теорем. Так же в этой главе представлены минимизированные универсальные тесты для исследуемых подклассов. Более подробно рассмотрен подкласс линейных автоматов, для которого найдены минимальные по длине универсальные тесты.

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

Большинство полученных в работе результатов носят количественный характер. Поэтому для получения этих результатов использовался метод доказательного вычислительного эксперимента. В таких полных вычислительных экспериментах исключаются интерполяция и экстраполяция, вероятностные процедуры, основным является логический вывод на основе полного перебора исследуемых объектов. Такой подход обосновывается в работах академика А.П. Ершова и H.H. Моисеева (см., например [31,32]).

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

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Пономаренко, Александр Владимирович

ЗАКЛЮЧЕНИЕ

В результате проведения диссертационного исследования было доказано значительное сокращение длин универсальных тестов для основных подклассов автоматов относительно универсальных тестов для всего класса (для линейных автоматов - на 5 порядков, для самодвойственных автоматов - на 5 порядков, для монотонных автоматов - на 4 порядка) и найдены конкретные минимизированные универсальные тесты в подклассах линейных (4,2,2)-автоматов, самодвойственных (4,2,2) - автоматов, монотонных (4,2,2)-автоматов, линейных и самодвойственных (4,2,2) - автоматов, линейных и монотонных (4,2,2) - автоматов, самодвойственных и монотонных (4,2,2)-автоматов, линейных, самодвойственных и монотонных (4,2,2) - автоматов. Для линейных (4, 2. 2) - автоматов были определены минимальные универсальные тесты.

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

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

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

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

Результаты, изложенные в диссертационной работе прошли научную апробацию на семи международных конференциях. По результатам исследований в период с 2004 по 2006 годы было опубликовано 9 статей [30, 51-58] в том числе статья в журнал, входящем в Перечень периодических изданий, рекомендованных ВАК РФ для публикации основных результатов диссертаций на соискание ученой степени [58].

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

Список литературы диссертационного исследования кандидат физико-математических наук Пономаренко, Александр Владимирович, 2007 год

1. McCulloch W.S., A logical calculus of the ideas immanent in nervous activity /W.S. McCulloch, W. Pitts//Bulletin of Mathematical Biophysics.- 1943.-№5.- p. 115-133.

2. Клини С. К. Представление событий в нервных сетях и конечных автоматах //Сб. "Автоматы" под ред. К. Э. Шеннона и Дж. Маккарти: Пер. с англ.—М.: ИЛ, 1956.-С. 15-67.

3. Mealy G.H. Method for synthesizing sequential circuits /G.H. Mealy //Bell System Techn.- 1955.-J. 34.-p. 1045-1079.

4. Мур Э. Ф. Умозрительные эксперименты с последовательностными машинами /Э.Ф. Мур //Автоматы: Сб. под ред. К.Э. Шеннона и Дж. Маккарти.-Пер. с англ.- М.:ИЛ.- 1956.- С. 179-212.

5. Блох А.Ш. О задачах, решаемых последовательностными машинами /А.Ш. Блох //Проблемы кибернетики: Сб. статей под ред. A.A. Ляпунова.- М., 1960.-Вып.З.- С. 81—88.

6. Гилл А. Введение в теорию конечных автоматов /А. Гилл,- Пер. с англ.- М.: Изд-во «Наука», 1966.- 272 с.

7. Глушков В. М. Абстрактная теория автоматов / В. М. Глушков // Успехи матем. наук.-1961.-Т. 16, № 5.-С. 3-62.

8. Логика. Автоматы. Алгоритмы /М. А. Айзерман, Л. А. Гусев, Л. И. Розоноэр и др.- М.: Физматгиз, 1963.- 556 с.

9. Ю.Спивак М.А. Введение в абстрактную теорию автоматов / М.А. Спивак.-Саратов: Изд-во Сарат. ун-та, 1970.- 108 с.

10. Минский М. Вычисления и автоматы /М. Минский,- Пер. с англ.- М.: Мир, 1971.-364 с.

11. Трахтенброт Б. А. Конечные автоматы. Поведение и синтез /Б. А. Трахтенброт, Я.М. Барздинь.- М.: Наука, 1970.- 400 с.

12. Богомолов A.M. Эксперименты с автоматами /A.M. Богомолов, A.C. Барашко, И.С. Грунский.- Киев: Наук, думка, 1973.- 144 с.

13. Н.Богомолов A.M. Контроль и преобразования дискретных автоматов /A.M. Богомолов, И.С. Грунский, Д.В. Сперанский.- Киев: Наук, думка, 1975.- 174 с.

14. Брауэр В. Введение в теорию конечных автоматов /В. Брауэр.- Пер. с нем.-М.: Радио и связь, 1987.- 392 с.

15. Твердохлебов В. А. Логические эксперименты с автоматами /В. А. Твердохлебов.- Саратов: Изд-во Сарат. ун-та, 1988.- 184 с.

16. Карпов Ю.Г. Теория автоматов /Ю. Г. Карпов.- СПб.: Питер, 2002.- 224 с.

17. Хопкрофт Дж. Ведение в теорию автоматов, языков и вычислений /Дж. Хопкрофт, Р. Мотвани, Дж. Ульман.- Пер. с англ.- М.: Издательский дом "Вильяме", 2002.- 528 с.

18. Твердохлебов В. А. Универсальное решение задачи распознавания автоматов /В. А. Твердохлебов // Методы и системы технической диагностики.-Саратов: Изд-во Сарат. ун-та, 1981.- Вып. 2.

19. Твердохлебов В. А. Универсальные генераторы тестов и системы диагностирования /В. А. Твердохлебов / Техническая диагностика,- Ростов-на/Д.: Изд-во РИСИ, 1982.

20. Твердохлебов В.А. Детерминированная и вероятностная оценки универсальных тестов /В. А. Твердохлебов //Марковские случайные процессы и их применение.- Саратов: Изд-во Сарат. ун-та, 1988.- Вып. 4.

21. Богомолов A.M. Диагностика сложных систем /A.M. Богомолов, В.А. Твердохлебов.- Киев: Наук, думка, 1974.- 128 с.

22. Пархоменко П.П. Основы технической диагностики: (Оптимизация алгоритмов диагностирования, аппаратурные средства) / П.П. Пархоменко, Е.З. Согомонян //Под ред. П.П.Пархоменко. М.: Энергия, 1981. - 320 с.

23. Резчиков А.Ф. Управление и диагностирование в сложных системах /А.Ф.Резчиков, В.А.Твердохлебов.- Саратов: Изд-во Сарат. ун-та, 1997.- 128 с.

24. Резчиков А.Ф. Управление жизненными циклами сложных систем /А.Ф.Резчиков, В.А.Твердохлебов.- Саратов: Изд-во Сарат. ун-та, 2000.- 110с.

25. Смирнов А.К. Управление жизненными циклами сложных систем /А.К.Смирнов, В.А.Твердохлебов.- Саратов: Изд-во Сарат. ун-та, 2000,- 130с.

26. Твердохлебов В.А. Классификация конечных автоматов и информационные технологии в техническом диагностировании /В.А. Твердохлебов //Высокие технологии путь к прогрессу. - Саратов: Изд-во «Научная книга», 2003.- с. 9398.

27. Твердохлебов В.А Классификация конечных автоматов по свойствам функций переходов и выходов /В.А Твердохлебов, A.B. Пономаренко //Сб. научных трудов ИПТМУ РАН.- Саратов: Изд-во СГТУ, 2004.- с. 16-25.

28. Ершов А.П. Научные основы доказательного программирования / А.П. Ершов //Вестн. АН СССР, 1984.- № ю.- С. 9-19.

29. Моисеев H. Н. Математика ставит эксперимент /Н. Н. Моисеев,- М,: Наука, 1979.- 224 с.

30. Post Е. Introduction to a general theory of elementary propositions /Е. Post //Amer. J. Math.-1921.- №43.- p. 163-185

31. Яблонский C.B. Функции алгебры логики и классы Поста /С. В. Яблонский, Г. П. Гаврилов, В. Б. Кудрявцев.- М.: Наука, 1966.- 120 с.

32. Яблонский C.B. Ведение в дискретную математику /С. В. Яблонский.- М.:1. Высш. шк., 2002.- 384 с.

33. Марченков С.С. Замкнутые классы булевых функций /С.С. Марченков.- М.: ФИЗМАТЛИТ, 2000.- 128 с.

34. Сидоренко О. И. Секреты логической зависимости /О.И. Сидоренко.-Саратов: Изд-во Сарат. ун-та, 2001,- 56 с.

35. Токхейм Я. Основы цифровой электроники /Я. Токхейм.- М.: Мир, 1988.420 с.39.0падчий Ю.Ф. Аналоговая и цифровая электроника /Ю.Ф. Опадчий.- М.: Радио и связь, 1996,- 768 с

36. Миловзоров О. В. Электроника /О. В. Миловзоров, И.Г. Панков.-М.: Высш. шк., 2005.- 288 с.41.de Bruijn N.G. A Combinatorial Problem /N.G. de Bruijn //Nederl. Akad. Wetensch. Proc., 1946.- vol. 49.- p. 758-764

37. Lippel B. A Method for Obtaining Complete Digital Coding Chains /В. Lippel, I.J Epstein //IRE Trans., 1957.- vol. EC-6.- p. 121.

38. Глушков В. M., Некоторые проблемы синтеза цифровых автоматов /В.М. Глушков //Жур. вычислительной математ. и матем. физики.- т. 1, № 3,1961.

39. Глушков В.М. Синтез цифровых автоматов /В.М. Глушков.- М:, Физматгиз, 1962.- 476 с.47.3акревский А. Д. К синтезу последовательностных автоматов / А. Д. Закревский //Труды Сибирского физико-технического ин-та.- вып. 40,1961.

40. Поспелов Д.А. Логические методы анализа и синтеза схем /Д.А Поспелов-М.: Энергия, 1974.- 368 с.

41. Гаврилов М.А. Композиция и декомпозиция комбинационных автоматов /М.А. Гаврилов //В кн.: Теория автоматов.- М.: Наука, 1976,-с. 34-71.

42. Гаврилов М.А. Логическое проектирование дискретных автоматов / М.А. Гаврилов, В.В. Девятков, Е.И Пупырев.- М.: Наука, 1977.-352 с.

43. Пономаренко А. В. Параметры тестов для распознавания начального состояния в классе (4, 2, 2) автоматов /А. В. Пономаренко //Проблемы точной механики и управления: Сб. науч. тр.- Саратов, 2004.- С. 159-163.

44. Пономаренко А. В. Исследование геометрических образов функционирования в классе (4, 2, 2) автоматов /А. В. Пономаренко //Информационно-управляющие системы на железнодорожном транспорте.-Харьков, 2004.- №4,5.- С.86-88.

45. Пономаренко А. В. Минимизация универсальных тестов в классе (4, 2, 2) -автоматов /А. В. Пономаренко //Автоматизация проектирования дискретных систем: Материалы V Межд. конф.- Минск, 2004.- Том 1.- С.211-216.

46. Пономаренко А. В. Недостижимые траектории состояний при управлении автоматами из частных классов /А. В. Пономаренко //Аналитическая теория автоматического управления и её приложения: Труды 2-ой Межд. науч. конф.-Саратов, 2005.- С.79-80.

47. Пономаренко А. В. Универсальные тесты для специальных классов конечных автоматов /А. В. Пономаренко //Радиоэлектронные и компьютерные системы,- Харьков, 2006.- С. 115-118.

48. Пономаренко А. В. Оптимизация универсального тестирования поведения автоматов /А. В. Пономаренко //Интеллектуальные системы и компьютерные науки: Материалы IX Межд. конф.- Москва, 2006.- Том 1. ч.2- С.213-215.

49. Пономаренко А. В. Критерий трансляции универсального теста в композициях (4,2,2) автоматов /А. В. Пономаренко //Проблемы и перспективы прецизионной механики и управления в машиностроении: Материалы Межд. конф.- Саратов, 2006.- С.290-295

50. Пономаренко А. В. Универсальное диагностирование в частных классах конечных автоматов /А. В. Пономаренко //Мехатроника, Автоматизация, Управление.- Москва, 2006.- №12.- С. 17-24.