Проблема высоты звезды

Проблема в формальной теории языка

Проблема высоты звезды в формальной теории языка — это вопрос о том, могут ли все регулярные языки быть выражены с помощью регулярных выражений ограниченной высоты звезды , т. е. с ограниченной глубиной вложенности звезд Клини . В частности, всегда ли достаточно глубины вложенности в единицу? Если нет, то существует ли алгоритм для определения требуемого количества? Впервые эта проблема была представлена ​​Эгганом в 1963 году. ^[1]

Семейства регулярных языков с неограниченной высотой звезды

На первый вопрос был дан отрицательный ответ, когда в 1963 году Эгган привел примеры регулярных языков с высотой звезды n для каждого n . Здесь высота звезды h ( L ) регулярного языка L определяется как минимальная высота звезды среди всех регулярных выражений, представляющих L . Первые несколько языков, найденных Эгганом, описаны ниже с помощью указания регулярного выражения для каждого языка:

${\displaystyle {\begin{alignedat}{2}e_{1}&=a_{1}^{*}\\e_{2}&=\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\\e_{3}&=\left(\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\left(a_{4}^{*}a_{5}^{*}a_{6}\right)^{*}a_{7}\right)^{*}\\e_{4}&=\left(\left(\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\left(a_{4}^{*}a_{5}^{*}a_{6}\right)^{*}a_{7}\right)^{*}\left(\left(a_{8}^{*}a_{9}^{*}a_{10}\right)^{*}\left(a_{11}^{*}a_{12}^{*}a_{13}\right)^{*}a_{14}\right)^{*}a_{15}\right)^{*}\end{alignedat}}}$

Принцип построения этих выражений заключается в том, что выражение получается путем конкатенации двух копий , соответствующего переименования букв второй копии с использованием новых символов алфавита, конкатенации результата с другим новым символом алфавита, а затем окружения полученного выражения звездой Клини. Оставшаяся, более сложная часть, заключается в доказательстве того, что для не существует эквивалентного регулярного выражения с высотой звезды меньше n ; доказательство приведено в работе Eggan (1963). ${\displaystyle e_{n+1}}$ ${\displaystyle e_{n}}$ ${\displaystyle e_{n}}$

Однако примеры Эггана используют большой алфавит , размером 2 ⁿ -1 для языка со звездной высотой n . Таким образом, он спросил, можем ли мы также найти примеры для двоичных алфавитов. Это было доказано вскоре после этого Дежаном и Шютценбергером в 1966 году. ^[2] Их примеры можно описать индуктивно определенным семейством регулярных выражений для двоичного алфавита следующим образом – см. Salomaa (1981): ${\displaystyle \{a,b\}}$

${\displaystyle {\begin{alignedat}{2}e_{1}&=(ab)^{*}\\e_{2}&=\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}\\e_{3}&=\left(aaaa\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}bbbb\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}\right)^{*}\\\,&\cdots \\e_{n+1}&=(\,\underbrace {a\cdots a} _{2^{n}}\,\cdot \,e_{n}\,\cdot \,\underbrace {b\cdots b} _{2^{n}}\,\cdot \,e_{n}\,)^{*}\end{alignedat}}}$

Опять же, необходимо строгое доказательство для факта, что не допускает эквивалентного регулярного выражения меньшей высоты звезды. Доказательства даны Дежаном и Шютценбергером (1966) и Саломаа (1981). ${\displaystyle e_{n}}$

Вычисление высоты звезды регулярных языков

Напротив, второй вопрос оказался намного сложнее, и этот вопрос стал известной открытой проблемой в формальной теории языков на протяжении более двух десятилетий. ^[3] В течение многих лет прогресс был незначительным. Чисто-групповые языки были первым интересным семейством регулярных языков, для которых было доказано, что проблема высоты звезды разрешима . ^[4] Но общая проблема оставалась открытой более 25 лет, пока ее не решил Хашигучи , который в 1988 году опубликовал алгоритм для определения высоты звезды любого регулярного языка. ^[5] Алгоритм был совершенно непрактичным, поскольку имел неэлементарную сложность . Чтобы проиллюстрировать огромные ресурсные затраты этого алгоритма, Ломбарди и Сакарович (2002) приводят некоторые фактические цифры:

[Процедура, описанная Хашигучи] приводит к вычислениям, которые на сегодняшний день невозможны, даже для очень маленьких примеров. Например, если L принимается автоматом с 4 состояниями и сложностью цикла 3 (и с небольшим моноидом переходов из 10 элементов), то очень низкая миноранта числа языков, которые нужно проверить с помощью L на равенство, равна: ${\displaystyle \left(10^{10^{10}}\right)^{\left(10^{10^{10}}\right)^{\left(10^{10^{10}}\right)}}.}$

