Линейные автоматы над подкольцами рациональных чисел тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Ронжин Дмитрий Владимирович

• Ронжин Дмитрий Владимирович
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Ронжин Дмитрий Владимирович

Введение

Глава 1. Определения и обозначения

1.1 Основные понятия и вспомогательные утверждения

1.2 Дополнительные обозначения

Глава 2. Линейные автоматы над полем рациональных чисел

2.1 Мощность порождающих множеств по операциям композиции и суперпозиции

2.2 Условия полноты систем с добавками

Глава 3. Линейные автоматы над кольцом

двоично-рациональных чисел

3.1 Условия А-полноты систем с добавками

3.2 Алгоритмическая разрешимость проверки непринадлежности предполным классам

3.3 Мощности порождающих подмножеств в А-предполных классах.

Заключение

Список литературы

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

Введение

Одной из классических задач дискретной математики является исследование условий полноты функциональных систем [25] по заданному набору операций. Примером функциональной системы может служить множество функций fc-значной логики с введенными операциями суперпозиции. Одними из первых трудов, посвященных проблеме проверки полноты указанной функциональной системы, являются работы Э. Поста [61; 62]. В частности, в терминах предполных классов им описан критерий полноты конечных систем функций в случае к = 2, причем число предполных классов в этом случае оказалось равным пяти. В работах Поста также была описана структура решетки замкнутых классов для функций двузначной логики и показано, что указанная решетка имеет конечную ширину и счетную глубину. Дальнейшее развитие исследований в этом направлении проведено A.B. Кузнецовым [27; 28]. В частности, им получен алгоритм, распознающий полноту конечных систем функций fc-значной логики. Следует подчеркнуть, что при всяком к упомянутая функциональная система является конечнопорождешюй по операциям суперпозиции.

Другим примером функциональной системы является множество конечных автоматов, начало исследованию которых было положено в трудах Дж. фон-Неймана [34], С.К. Клини [21], М.Л. Минского [31], Э.Ф. Мура [33]. Классическими операциями на множестве конечных автоматов считаются операции суперпозиции (£) и композиции (К) [ ]. Элементы этой функциональной системы потактово преобразуют последовательности, состоящие из элементов фиксированного конечного множества, называемого входным алфавитом, в последовательности из фиксированного конечного множества, называемого выходным алфавитом, используя в ходе своего функционирования дискретную память, представленную в виде элементов конечного множества, называемого алфавитом состояний. Функционирование конечного автомата в каждый такт могут быть описаны с помощью функций fc-значной логики.

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

Множество конечных автоматов по своей сложности существенно отличается от множества функций fc-значной логики. Так, в частности, В.Б. Кудрявцевым было показано, что мощность множества предполных классов по операции композиции равна континууму при фиксированном к. В то же время известно, что из всякого множества конечных автоматов можно выделить конечную полную систему по операциям композиции, что существенно отличает случай операций композиции от случая операций суперпозиции, поскольку всякое полное множество по операциям суперпозиции в классе конечных автоматов непременно бесконечно. При этом C.B. Алешиным [2] было показано, что можно выделить счетно-бесконечную систему конечных автоматов, полную по операциям суперпозиции и являющуюся базисом. В работе C.B. Алешина [1] о вложенности группы Бернсайда в класс конечных автоматов продемонстрирована сложность класса конечных автоматов.

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

Исследование задачи распознавания полноты в классе конечных автоматов приводит к отрицательному результату в работе М.И. Кратко [24] была показана алгоритмическая неразрешимость задачи полноты конечных множеств конечных автоматов по операциям композиции. В силу полученно-

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

