Сложность графоходных автоматов тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Мартынова Ольга Максимовна

• Мартынова Ольга Максимовна
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Мартынова Ольга Максимовна

Оглавление

Глава 1 Введение

1.1 Положения, выносимые на защиту

1.2 Основные научные результаты

Глава 2 Сложность по числу состояний преобразования графоходных

автоматов к возвращающимся, останавливающимся и обратимым

2.1 Графоходные автоматы и их подклассы

2.2 Улучшение верхних оценок

2.3 Построение «диода»

2.4 Нижняя оценка размера возвращающихся автоматов

2.5 Нижняя оценка размера останавливающихся автоматов

2.6 Нижняя оценка размера возвращающихся и останавливающихся автоматов

2.7 Нижняя оценка размера обратимых автоматов

Глава 3 Вычислительная сложность задачи пустоты для графоходных

и звёздных автоматов

3.1 Задача непустоты для сигнатур решается в КР

3.2 Звёздные автоматы

3.3 Сведение звёздного автомата к сигнатуре

3.4 Сведение графоходного автомата к сигнатуре

3.5 Вычислительная сложность задач пустоты

Глава 4 Заключение

Литература

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

Глава 1 Введение

Моя научная деятельность началась с исследования (детерминированных) графоход-ных автоматов. Что же это за автоматы? Почему меня заинтересовала эта модель?

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

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

В диссертации я рассказываю о моих исследованиях за время обучения в СПбГУ на факультете математики и компьютерных наук. Изучать графоходные автоматы я начала на втором курсе бакалавриата, и к 4-му курсу написала первую статью [19, 26]. Придуманный в ней метод диодов оказался очень удобным, и помог мне доказать ещё несколько нижних оценок для графоходных автоматов [20, 21, 23]. В дальнейшем, я решила ещё две открытые задачи про графоходные автоматы, уже другими методами [17, 22]. В процессе исследования графоходных автоматов я заинтересовалась более базовыми частными случаями автоматов, ходящих по деревьям и строкам [25], а также получила результаты про линейные грамматики [24] и магазинные автоматы, управляемые входом, также известные как автоматы с видимым магазином [18]. Список моделей вычислений, которые я исследую, постоянно пополняется. Однако, несколько последних статей ещё не опубликованы, а некоторые статьи опубликованы пока только в сборниках докладов конференций, поэтому я решила составить мою диссертацию из двух статей про графоходные автоматы,

которые я считаю наиболее важными. В первой статье [26] доказываются асимптотически точные нижние оценки сложности по числу состояний для преобразований графоходных автоматов к останавливающимся, возвращающимся и обратимым подклассам, эти результаты рассказаны в главе 2. Глава 3 описывает результаты другой моей статьи [17], в которой определяются точные классы сложности задачи пустоты для графоходных автоматов и для звёздных автоматов, обобщающих древесные автоматы на графы.

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

Впервые графоходные автоматы были придуманы Майклом Рабином, который выдвинул гипотезу, что для каждого графоходного автомата есть граф, который этот автомат не сможет обойти, — и более того, даже если автомат может использовать конечное число камешков, которые можно класть и поднимать, всё равно он не обойдёт какой-то граф. Вначале Будах [3] показал, что гипотеза верна для автоматов без камешков. Френьё и др. [5] придумали более простое доказательство этого факта. Позже Роллик [28] доказал, что не только автоматы с камешками, а даже несколько автоматов, обменивающихся информацией, не смогут обойти любой граф. Диссер и др. [4] показали, что любой граф с п вершинами можно обойти, используя log log п памяти и log log п камешков, а также, что такое количество ресурсов бывает необходимо. Я и Охотин [22] показали, что если камешки можно только класть, но нельзя поднимать, то графоходные автоматы с такими камешками будут не сильнее обычных и не смогут задать новые графовые языки.

Исследовались преобразования графоходных автоматов (без камешков) к графо-ходным автоматам с хорошими свойствами: возвращающимся в начальную вершину перед принятием, всегда останавливающимся, и обратимым, вычисление которых можно запустить в обратном направлении. Физический смысл обратимых вычислений в том, что по принципу Ландауэра [16] необратимая операция приводит к выделению тепла и потере энергии, поэтому обратимые модели вычислений могут оказаться эффективнее, чем обычные необратимые вычисления. Оказалось, что любой графо-ходный автомат можно преобразовать к возвращающемуся, останавливающемуся и обратимому, чтобы новый автомат принимал то же множество графов. Кунц и Охотин [15] показали, что любой графоходный автомат с п состояниями, работающий на графах с к направлениями (метками концов рёбер), можно преобразовать к возвращающемуся автомату с 3кп состояниями, а также к обратимому, возвращающемуся и останавливающемуся с 6кп + 1 состояниями. Преобразование использует общую идею обхода дерева вычислений, придуманную Сипсером [29].

