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