Проблема высоты звезды - Star height problem

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

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

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

${\ displaystyle {\ begin {alignat} {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 {alignat}}}$

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

Однако в примерах Эггана используется большой алфавит размером 2 ⁿ -1 для языка с высотой звезды n . Поэтому он спросил, можем ли мы также найти примеры для двоичных алфавитов. Это подтвердилось вскоре после этого Dejean & Schützenberger (1966) . Их примеры можно описать индуктивно определенным семейством регулярных выражений над двоичным алфавитом следующим образом: ср. Саломаа (1981) : ${\ Displaystyle \ {а, б \}}$

${\ displaystyle {\ begin {alignat} {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 {alignat}}}$

Опять же, требуется строгое доказательство того факта, что оно не допускает эквивалентного регулярного выражения для более низкой высоты звезды. Доказательства даны ( Dejean & Schützenberger 1966 ) и ( Salomaa 1981 ). ${\ displaystyle e_ {n}}$

Вычисление звездной высоты обычных языков

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

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

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

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

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

Этот алгоритм был оптимизирован и обобщен на деревья Колкомбетом и Лёдингом в 2008 г. ( Colcombet & Löding 2008 ) как часть теории регулярных функций стоимости. Он был реализован в 2017 году в наборе инструментов Stamina.

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

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

Рекомендации

Процитированные работы

• Бжозовский, Януш А. (1980). «Открытые задачи о регулярных языках» . В книге Рональд В. (ред.). Теория формального языка - перспективы и открытые проблемы . Нью-Йорк: Academic Press. С.  23–47 . ISBN 978-0-12-115350-2. (версия технического отчета)
• Колкомбет, Томас; Лёдинг, Кристоф (2008). "Глубина вложенности дизъюнктивного μ-исчисления для языков деревьев и проблема ограниченности". CSL . Конспект лекций по информатике. 5213 : 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. DOI : 10.1016 / S0019-9958 (66) 90083-0 .
• Эгган, Лоуренс К. (1963). «Графики переходов и звездность регулярных событий» . Мичиганский математический журнал . 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. Zbl  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). "Высота звезды обратимых языков и универсальных автоматов" (PDF) . 5-й латиноамериканский симпозиум по теоретической информатике (LATIN) 2002, Vol. 2286 из LNCS . Springer.
• Кирстен, Дэниел (2005). «Дистанционные пустынные автоматы и проблема высоты звезды». RAIRO - Теория информатики и приложения . 39 (3): 455–509. DOI : 10.1051 / ITA: 2005027 .
• Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рувима Томаса. Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-84425-3. Zbl  1188.68177 .