Особый класс языков: «круговые» языки. Это известно?

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

Язык L является круговым, если для всех слов $w$ в $\Sigma^*$ имеем:

$w$ принадлежит L тогда и только тогдакогда для всех целых$k > 0$ ,$w^k$ которой принадлежит L.

Известен ли этот класс языков? Мне интересны циркулярные языки, которые также являются регулярными и, в частности:

• имя для них, если они уже известны

• разрешимость проблемы с учетом автомата (в частности: DFA), подчиняется ли принятый язык приведенному выше определению

В первой части мы показываем экспоненциальный алгоритм для определения округлости. Во второй части мы покажем, что эта проблема трудоемкая. В третьей части мы покажем, что каждый циркулярный язык является объединением языков вида $r^+$ (здесь r может быть пустым регулярным выражением); союз не обязательно не пересекается. В четвертой части мы показываем круговой язык, который нельзя записать в виде непересекающейся суммы ∑ r + i .$r$$\sum r_i^+$

Изменить: Внесены некоторые исправления после комментариев Марка. В частности, мои более ранние утверждения о том, что цикличность является coNP-полной или NP-сложной, исправлены.

Редактировать: Исправлена ​​нормальная форма из $\sum r_i^*$ до ∑ r + i . Выставлен «по своей сути неоднозначный» язык.$\sum r_i^+$

Продолжая комментарий Питера Тейлора, вот как решить (крайне неэффективно), является ли язык круговым, учитывая его DFA. Построить новый DFA, чьи состояния являются n- корнями старых состояний. Этот новый DFA запускает n копий старого DFA параллельно.$n$$n$

Если язык не циклический, то есть слово w, такое, что если мы несколько раз пропустим его через DFA, начиная с начального состояния s 0 , то получим состояния s 1 , … , s n такие, что s 1 принимает, кроме одного из других не принимает (если все они принимают, то последовательность s 0 , … , s $w$$s_0$$s_1,\ldots,s_n$$s_1$$s_0,\ldots,s_n$ должна циклически изменяться, чтобы w ∗ всегда было в языке). Другими словами, у нас есть путь от s 0 , … , s $w^*$- от 1 до s 1 ,…, s n, где s 1 принимает, но один из других не принимает. И наоборот, если язык круговой, то этого не может быть.$s_0,\ldots,s_{n-1}$$s_1,\ldots,s_n$$s_1$

Таким образом, мы сократили проблему до простого теста направленной достижимости (просто отметьте все возможные «плохие» n- кортежи).$n$

Проблема округлости является трудоемкой. Предположим, нам дан экземпляр 3SAT с n переменными → x и m предложениями C 1 , … , C m . Можно предположить, что n = $n$$\vec{x}$$m$$C_1,\ldots,C_m$$n = m$ (добавить фиктивные переменные) и что n простое (иначе найти простое число между n и 2 n, используя тестирование простоты AKS, и добавить фиктивные переменные и предложения).$n$$n$$2n$

Рассмотрим следующий язык: «вход не имеет форму → x 1 ⋯ → x n, где → x i - удовлетворительное присваивание для C i ». Для этого языка легко построить O ( n 2 ) DFA. Если язык не круговой, то в языке есть слово w , некоторая сила которого не в языке. Поскольку единственные слова, отсутствующие в языке, имеют длину $\vec{x}_1 \cdots \vec{x}_n$$\vec{x}_i$$C_i$$O(n^2)$$w$ 2 , w должно иметь длину 1 или n . Если это длины$n^2$$w$$1$$n$1 , рассмотрим w n (оно все еще на языке), так что w на языке, а w n на языке. Тот факт, что w n отсутствует в языке, означает, что w является удовлетворительным назначением.$1$$w^n$$w$$w^n$$w^n$$w$

И наоборот, любое удовлетворительное присваивание переводится как слово, доказывающее некруглость языка: удовлетворяющее присваивание w принадлежит языку, а w n - нет. Таким образом, язык является круговым, если экземпляр 3SAT неудовлетворителен.$w$$w^n$