—  С. Ломбарди и Дж. Сакарович, Звездная высота обратимых языков и универсальных автоматов , LATIN 2002

Обратите внимание, что само по себе это число имеет 10 миллиардов нулей, если его записать в десятичной системе счисления , и это уже намного больше, чем число атомов в наблюдаемой Вселенной . ${\displaystyle 10^{10^{10}}}$

Гораздо более эффективный алгоритм, чем процедура Хашигучи, был разработан Кирстен в 2005 году. ^[6] Этот алгоритм работает для заданного недетерминированного конечного автомата в качестве входных данных в пределах дважды экспоненциального пространства . Тем не менее, требования к ресурсам этого алгоритма все еще значительно превышают пределы того, что считается практически осуществимым.

Этот алгоритм был оптимизирован и обобщен на деревья Колкомбетом и Лёдингом в 2008 году ^[7] как часть теории регулярных функций стоимости. Он был реализован в 2017 году в наборе инструментов Stamina. ^[8]

Смотрите также

• Обобщенная проблема высоты звезды
• Алгоритм Клини — вычисляет регулярное выражение (обычно не минимальной высоты звезды) для языка, заданного детерминированным конечным автоматом.

Примечания

1. Эгган 1963.
2. Дежан и Шютценбергер 1966.
3. Бжозовский 1980.
4. Макнотон 1967.
5. Хашигучи 1988.
6. Кирстен 2005.
7. Колкомбет и Лёдинг 2008.
8. Фиялков и др. 2017.

Ссылки

• Brzozowski, Janusz A. (1980). "Открытые проблемы о регулярных языках". В книге, Ronald V. (ред.). Formal language theory—Perspectives and open problems . New York: Academic Press. стр. 23–47. ISBN 978-0-12-115350-2.(версия технического отчета)
• Колкомбет, Томас; Лёдинг, Кристоф (2008). «Глубина вложенности дизъюнктивного μ-исчисления для древовидных языков и проблема ограниченности». Computer Science Logic . Lecture Notes in Computer Science. Vol. 5213. pp. 416–430. doi :10.1007/978-3-540-87531-4_30. ISBN 978-3-540-87530-7. ISSN  0302-9743.
• Дежан, Франсуаза; Шютценбергер, Марсель-Поль (1966). «К вопросу об Эггане». Информация и контроль . 9 (1): 23–25. дои : 10.1016/S0019-9958(66)90083-0.
• Эгган, Лоуренс К. (1963). «Графы переходов и звездная высота регулярных событий». Michigan Mathematical Journal . 10 (4): 385–397. doi : 10.1307/mmj/1028998975 . Zbl  0173.01504.
• Макнотон, Роберт (1967). «Петлевая сложность чисто групповых событий». Информация и управление . 11 (1–2): 167–176. doi :10.1016/S0019-9958(67)90481-0.
• Саломаа, Арто (1981). Жемчужины теории формального языка . Мельбурн: Издательство Pitman Publishing. ISBN 978-0-273-08522-5. Збл  0487.68063.

Дальнейшее чтение

• Хашигучи, Косабуро (1982). «Регулярные языки звездной высоты один». Информация и управление . 53 (2): 199–210. doi :10.1016/S0019-9958(82)91028-2.
• Хашигучи, Косабуро (1988). «Алгоритмы определения относительной высоты звезды и высоты звезды». Информация и вычисления . 78 (2): 124–169. doi : 10.1016/0890-5401(88)90033-8 .
• Ломбарди, Сильвен; Сакарович, Жак (2002). «Звездная высота обратимых языков и универсальных автоматов». LATIN 2002: Теоретическая информатика (PDF) . Конспект лекций по информатике. Том 2286. Springer. С. 76–90. doi :10.1007/3-540-45995-2_12. ISBN 978-3-540-43400-9.
• Кирстен, Дэниел (2005). «Дальние автоматы пустыни и проблема высоты звезды». RAIRO - Теоретическая информатика и приложения . 39 (3): 455–509. дои : 10.1051/ita: 2005027.
• Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рубена Томаса. Кембридж: Cambridge University Press . ISBN 978-0-521-84425-3. Збл  1188.68177.
• Фиялков, Натанаэль; Гимберт, Хьюго; Кельменди, Эдон; Куперберг, Денис (2017). Карайоль, Арно; Нико, Сирил (ред.). Выносливость: моноиды стабилизации в теории автоматов. ЦИАА. Чам: Международное издательство Springer. стр. 101–112. дои : 10.1007/978-3-319-60134-2_9. ISBN 978-3-319-60134-2.