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