Одним из подходов, использованных в попытках преодоления алгоритмической неразрешимости распознавания полноты, является введение дополнительных операций замыкания в классе автоматов так В.А. Бу-евичем [12; 13] был введен оператор аппроксимационного замыкания (А-замыкания). Указанный оператор определяет множество автоматов, которые могут быть промоделированы до любого заданного такта при помощи некоторой автоматной системы применением операций композиции. В общем случае, аппроксимационное замыкание фиксированного множества конечных автоматов порождает более широкие классы автоматов, чем замыкание оператором композиции. Однако, как и в случае операций композиции, проверка полноты конечной системы конечных автоматов по операциям А-замыкания оказалась алгоритмически неразрешимой задачей. A.A. Летичевским [29] был получен критерий полноты множеств автоматов Медведева (т.е. автоматов, выдающих свое состояние в качестве результата функционирования) в случае работы со специальной операцией замыкания.

Еще одним подходом в преодолении алгоритмической неразрешимости является исследование задачи полноты конечных систем в случае наличия определенных автоматов в качестве добавок к данной системе. В.А. Буевичем была показана алгоритмическая разрешимость задачи А-полноты в случае наличия в качестве добавки к системе всех булевых функций. Д.Н. Бабиным [4 7; 9] для каждого замкнутого класса решетки Поста дан ответ на вопрос об алгоритмической разрешимости проблемы проверки полноты конечных множеств конечных автоматов, если к этим множествам добавлять данный замкнутый класс. Д.Н. Жуком [19; 20] была доказана неразрешимость задачи полноты в классе дефинитных автоматов, кроме того, им было доказано, что этот класс содержит континуум предполных подклассов.

В качестве еще одного направления исследования может служить рассмотрение подклассов в классе конечных автоматов, для которых задача проверки полноты может оказаться алгоритмически разрешимой. Так при рассмотрении конечных автоматов одним из наиболее интересных для исследования подклассов является класс линейных автоматов. В книге А. Гилла «Линейные последовательные машины» [17] приведено подробное описание свойств линейных автоматов, изучены свойства линейных автоматов с нулевым начальным состоянием. Также в ней описаны некоторые условия для возможности кодирования автоматов, функционирующих над конечными полями, используя наборы линейных функций подобное представление называется линейной реализуемостью. Подробное исследование вопросов линейной реализуемости автоматов приведено в диссертации С.Б. Родина [37].

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

При фиксированном простом числе р и натуральном числе т в произвольном поле Галуа Ерт существует конечная приведенная А-критериальная система состоящая из следующих А-предполных классов:

АЗк = [У1,УР,М(£2),Т3,Р3'\8 = 0,1,...,к - М' = 1,2,...,/},

где к = рт7 / — число различных простых делителей т в Е^. Классы Т8 обозначают множество автоматов, сохраняющих число в в первый такт, — множество линейных автоматов, зависящих в первый такт не более чем от одной переменной, Ур — множество линейных автоматов, сумма коэффициентов которых в первый такт равна единице в Е^ Р8/ — автоматы, коэффициенты которых в первый такт лежат в фиксированном подполе а М(£,2) — автоматы, игнорирующие второй такт входных значений (т.е. с коэффициентом О

при формальной переменной £ у переменных). Таким образом, в случае полей Галуа число предполных классов при исследовании А-полиоты в классе линейных автоматов оказывается конечным.

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

Тем не менее, несмотря на положительный результат для класса конечных линейных автоматов, в реальных приложениях могут требоваться автоматы, функционирующие над бесконечными алфавитами. В частности, нейронные сети, являющиеся автоматными схемами без памяти, используют в качестве функциональных элементов умножители на произвольные действительные числа. Интерес также представляют так называемые нейронные схемы с памятью, которые могут моделировать ассоциативную память. В 1982 году Д. Хопфил-дом [60] было предложено использовать рекуррентные нейронные сети для моделирования ассоциативной памяти. Используя этот подход были получены различные архитектуры нейронных сетей, которые в настоящее время активно используются в задачах автоматического распознавания речи и перевода [59]. Для класса нейронных схем с памятью B.C. Половниковым [36] исследованы вопросы нелинейной сложности и глубины. В реальных приложениях память, используемая в нейронных схемах, может хранить произвольные значения, ограниченные лишь объемом хранения данных. Таким образом, при математическом моделировании подобных схем удобно считать бесконечными алфавиты, над которыми функционирует схема.

