Регулярные выражения без чередования

9

Мне было интересно, какие наборы языков генерируются ограничениями регулярных выражений. Предположим, что все ограничения имеют постоянный символ для каждого элемента и конкатенации. Тогда восемь классов могут быть сформированы наличием или отсутствием дополнения / отрицания, изменения / объединения и звезды Клини. (Да, у «обычных» регулярных выражений нет оператора , но здесь это удобно.)ΣC

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

Но можно ли генерировать какие-либо интересные классы языков без чередования? Без любого из трех операторов все, что может быть сгенерировано, - это одно слово. Оператор дополнения здесь не сильно помогает.

Только со звездой Клини класс несколько интересен ... не ясно, могут ли они быть распознаны быстрее обычных языков. (Что-нибудь нетривиальное известно об этом?)

И со звездой Клини, и с дополнением ... у вас есть что-нибудь интересное? У этого класса есть имя?

Этот вопрос был вдохновлен вопросом регулярного выражения на math.se.

Чарльз
источник
что означает чередование? Кроме того, это "Kleene".
Суреш Венкат
1
@ Суреш Венкат: Союз, логическое ИЛИ, |, /, ∪.
Чарльз
Обратите внимание, что в исходном контексте класс не имеет дополнения, но имеет обратные ссылки.
Питер Тейлор
@ Питер Тейлор: правильно. Я намерен задать дополнительный вопрос о обратных ссылках, но я подумал, что это будет слишком много, чтобы вписаться в этот вопрос.
Чарльз

Ответы:

12

Класс регулярных языков , которые могут быть описаны регулярными выражениями без союза (и без комплементарности) известен как союз свободного регулярная (также: звезда-точка регулярна ) языков. Этот класс языков, по-видимому, недавно привлек к себе внимание:

Бенедек Надь: «Свободные от объединения регулярные языки и 1-циклические автоматы без путей», Publicationes Mathematicae 68 (1-2), 2006.

Сергей Афонин и Денис Голомазов: «Минимальные несвязные разложения регулярных языков», Теория языка и автоматов и приложения, Springer 2009.

Галина Йираскова и Томас Масопуст: «Сложность в регулярных языках, не состоящих в союзе», Развитие теории языка, Springer 2010.

Герман Грубер
источник
1
Ницца. Что-нибудь известно о дополнительной мощности от дополнения?
Чарльз
1
Короткая мелкая поправка: статья Афонина и Голомазова появилась на LATA 2009, а не на DLT 2009.
Доминик Д. Фрейденбергер,