Позже я и Охотин [19, 26] улучшили преобразование, показав, что для любого гра-фоходного автомата с п состояниями, работающего на графах с к направлениями, существует возвращающийся автомат с 2кп + п состояниями, существует обратимый

и останавливающийся автомат с 2кп + 1 состояниями, и обратимый, возвращающийся и останавливающийся с 4кп + 1 состояниями, принимающие те же графы. Кроме того, в этих же статьях были впервые доказаны нижние оценки к этим преобразованиям. Оказалось, что для преобразования к возвращающемуся автомату бывает необходимо 2(к — 3)п состояний, для преобразования к останавливающемуся в худшем случае требуется не меньше 2(к — 3)(п — 1) состояний, для преобразования к возвращающемуся и останавливающемуся — не менее 2(к — 3)(2п — 1) состояний. Для преобразования просто к обратимому бывает необходимо 2(к — 3)(п — 1) — 1 состояний, а к обратимому и возвращающемуся 2(к — 3)(2п — 1) — 1 состояний. Все оценки асимптотически точные.

Методы, придуманные в статьях [19, 26], оказались полезными и для решения других задач, связанных с графоходными автоматами. Одна из базовых задач для любой модели вычислений — относительно каких операций она замкнута? Я и Охо-тин [20] показали, что объединение и пересечение языков, задаваемых графоходными автоматами, тоже принимаются какими-то графоходными автоматами, а также, что графоходные автоматы замкнуты относительно дополнения. Были построены гра-фоходные автоматы для объединения, пересечения и дополнения, а также получены асимптотически точные нижние оценки к этим построениям: для двух автоматов с т и п состояниями, где т ^ п, работающих на графах с к направлениями, чтобы распознать объединение языков, в худшем случае требуется не менее 2(к — 3)(т—1)+п—1 и не более 2кт +1 + п состояний. Для пересечения нижняя оценка 2{к — 3)(т — 1) + п — 1 состояний и верхняя 2кт + т + п. Для дополнения автомата с п состояниями необходимо в худшем случае 2(к — 3)(п — 1) состояний, и достаточно 2кп + 1.