Диссертационная работа посвящена исследованию вопросов полноты и доказательству условий полноты конечных автоматных систем в классе линейных автоматов, функционирующих на бесконечных структурах, т.е. автоматов, входной, выходной алфавит которых, как и алфавит состояний бесконечные множества. При переходе к изучению автоматов этого класса (в частности автоматов, функционирующих над полем рациональных чисел) [38 45], возникают сложности в описании условий ^-полноты конечных систем, поскольку в данном классе автоматов не существует конечных систем, полных по операциям композиции. Тем не менее, обнаруживаются свойства, объединяющие данный класс с общим случаем в частности становится ясно, что в исследуемом классе существует счетный £-базис.

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

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

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

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

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

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

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

Исследования конечных автоматов имеют прикладное значение в сфере распознавания образов [8; 30], защиты информации [14; 35], построения датчиков псевдослучайных чисел [32], создания компьютерных систем обучения [3], синтеза схем [18], прогнозирования [15], диагностики [10], моделировании биологических процессов [16; 57] и др.

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

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

Объектом исследования является класс линейных автоматов, функционирующих в дискретном времени над бесконечными структурами.

и

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

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

Для достижения поставленной цели решаются следующие задачи.

1. Сформулировать и доказать условия полноты, ^-полноты и А-полноты конечных систем линейных автоматов, функционирующих в поле рациональных чисел.

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

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

4. Исследовать вопросы конечнопорожденности полученных А-предполных классов.

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

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

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

3. Впервые проведено исследование вопросов алгоритмической разрешимости проблемы проверки полноты в классе линейных автоматов над кольцом двоично-рациональных чисел.

4. Впервые исследованы вопросы конечной порожденное™ А-предполных классов в классе линейных автоматов, функционирующих над кольцом двоично-рациональных чисел.

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

Методология и методы исследования. В работе применялись методы дискретной математики, алгебры и комбинаторики.

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

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

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

3. Описание счетно-бесконечного набора А-предполных классов в классе линейных автоматов, функционирующих над кольцом двоично-рациональных чисел.

4. Условия А-полноты конечных автоматных систем с добавками, функционирующих над кольцом двоично-рациональных чисел в терминах описанных предполных классов.

5. Оценка алгоритмической сложности проблемы полноты систем линейных автоматов над двоично-рациональными числами с добавками.

6. Результаты исследования вопроса о конечной порожденное™ выделенных А-предполных классов.

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

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

— научный семинар «Математические вопросы кибернетики» кафедр дискретной математики и математической теории интеллектуальных систем механико-математического факультета и математической кибернетики факультета вычислительной математики и кибернетики МГУ имени М.В.Ломоносова, 2021 год;

— XII Международная конференция «Интеллектуальные системы и компьютерные науки», секция «Математика и компьютерные науки», МГУ имени М.В.Ломоносова, 2021 год;

— научный семинар «Теория автоматов» под руководством профессора В.Б.Кудрявцева, механико-математический факультет МГУ имени М.В.Ломоносова, 2021 год;

— научный семинар «Нейронные сети» под руководством доцента А.А.Часовских, научного сотрудника В.С.Половникова, старшего научного сотрудника А.А.Говорко, механико-математический факультет МГУ имени М.В.Ломоносова, 2020 год;

— международные научные конференция студентов, аспирантов и молодых ученых «Ломоносов-2021» и «Ломоносов-2019», секция «Математика и механика»;

— ежегодные научные конференции «Ломоносовские чтения-2020», «Ломоносовские чтения-2019», «Ломоносовские чтения-2018», секция «Математика».

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

Объем и структура работы. Диссертация состоит из введения, 3 глав и заключения. Полный объём диссертации составляет 100 страниц. Список литературы содержит 62 наименования.