В этой части мы обсудим нормальную форму для циркулярных языков. Рассмотрим некоторый DFA для кругового языка L . Последовательность C = C 0 , ... в реальном , если C 0 = s (начальное состояние), все остальные государства принимают и C я = C J означает C $L$$C = C_0,\ldots$$C_0 = s$$C_i = C_j$ + 1 = С J + 1 . Таким образом, каждая действительная последовательность в конечном итоге является периодической, и существует только конечное число действительных последовательностей (поскольку DFA имеет конечное число состояний).$C_{i+1} = C_{j+1}$

Мы говорим, что слово ведет себя согласно $C$ если слово переводит DFA из состояния c i в состояние c i + 1 для всех i . Множество всех таких слов E ( C $c_i$$c_{i+1}$$i$$E(C)$ регулярно (аргумент аналогичен первой части этого ответа). Заметим , что Е ( С ) представляет собой подмножество L .$E(C)$$L$

Для реальной последовательности C определите C k как последовательность C k ( t ) = C ( k t ) . Последовательность C k также действительна. Поскольку существует только конечное число различных последовательностей C k , язык D ( C ), являющийся объединением всех E ( C k ) , также является регулярным.$C$$C^k$$C^k(t) = C(kt)$$C^k$$C^k$$D(C)$$E(C^k)$

Покажем, что D ( C ) обладает тем свойством, что если x , y ∈ D ( C ), то x y ∈ D ( C ) . Действительно, предположим, что x ∈ C k и y ∈ C l . Тогда x y ∈ C k + l . Таким образом, D ( C ) = D ( C ) + можно записать в виде $D(C)$$x,y \in D(C)$$xy \in D(C)$$x \in C^k$$y \in C^l$$xy \in C^{k+l}$$D(C) = D(C)^+$+ для некоторого регулярного выражения r .$r^+$$r$

Каждое слово ш в языке соответствует некоторой реальной последовательности C , то существует реальная последовательность C , что ж ведет себя в соответствии с. Таким образом , L является объединением D ( C ) в течение всего действительной последовательности C . Поэтому каждый циркулярный язык имеет представление вида ∑ r + i . И наоборот, каждый такой язык является круговым (тривиально).$w$$C$$C$$w$$L$$D(C)$$C$$\sum r_i^+$

Рассмотрим круговой язык L всех слов над a , b, которые содержат четное число или a 's или четное число b ' (или оба). Покажем, что она не может быть записана как непересекающаяся сумма ∑ r + i ; под «дизъюнктом» мы подразумеваем, что r + i ∩ $L$$a,b$$a$$b$$\sum r_i^+$ + j =∅.$r_i^+ \cap r_j^+ = \varnothing$

Пусть N i будет размером некоторого DFA для r + i , а N > max N i будет нечетным целым числом. Рассмотрим x = a N b N ! , Поскольку x ∈ L , x ∈ r + i для некоторого i . По насосным леммам, можно накачать префикс х длин не более N . Таким образом, r + i порождает z = a N $N_i$$r_i^+$$N > \max N_i$$x = a^N b^{N!}$$x \in L$$x \in r_i^+$$i$$x$$N$$r_i^+$б N ! , Точно так же y = a N ! b N порождается некоторым r + j , что также порождает z . Обратите вниманиечто я ≠ J , так как х у ∉ L . Таким образом, представление не может быть дизъюнктивным.$z = a^{N!} b^{N!}$$y = a^{N!} b^N$$r_j^+$$z$$i \neq j$$xy \notin L$

Вот некоторые документы, которые обсуждают эти языки:

Тьерри Кашат, Сила однобуквенных рациональных языков, DLT 2001, Springer LNCS # 2295 (2002), 145-154.

S. Hovath, P. Leupold, G. Lischke, Корни и возможности регулярных языков, DLT 2002, Springer LNCS # 2450 (2003), 220-230.

H. Bordihn, «Контекстно-свободная сила власти контекстно-свободных языков неразрешима», TCS 314 (2004), 445-449.

@ Дэйв Кларк, L = a * | b * будет круглым, но L * будет (a | b) *.

С точки зрения разрешимости язык L является круговым, если существует L ′, такой что L является замыканием под + L , или если он является конечным объединением круговых языков.$L$$L'$$L$$L'$

(Мне не терпится переопределить «циклический», заменив ваш > на ≥ . Это многое упрощает. Затем мы можем охарактеризовать циклические языки как те, для которых существует NDFA, начальное состояние которого имеет только эпсилон-переходы в принимающие состояния и имеет эпсилон-переход к каждому принимающему состоянию).$>$$\ge$

Изменить: Полное (упрощенное) доказательство полноты PSPACE появляется ниже.

Два обновления. Во-первых, нормальная форма, описанная в моем другом ответе, появляется уже в статье Calbrix и Nivat под названием « Префикс и периодические языки рациональных ω- языков».$\omega$ , к сожалению, недоступной в Интернете.

Во-вторых, решение о том, является ли язык циклическим, учитывая, что его DFA является PSPACE-полным.

Круговая форма в PSPACE. Так как NPSPACE = PSPACE по теореме Савича, достаточно дать алгоритм NPSPACE для некруглости. Пусть A = ( Q , Σ , δ , q 0 , F ) DFA с | Q | = n государств. Тот факт, что синтаксический моноид L ( A ) имеет размер не более n n, подразумевает, что если L ( A ) не является круговым, то существует слово w длиной не более n $A = (Q,\Sigma,\delta,q_0,F)$$|Q|=n$$L(A)$$n^n$$L(A)$$w$$n^n$такой, что w ∈ L ( A ), но w k ∉ L ( A ) для некоторого k ≤ n . Алгоритм догадок ж и вычисляет & delta ; ш ( д ) = δ ( д , ш ) для всех д ∈ Q , используя O ( п войти п ) пространства (используется для подсчета до п п ). Затем он проверяет, что δ w$w \in L(A)$$w^k \notin L(A)$$k \leq n$$w$$\delta_w(q) = \delta(q,w)$$q \in Q$$O(n\log n)$$n^n$q 0 ) ∈ F, но δ ( k ) w ∉ F для некоторого k ≤ n .$\delta_w(q_0) \in F$$\delta_w^{(k)} \notin F$$k \leq n$

