Проблема высоты звезды - Википедия - Star height problem

Эта статья включает встроенные цитаты, но они не правильно отформатирован. Пожалуйста улучшать эта статья исправляя их. Ссылка в скобках была устарел; преобразовать в сокращенные сноски. (Сентябрь 2020) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

На первый вопрос был дан отрицательный ответ, когда в 1963 году Эгган привел примеры обычных языков высота звезды п для каждого п. Здесь высота звезды час(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}}}$

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

Однако в примерах Эггана используется большой алфавит, размер 2^п-1 для языка с высотой звезды п. Поэтому он спросил, можем ли мы также найти примеры для двоичных алфавитов. Это подтвердилось вскоре после этого. Дежан и Шютценбергер (1966). Их примеры можно описать индуктивно определенный семейство регулярных выражений над двоичным алфавитом ${ Displaystyle {а, Ь }}$ следующим образом - ср. Саломаа (1981):

${ 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}}}$

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

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

Напротив, второй вопрос оказался намного сложнее, и этот вопрос стал известной открытой проблемой в теории формального языка более двух десятилетий (Бжозовский 1980 ). В течение многих лет прогресс был незначительным. В чистогрупповые языки были первым интересным семейством регулярных языков, для которого проблема высоты звезды оказалась решаемой. разрешимый (Макнотон 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

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

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

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

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

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

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

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

• Бжозовский, Януш А. (1980). «Открытые проблемы об обычных языках». В книге Рональд В. (ред.). Теория формального языка - перспективы и открытые проблемы. Нью-Йорк: Academic Press. стр.23–47. ISBN  978-0-12-115350-2.CS1 maint: ref = harv (связь) (версия технического отчета)
• Колкомбет, Томас; Лёдинг, Кристоф (2008). "Глубина вложенности дизъюнктивного μ-исчисления для языков деревьев и проблема ограниченности". CSL. Конспект лекций по информатике. 5213: 416–430. Дои:10.1007/978-3-540-87531-4_30. ISBN  978-3-540-87530-7. ISSN  0302-9743.CS1 maint: ref = harv (связь)
• Дежан, Франсуаза; Шютценбергер, Марсель-Поль (1966). «К вопросу об Эггане». Информация и контроль. 9 (1): 23–25. Дои:10.1016 / S0019-9958 (66) 90083-0.CS1 maint: ref = harv (связь)
• Эгган, Лоуренс К. (1963). «Графики переходов и звездность регулярных событий». Мичиганский математический журнал. 10 (4): 385–397. Дои:10,1307 / ммдж / 1028998975. Zbl  0173.01504.CS1 maint: ref = harv (связь)
• Макнотон, Роберт (1967). "Сложность цикла чисто-групповых событий". Информация и контроль. 11 (1–2): 167–176. Дои:10.1016 / S0019-9958 (67) 90481-0.CS1 maint: ref = harv (связь)
• Саломаа, Арто (1981). Драгоценности теории формального языка. Мельбурн: издательство Pitman Publishing. ISBN  978-0-273-08522-5. Zbl  0487.68063.CS1 maint: ref = harv (связь)

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

• Хасигучи, Косабуро (1982). «Обычные языки первой звезды». Информация и контроль. 53 (2): 199–210. Дои:10.1016 / S0019-9958 (82) 91028-2.CS1 maint: ref = harv (связь)
• Хасигути, Косабуро (1988). «Алгоритмы определения относительной высоты звезды и высоты звезды». Информация и вычисления. 78 (2): 124–169. Дои:10.1016/0890-5401(88)90033-8.CS1 maint: ref = harv (связь)
• Ломбардия, Сильвен; Сакарович, Жак (2002). «Звездная высота обратимых языков и универсальных автоматов» (PDF). 5-й латиноамериканский симпозиум по теоретической информатике (LATIN) 2002, Vol. 2286 из LNCS. Springer.CS1 maint: ref = harv (связь)
• Кирстен, Дэниел (2005). «Дистанционные пустынные автоматы и проблема высоты звезды». RAIRO - Теория информатики и приложения. 39 (3): 455–509. Дои:10.1051 / ita: 2005027.CS1 maint: ref = harv (связь)
• Сакарович, Жак (2009). Элементы теории автоматов. Перевод с французского Рувима Томаса. Кембридж: Издательство Кембриджского университета. ISBN  978-0-521-84425-3. Zbl  1188.68177.CS1 maint: ref = harv (связь)