Другая операция над языками, задаваемыми автоматами, — это гомоморфизмы графов. Гомоморфизм заменяет вершины с одной и той же меткой на один и тот же подграф. Можно ли распознать графоходным автоматом гомоморфный образ языка, принимаемого автоматом? А есть ли замкнутость относительно обратных гомоморфизмов? Я и Охотин [21, 23] доказали, что графоходные автоматы замкнуты относительно обратных гомоморфизмов: если язык с к направлениями распознаётся графоходным автоматом с п состояниями, то множество его прообразов К-1(Ь) = {| Н('ш) Е Ь } можно распознать автоматом с кп + 1 состояниями. Также получена нижняя оценка кп состояний. А относительно прямых гомоморфизмов графоходные автоматы оказываются незамкнуты, более того, уже автоматы на деревьях незамкнуты относительно инъективных гомоморфизмов.

Для многих моделей вычислений рассматривается задача пустоты: по данному на вход автомату определить, пуст ли задаваемый им язык. Класс сложности, в котором оказывается эта задача, говорит что-то о выразительности модели вычисления. Известны результаты о разрешимости и вычислительной сложности задачи пустоты для более простых видов конечных автоматов, обходящих данный на входе объект: для двухсторонних конечных автоматов (2ВЕЛ) задача пустоты ВВЕДОВ-полна (что следует из результата Козена [13, лемма 3.2.3]), а для детерминированных древо-ходных автоматов, как показал Боянчик [1], аналогичная задача ЕХР-полна. Также Кари и Мур [12, теорема 4.1] доказали, что задача пустоты для двумерных ВЕА и КЕА (автоматов на картинках) неразрешима. Я исследовала сложность задачи непустоты для графоходных автоматов, обобщающих 2ВЕА и древоходные автоматы, и показала, что эта задача КЕХР-полна [17].

Другая разновидность конечных автоматов — это недетерминированные автома-

ты, которые распознают объект, замощая его окрестностями состояний. Таковы односторонние недетерминированные конечные автоматы (NFA), для которых задача непустоты NL-полна (это одна из классических задач, рассмотренных Джонсом [11]). Для деревьев это недетерминированные древесные автоматы, задача пустоты для которых P-полна, как показано Винсом [31]. Для распознаваемых языков картинок, заданных замощениями на картинках, Джиаммарреси и Рестиво [7] доказали, что задачи пустоты и универсальности неразрешимы.

Рассматривались замощающие модели и для графов: Томас [30] ввёл так называемые (graph) acceptors. В модели Томаса граф лежит в языке, если его можно покрыть плитками-подграфами из специального конечного множества, чтобы каждая вершина лежала во внутренней части какой-то плитки, чтобы состояния на вершинах плиток были согласованы и чтобы ещё выполнялись дополнительные условия на количества плиток разных типов. Для этой общей модели Томас показал неразрешимость задачи пустоты (эта модель позволяет распознавать графы-решётки и моделировать машину Тьюринга). У Томаса также были «elementary acceptors» — частный случай, в котором каждая плитка имеет вид звезды, то есть это вершина с её соседями. Для них Томас показал, что язык графов-решёток ими распознать нельзя, но не показал, разрешима ли пустота для «elementary acceptors».

В данной диссертации, кроме задачи пустоты для графоходных автоматов, также рассматривается задача пустоты для звёздных автоматов — это «elementary acceptors» Томаса, но без дополнительных условий на количества плиток. Звёздные автоматы — это одновременно частный случай модели Томаса и обобщение недетерминированных древесных автоматов. Я доказала, что задача непустоты для звёздных автоматов разрешима и NP-полна [17].

1.1 Положения, выносимые на защиту

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

2. NEXP-полнота задачи непустоты для графоходных автоматов, NP-полнота задачи непустоты для звёздных автоматов, обобщающих древесные автоматы на графы.

1.2 Основные научные результаты

1. Асимптотически точные нижние и верхние оценки числа состояний, нужного для преобразования графоходных автоматов к возвращающимся, останавливающимся и обратимым графоходным автоматам [19, 26] (личный вклад составляет не менее 50%)

2. Доказательство, что задача непустоты для графоходных автоматов NEXP-полна, а задача непустоты для звёздных автоматов (обобщения древесных автоматов на графы) NP-полна [17].

Заключение диссертации по теме «Другие cпециальности», Мартынова Ольга Максимовна

Глава 4 Заключение

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

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

преобразование к нижняя оценка верхняя оценка

возвращающемуся останавливающемуся возвращающемуся и останавливающемуся обратимому обратимому и возвращающемуся 2( к — 3)п 2( к — 3)(п — 1) 2( к — 3)(2 п — 1) 2( к — 3)(п — 1) — 1 2( к — 3)(2п — 1) — 1 2 к п + п 2 к п + 1 4 к п + 1 2 к п + 1 4 к п + 1

Таблица 4.1: Нижние и верхние оценки для разных преобразований графоходных автоматов.

Однако, в важных частных случаях детерминированных древоходных автоматов и конечных двусторонних автоматов (2DFA) многое неизвестно.

Для 2DFA с п состояниями верхняя оценка для преобразования к останавливающимся 2DFA равна 4 п + const состояний, её доказали Гефферт и др. [6]. Неизвестно никаких нижних оценок. Для преобразования к обратимому 2DFA верхняя оценка 4 п+3 состояний доказана Кунцем и Охотиным [15], они же доказали нижнюю оценку 2 п — 2 [14]. Улучшить нижние оценки для преобразований 2DFA к останавливающимся и обратимым — интересная открытая задача.

Детерминированные древоходные автоматы тоже можно преобразовать к останавливающимся, что доказали Мушолл и др. [27], и известно, что для деревьев с к потомками в вершине достаточно использовать 4 кп + 2 к + 1 состояний для преобразования к обратимому автомату, как показали Кунц и Охотин [15]. Доказательство нижних оценок для преобразований древоходных автоматов остаётся для дальнейших исследований.

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

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

строки деревья графы картинки

ходящие (2DFA) PSPACE-полны [13] (DTWA) EXP-полны [1] (GWA) NEXP-полны (сл. 3, теор. 16) (4DFA) неразрешимы [12]

замощающие рёбрами/ звёздами (NFA) NL-полны [11] (древесные авт.) P-полны [31] (звёздные авт.) NP-полны (сл. 1, теор. 15) неразрешимы [7]

Таблица 4.2: Сложность задачи непустоты для разных семейств автоматов.

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

Звёздные автоматы в диссертации — это частный случай «elementary acceptors» Томаса [30], без ограничений на число вхождений каждой звезды. Окажется ли задача пустоты для «elementary acceptors» Томаса тоже разрешимой? Это остаётся открытой задачей.

Список литературы диссертационного исследования кандидат наук Мартынова Ольга Максимовна, 2025 год

Литература

[1] M. Bojanczyk, "Tree-walking automata", LATA 2008, LNCS 5196, 1-2. Extended version available at https://www.mimuw.edu.pl/~bojan/upload/ conflataBojanczyk08.pdf.

[2] M. Bojanczyk, T. Colcombet, "Tree-walking automata cannot be determinized", Theoretical Computer Science, 350:2-3 (2006), 164-173.

[3] L. Budach, "Automata and labyrinths", Mathematische Nachrichten, 86:1 (1978), 195-282.

[4] Y. Disser, J. Hackfeld, M. Klimm, "Tight bounds for undirected graph exploration with pebbles and multiple agents", Journal of the ACM, 66:6 (2019), 40:1-40:41.

[5] P. Fraigniaud, D. Ilcinkas, G. Peer, A. Pelc, D. Peleg, "Graph exploration by a finite automaton", Theoretical Computer Science, 345:2-3 (2005), 331-344.

[6] V. Geffert, C. Mereghetti, G. Pighizzini, "Complementing two-way finite automata", Information and Computation, 205:8 (2007), 1173-1187.

[7] D. Giammarresi, A. Restivo, "Recognizable picture languages", International Journal of Pattern Recognition and Artificial Intelligence, 6:2-3 (1992), 241-256.

[8] J. Hadamard, "Resolution d'une question relative aux determinants", Bulletin des Sciences Mathématiques, 17 (1893), 240-246.

[9] K. Inoue, A. Nakamura, "Some properties of two-dimensional on-line tessellation acceptors", Information Sciences, 13:2 (1977), 95-121.

[10] K. Inoue, I. Takanami, "A characterization of recognizable picture languages", International Journal of Pattern Recognition and Artificial Intelligence, 8:2 (1994), 501-508.

[11] N. D. Jones, "Space bounded reducibility among combinatorial problems", Journal of Computer and System Sciences, 11:1 (1975), 68-85.

[12] J. Kari, C. Moore, "Rectangles and Squares Recognized by Two-Dimensional Automata", Theory Is Forever 2004, LNCS 3113, 134-144.

[13] D. Kozen, "Lower bounds for natural proof systems", FOCS 1977, 254-266.

[14] M. Kunc, A. Okhotin, "Reversible two-way finite automata over a unary alphabet", TUCS Technical Report 1024, Turku Centre for Computer Science, December 2011.

[15] M. Kunc, A. Okhotin, "Reversibility of computations in graph-walking automata", Information and Computation, 275 (2020), article 104631.

[16] R. Landauer, "Irreversibility and heat generation in the computing process", IBM Journal of Research and Development, 5:3 (1961), 183-191.

[17] O. Martynova, "Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs", Information and Computation, 296 (2024), article 105127.

[18] O. Martynova, "Exact descriptional complexity of determinization of input-driven pushdown automata", Implementation and Application of Automata (CIAA 2024, Akita, Japan, 3-6 September 2024), LNCS 15015, 249-260.

[19] O. Martynova, A. Okhotin, "Lower bounds for graph-walking automata", 38th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2021, Saarbrucken, Germany, 16-19 March 2021), LIPIcs 187, 52:1-52:13.

[20] O. Martynova, A. Okhotin, "State complexity of union and intersection on graphwalking automata", Descriptional Complexity of Formal Systems 2021, LNCS 13037, 125-136.

[21] O. Martynova, A. Okhotin, "Homomorphisms on Graph-Walking Automata", 26th International Conference on Implementation and Application of Automata (CIAA 2022, Rouen, France, June 28-July 1, 2022), LNCS 13266, 177-188.

[22] O. Martynova, A. Okhotin, "A time to cast away stones", Implementation and Application of Automata: 27th International Conference (CIAA 2023, Famagusta, 19-22 September 2023), LNCS 14151, 242-253.

[23] O. Martynova, A. Okhotin, "Homomorphisms and inverse homomorphisms on graphwalking automata", Theoretical Computer Science, 979 (2023), article 114197.

[24] O. Martynova, A. Okhotin, "Non-closure under complementation for unambiguous linear grammars", Information and Computation, 292 (2023), article 105031.

[25] O. Martynova, A. Okhotin, "Shortest accepted strings for two-way finite automata: approaching the 2n lower bound", Descriptional Complexity of Formal Systems (DCFS 2023, Potsdam, Germany, 4-6 July 2023), LNCS 13918, 134-145.

[26] O. Martynova, A. Okhotin, "State complexity of transforming graph-walking automata to halting, returning and reversible", Information and Computation, 291 (2023), article 105011.

[27] A. Muscholl, M. Samuelides, L. Segoufin, "Complementing deterministic tree-walking automata", Information Processing Letters, 99:1 (2006), 33-39.

[28] H. A. Rollik, "Automaten in planaren Graphen", Acta Informatica, 13:3 (1980), 287298.

[29] M. Sipser, "Halting space-bounded computations", Theoretical Computer Science, 10:3 (1980), 335-338.

[30] W. Thomas, "On logics, tilings, and automata", Automata, Languages and Programming (ICALP 1991, Madrid, Spain, 8-12 July 1991), LNCS 510, 441-454.

[31] M. Veanes, "On computational complexity of basic decision problems of finite tree automata", Technical Report 133, Uppsala University, Computing Science Department, 1997.