Круглость PSPACE-сложная. Козен показал в своей классической работе 1977 г. « Нижние оценки для систем естественных доказательств», что с учетом списка DFA трудно решить, является ли пересечение принятых ими языков пустым. Мы сводим эту проблему к круглости. Для заданных двоичных DFA A 1 , … , A n мы находим простое число p ∈ [ n , 2 n ] и строим троичную DFA A, принимающую язык L ( A ) = ¯ { 2 w 1 2 w $A_1,\ldots,A_n$$p \in [n,2n]$$A$⋯ 2 w p : w i ∈ L ( A 1 + ( iмодификациян ) )}. (Приложив немного больше усилий, мы также можем сделатьдвоичный файлA). Нетрудно увидеть (используя тот факт, чтоpпростое), чтоL(A)является круговым тогда и только тогда, когда пересечениеL(A1)∩⋯∩L(An)пусто.

Любое s ∈ L длины p > 0 можно записать в виде x y i z, где x = z = ϵ , y = w ≠ ϵ . Очевидно, что | х у | ≤ p и | у | = | ш | > 0 . Отсюда следует, что язык является регулярным для непустых входов по лемме накачки.$s \in L$$p>0$$xy^{i}z$$x = z = \epsilon$$y = w \neq \epsilon$$|xy| \leq p$$|y| = |w| > 0$

Для w = ϵ определение выполняется, поскольку NDFA, который принимает пустую строку, также будет принимать любое количество пустых строк.$w= \epsilon$

Объединение вышеуказанных языков - это язык L, и поскольку регулярные языки закрыты при объединении, из этого следует, что каждый циркулярный язык является регулярным.

По теореме Райс C I R C U L A R I T Y / T M неразрешима. Доказательство аналогично регулярности.$CIRCULARITY/TM$