Публикации. По теме диссертации автор имеет 8 печатных работ. Результаты, выносимые на защиту, изложены в 5 статьях, опубликованных в рецензируемых научных изданиях, рекомендованных для защиты в диссертационном совете МГУ по специальности 01.01.09 Дискретная математика и математическая кибернетика и входящих в базы цитирования Scopus, Web of Science и RSCI.

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

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

В главе 1 приведены основные обозначения и сформулированы вспомогательные утверждения.

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

Вводятся понятия множеств формальных степенных рядов от переменной £ в поле рациональных чисел (обозначается через и кольце двоично-

рациональных чисел (обозначается через (£,)). Элементы данных множеств

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

Определяются вспомогательные системы линейных автоматов, с помощью которых в дальнейшем проводится исследование полноты:

В = {ад, 11(х),У+(х,у),У.с(х)1с € О}, В' = {У+ (х,у), V,—1 )(ж), £,1(ж)}, где

1. У+ (х,у) сумматор с двумя входами,

2. Е,а(х) — задержка с начальным состоянием а,

3. ^(с)(ж) — умножитель на число с.

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

системами, т.е.:

ДО) = к (в), ¿(О #) = к (в').

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

К(О) = {ЩIр€ Ои,з(О) = 1,нод(р(£), д(£)) = 1}, К(О#) = {ЩIр€ о#И, ДО) = 1,ноД(Р(£), <2Ю) = 1},

где НОД обозначает операцию взятия наибольшего общего делителя, О[£], Ощ. [£] — многочлены над О и Ощ. С учетом определении операции деления можно заметить, что ЩО) является иодкольцом в О™(£)? а ЩОж.)

является подкольцом в О™ (£,).

2"

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

УУ € Ь(О), 31 € N такое, что V(ж1,...,ж/): (О™) ^ О™, УУ' € Ь(Оъ), 31 € N такое, что У'(х1,...,х1): (О» ) ^ О™.,

причем найдутся Щ £ И^щ), Д; £ И(0>),ъ £ [0,/] такие что для произвольных а £ а.^ £ £ [1,/] ^входных рядов верно:

