Обобщенная проблема высоты звезды

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

В частности, открытым остается вопрос, требуется ли глубина вложенности более 1, и если да, то существует ли алгоритм для определения минимально необходимой высоты звезды. ^[1]

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

• Теорема Эггана и разделы «Обобщенная высота звезды» статьи « Высота звезды»
• Проблема высоты звезды

• Януш А. Бжозовски (1980). «Открытые проблемы о регулярных языках». В книге Рональда В. (ред.). Формальная теория языка: перспективы и открытые проблемы . Academic Press. стр.  23–47 .
• Вольфганг Томас (1981). «Замечание о проблеме высоты звезды». Теоретическая информатика . 13 (2): 231– 237. doi : 10.1016/0304-3975(81)90041-4 . MR  0594062.
• Жан-Эрик Пэн; Говард Штраубинг; Дени Териен (1992). "Некоторые результаты по обобщенной проблеме высоты звезды" (PDF) . Информация и вычисления . 101 (2): 219– 250. doi :10.1016/0890-5401(92)90063-L.
• Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рубена Томаса. Кембридж: Cambridge University Press . ISBN 978-0-521-84425-3. Збл  1188.68177.
• Марсель-Пауль Шютценбергер (1965). «О конечных моноидах, имеющих только тривиальные подгруппы». Информация и управление . 8 (2): 190– 194. doi : 10.1016/S0019-9958(65)90108-7 . Zbl  0131.02001.

• Жан-Эрик Пин: Проблема высоты звезды