V(ах,...,а/) = Ев + Я\ • а + Я2 • а2 + ... + Щ • а/, У>(а[,...,а>1) = Я'0 + Л! • а1 + Я'2 • а'2 + ... + Щ • а[.

Множители ,Я'к называются коэффициентами отображения, причем через [т], Я'к [т] обозначаются коэффициенты при формальных степенных рядов и Я'к. Перемениая называется непосредственной, в случае если соответствующий ей коэффициент К^ не кратен £ как формальный степенной ряд, т.е. Д[0] = 0. Линейный автомат называется существенным, если он представляет собой отображение с не менее чем двумя непосредственными входами. Под кратностью в кольце двоично-рациональных чисел некоторому целому числу в работе понимается кратность числителя дроби в несократимом виде этому числу.

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

1. Для фиксированного к £ Ми множества

Р = {Рг1Рг —нечетное простое, % £ [1,^]},

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

Список литературы диссертационного исследования кандидат наук Ронжин Дмитрий Владимирович, 2022 год

Список литературы

1. Алешин, С. В. Конечные автоматы и проблема Бернсайда о периодических группах. / С. В. Алешин // Мат. заметки. — 1972. — Вып. 3. — С. 319 328.

2. Алешин, С. В. О суперпозициях автоматных отображений. / С. В. Алешин // Киев: Кибернетика. — 1975. — № 1. — С. 29 34.

3. Об автоматном моделировании процесса обучения / П. А. Алисейчик [и др.] // Дискретная математика. — 1996. — Т. 8, вып. 4. — С. 3 10.

4. Бабищ Д. Н. Разрешимый случай задачи о полноте автоматных функций / Д. Н. Бабин // Дискретная математика. — 1992. — Т. 4, № 4. — С. 41 55.

5. Бабищ Д. Н. О возможностях суперпозиции, при наличии в базисе автоматов фиксированной добавки из булевых функций и задержки / Д. Н. Бабин // Докл. РАН. - 1999. - Т. 367, № 4. - С. 439-441.

6. Бабищ Д. Н. О разрешимости проблемы полноты для автоматов / Д. Н. Бабин // Интеллектуальные системы. - 2007. - Т. 10. - С. 639-655.

7. Бабищ Д. Н. О классификации базисов в Pk по разрешимости проблемы полноты для автоматов / Д. Н. Бабин // Фундамент, и прикл. матем. — 2009. - Т. 15, № 5. - С. 33-47.

8. Бабищ Д. Н. Автоматные языки с частотным свойством естественных языков / Д. Н. Бабин, И. Л. Мазуренко, А. Б. Холоденко // Интеллектуальные системы в производстве. — 2013. Л'° 1. О. 9—13.

9. Бабищ Д. Н. О классификации автоматных базисов Поста по разрешимости свойств полноты и А-полноты / Д. Н. Бабин, А. Летуновский // Интеллектуальные системы. Теория и приложения. — 2015. — Т. 19, № 3. — С. 71-78.

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

11. Буевич, В. А. Построение простейшей универсальной о.-д. функции. /

B. А. Буевич // Проблемы кибернетики. — 1970. — Т. 22.

12. Буевич, В. А. Об алгоритмической неразрешимости распознавания А-пол-ноты для о. д.-функций / В. А. Буевич // Математические заметки. — 1972. - Т. 12, № 6. - С. 087 097.

13. Буевич, В. А. О полноте, А-полноте и ^полноте в классе автоматных отображений. / В. А. Буевич // Интеллектуальные системы. — 2000. — Т. 10. —

C. 613-638.

14. Галатенко, Л. 5. Автоматные модели защищенных компьютерных систем / А. В. Галатенко // Интеллектуальные системы. — 2007. — Т. 11, вып. 1—4. — С. 403 418.

15. Гасанов, Э. Э. Прогнозирование периодических сверхсобытий автоматами / Э. Э. Гасанов // Интеллектуальные системы. Теория и приложения. — 2015. - Т. 19, вып. 1. - С. 23-34.

16. Гераськина, Ю. Г. Об одной автоматной модели в биологии / Ю. Г. Герась-кина // Дискретная математика. — 2007. — Т. 19, № 3. — С. 122—139.

17. Галл. А. Линейные последовательностные машины. / А. Гилл. — 4-е издание. — Москва : НАУКА, 1974.

18. Глушков, В. М. Синтез цифровых автоматов / В. М. Глушков. — Москва : Физматгиз, 1962. — 476 с.

19. Жук, Д. Н. О неразрешимости проблемы полноты для дефинитных автоматов / Д. Н. Жук // Интеллектуальные системы. — 2008. — Т. 12, № 1. — С. 211-228.

20. Жук, Д. Н. Континуальность множества предполных классов в классе дефинитных автоматов / Д. Н. Жук // Фундаментальная и прикладная математика. — 2009. — Т. 15, вып. 4. — С. 29—36.

21. К лини, С. Представление событий в нервных сетях и конечных автоматах / С. Клини // Автоматы. — М.: ИЛ. — 1956. — С. 15—67.

22. Алгоритмы: построение и анализ / Т. Кормен [и др.]. — 3-е издание. — М. : «Вильяме», 2013. - 1328 с.

23. Кострикин, А. И. Введение в алгебру. Часть III. Основные структуры: Учебник для вузов. / А. И. Кострикин. — 3-е издание. — М. : Физматлиб, 2004. - 272 с.

24. Кратко, М. И. Алгоритмическая неразрешимость проблемы распознавания полноты для конечных автоматов / М. И. Кратко // ДАН СССР. — 1964. - Т. 155, № 1. - С. 35-37.

25. Кудрявцев, В. Б. Функциональные системы / В. Б. Кудрявцев. — Москва : МГУ, 1982. - 159 с.

26. Кудрявцев, В. Б. Введение в теорию автоматов / В. Б. Кудрявцев, С. В. Алешин, А. С. Подколзин. — Москва : НАУКА, 1985. — 320 с.

27. Кузнецов, А. В. О проблемах тождества и функциональной полноты для алгебраических систем / А. В. Кузнецов // Труды третьего всесоюзного математического съезда. М.: Изд. АН СССР. — 1956. — Т. 2. — С. 145 146.

28. Кузнецов, А. В. Структуры с замыканием и критерии функциональной полноты / А. В. Кузнецов // Успехи математических наук. — 1961. — Т. 16. - С. 201-202.

29. Летичевский, А. А. Условия полноты для конечных автоматов / А. А. Ле-тичевский // Вычислительная математика и математическая физика. — 1961. - № 4. - С. 702-710.

30. Мазуренко, И. Л. Автоматные методы распознавания речи : дис. ... канд. физ.-мат. наук : 01.01.09 / Мазуренко Иван Леонидович. — Москва : МГУ им. М.В. Ломоносова, 2001. — 119 с.

31. Минский, М. Некоторые универсальные элементы для конечных автоматов / М. Минский // Автоматы. — М.: ИЛ. — 1956. — С. 163—178.

32. Михалев, А. В. Цикловые типы семейств полилинейных рекуррент и датчики псевдослучайных чисел / А. В. Михалев, А. Нечаев // Математические вопросы криптографии. — 2014. — Т. 5, вып. 1. — С. 95—125.

33. Мур, Э. Умозрительные эксперименты с последовательными машинами / Э. Мур // Автоматы. - М.: ИЛ. - 1956. - С. 179-210.

34. Нейман, Д. Вероятностная логика и синтез надежных организмов из ненадежных компонент / Д. Нейман // Автоматы. — М.: ИЛ. — 1956. — С. 68-139.

35. Носов, В. А. О связи периодов состояний и периодов выходов автономных автоматов / В. А. Носов // Лесной вестник. — 2007. — Вып. 2. — С. 144-149.

36. Половников, В. С. Об оптимизации структурной реализации нейронных сетей : дис. ... канд. физ.-мат. наук : 01.01.09 / Половников Владимир Сергеевич. — Москва : МГУ им. М.В. Ломоносова, 2008.

37. Родин, С. Б. Размещение состояний автоматов : дис. ... канд. физ.-мат. наук : 01.01.09 / Родин Сергей Борисович. — Москва : МГУ им. М.В. Ломоносова, 2017.

38. Ронжин, Д. В. Линейные автоматы над полем рациональных чисел / Д. В. Ронжин // Интеллектуальные системы. Теория и приложения. — 2017. - Т. 21, № 4. - С. 144-155.

39. Ронжин, Д. В. А-полнота систем с добавками в классе линейных автоматов над кольцом двоично-рациональных чисел / Д. В. Ронжин // Интеллектуальные системы. Теория и приложения. — 2019. — Т. 23, № 4. — С. 125-131.

40. Ронжин, Д. В. Линейные автоматы над полем рациональных чисел. / Д. В. Ронжин // Материалы Международного молодежного научного форума «Ломоносов-2019», секция «Математика и механика». — 2019.

41. Ронжин, Д. В. Об условиях А-полноты линейных автоматов над двоично-рациональными числами / Д. В. Ронжин // Дискретная математика. — 2020. - Т. 32, № 2. - С. 44-60.

42. Ронжин, Д. В. О задаче А-полноты в классе линейных автоматов над кольцом двоично-рациональных чисел. / Д. В. Ронжин // Материалы

Международного молодежного научного форума «Ломоносов-2020», секция «Математика и механика». — 2020.

43. Ронжин, Д. В. Распознавание А-полноты конечных систем линейных автоматов с добавками над кольцом двоично-рациональных чисел / Д. В. Ронжин // Интеллектуальные системы. Теория и приложения. — 2021. - Т. 25, № 1. - С. 149—163.

44. Ронжин, Д. В. О конечной порожденности А-предполных классов в классе линейных автоматов над кольцом двоично-рациональных чисел / Д. В. Ронжин // Интеллектуальные системы. Теория и приложения. — 2021. - Т. 25, № 3. - С. 191—202.

45. Ронжин, Д. В. Исследование А-полноты линейных автоматов над пол кольни ми рациональных чисел. / Д. В. Ронжин // Материалы Международного молодежного научного форума «Ломоносов-2021», секция «Математика и механика». — 2021.

46. Часовских, А. А. Об алгоритмической разрешимости проблемы полноты для линейных автоматов / А. А. Часовских // Вестник Московского университета сер. 1, мат., мех. — 1986. Л'° 3. О. 82—84.

47. Часовских, А. А. О выразимости систем с сумматором в классе линейных автоматов / А. А. Часовских // Вестник Московского университета сер. 1, мат., мех. - 1990. - № 4. - С. 31-34.

48. Часовских, А. А. О полноте в классе линейных автоматов / А. А. Часовских // Математические вопросы кибернетики. — 1991. Т. 3.

С. 140-166.

49. Часовских, А. А. Проблема А-полноты линейно-автоматных функций над конечным полем / А. А. Часовских // Интеллектуальные системы. Теория и приложения. — 2014. — Т. 18, Л'° 1. О. 253—257.

50. Часовских, А. А. Условия полноты линейно-р-автоматных функций / А. А. Часовских // Интеллектуальные системы. Теория и приложения. — 2014. - Т. 18, № 3. - С. 203-252.

51. Часовских, А. А. Проблема полноты для класса линейно-автоматных функций / А. А. Часовских // Дискретная математика. — 2015. — Т. 27, Л" 2. - С. 134-151.

52. Часовских, А. А. Критериальные системы в классах линейно-автоматных функций над конечными полями / А. А. Часовских // Интеллектуальные системы. Теория и приложения. — 2015. — Т. 19, № 3. — С. 195—207.

53. Часовских, А. А. Сравнение операторов замыкания в классе линейно-автоматных функций / А. А. Часовских // Интеллектуальные системы. Теория и приложения. — 2016. — Т. 20, № 3. — С. 120—124.

54. Часовских, А. А. Проблема полноты в классах линейных автоматов / А. А. Часовских // Интеллектуальные системы. Теория и приложения. —

2018. - Т. 22, № 2. - С. 151-154.

55. Часовских, А. А. Максимальные подклассы в классах линейных автоматов над конечными полями / А. А. Часовских // Дискретная математика. —

2019. - Т. 31, № 4. - С. 88-101.

56. Часовских, А. А. О классах передаточных функций линейных автоматов / А. А. Часовских // Интеллектуальные системы. Теория и приложения. — 2019. - Т. 23, № 3. - С. 135-142.

57. Чернова, Ю. Г. О состоянии конденсации автоматной модели легких в чистой среде / Ю. Г. Чернова // Интеллектуальные системы. — 2010. — Т. 14, вып. 1-4. - С. 561-618.

58. Annals of Discrete Math. Algebraic and Structural Automata Theory. Vol. 44 / L. Beyga [et al.]. — North-Holland, 1991. — 402 p.

59. Hochreiter, S. Long Short-Term Memory / S. Hochreiter, J. Schmidhuber // Neural Computation. — 1997. — Vol. 9, no. 8. — P. 1735—1780.

60. Hop field, J. J. Neural networks and physical systems with emergent collective computational abilities /J.J. Hopfield // Proceedings of National Academy of Sciences. — 1982. — Vol. 79, no. 8. — P. 2554 2558.

61. Post, E. L. Introduction to a general theory of elementary propositions / E. L. Post // Amer. J. Math. — 1921. — Vol. 43, no. 3. — P. 163 185.

62. Post, E. L. The two-valued iterative systems of mathematical logic. - Annals of Math. Studies. Vol. 5 / E. L. Post. — Prineceton-London : Prineceton Univ. Press, 1941. — 122 p.