<tex dpi = "200"> O \mid p_{i,j} {Теорема|statement= 1, d_i \mid Задача о проверке на пустоту пересечения двух КС- </tex>{{Задачаграмматик неразрешима.|definitionproof=Дано Пусть <tex>m</tex> одинаковых станковA = \{ (G_1, которые работают параллельно, и <tex>nG_2) \mid L(G_1) \cap L(G_2) = \varnothing \}</tex> работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется единицу времени. Для каждой работы есть время окончания Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>d_i</tex> {\overline{---}} время, до которого она должна быть выполнена. Необходимо проверить, существует ли расписание, при котором все работы будут выполнены вовремя.}A} == Описание алгоритма ===== Идея ===Заметим, что если <tex>d_i < m</tex>, то очевиднотаким образом показав, что <tex>C_i > d_i</tex>, следовательно, расписания не существуетдополнение проблемы неразрешимо. Поэтому будем полагатьТак как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций|замкнуты относительно дополнения]], что <tex>m \leqslant d_i</tex> для <tex>i = 1 \ldots n</tex>то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.
Определим Для любого экземпляра ПСП <tex>T = \max\limits_{i \in [1(x_1, x_2, ..., n]}d_ix_n)</tex> {{---}} количество временных интервалов и <tex>[t - 1(y_1, t]</tex>y_2, где <tex>t = 1 \ldots T</tex>. Будем обозначать <tex>[t - 1.., t]y_n)</tex> как над алфавитом <tex>t\Sigma</tex>. Для каждого из них мы можем назначить не более можно подобрать символ <tex>m\# \notin \Sigma</tex> работ (по одной на каждый станок). Для каждой работы каждого экземпляра построим грамматики:* <tex>iG_1 : S \rightarrow aSa \mid a\#a</tex> будем назначать времена обработки на каждой из машин следующим образом: на машине для всех <tex>ma \in \Sigma</tex> работа займет временной интервал . Тогда <tex>d_iL(G_1) = \{ w\#w^R \mid w \in \Sigma^* \}</tex>, на машине где обозначение <tex>(m - 1)w^R</tex> {{---}} интервал разворот <tex>(d_i - 1)w</tex> и так далее, на машине .* <tex>1G_2 : S \rightarrow x_iSy^R_i \mid x_i\#y^R_i</tex> работа займет временной интервал для всех <tex>d_i - m + 1</tex>. В случае коллизий, то есть если найдется временной интервал <tex>k > i = 1</tex>, содержащий <tex>m + 1</tex> работу2, возьмем минимальный такой <tex>k\dots n</tex> и перенесем лишнюю работу из него на ту же машину, но на один временной интервал левее. Будем повторять этот процесс, пока необходимо (и пока Тогда <tex>k > 1</tex>L(G_2) = \{ x_{i_1} x_{i_2} \dots x_{i_m} \# (y_{i_1} y_{i_2} \dots y_{i_m}). Таким образом^R \mid i_1, только первый временной интервал может содержать более <tex>m</tex> работ. Причем это может произойти тогда и только тогдаi_2, когда задача не имеет решения\dots i_m \in \{ 1, то есть не существует расписания2, при котором все работы будут выполнены вовремя.=== Псевдокод ===Определим <tex>h(t)</tex> {{---\dots n \}, m \geqslant 1 \} количество работ во временном интервале <tex>t</tex>.
'''void''' checkExistenceOfSchedule('''int'''* <tex>d</tex>): <tex>T = \max\{d_i \mid i = 1 \ldots n\}</tex> '''for''' <tex>t = 1</tex> '''to''' Если данный экземпляр ПСП имеет решение, то <tex>T</tex> <tex>hL(tG_2) = 0</tex> '''for''' содержит хотя бы одну строку вида <tex>i = 1w\#w^R</tex> '''to''' <tex>n, поэтому </tex> '''for''' <tex>j = d_i</tex> '''to''' <tex>d_i - m + 1</tex> <tex>hL(jG_1) = h\cap L(jG_2) + 1</tex> '''while''' <tex>\exists k > 1ne \varnothing</tex> '''and''' , и наоборот, если он не имеет решения, то <tex>hL(kG_2) = m + 1</tex> '''find''' не содержит строк такого вида, соответственно <tex>\min\{k_0 \mid hL(k_0G_1) = m + 1\}</tex> <tex>hcap L(k_0 - 1G_2) = h(k_0 - 1) + 1</tex> <tex>h(k_0) = m</tex> '''if''' <tex>h(1) \leqslant m</tex> '''return''' true '''else''' '''return''' false=== Асимптотика ===Покажем, что данный алгоритм может быть реализован за время <tex>O(nm)varnothing</tex>.
== Доказательство корректности ==Таким образом мы свели проблему соответствий Поста к <tex>\overline{A}</tex>, следовательно, задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.}}Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров.{{ТеоремаПо двум КС-грамматикам <tex>G_1</tex> и <tex>G_2</tex> можно построить КС-грамматику для [[Замкнутость КС-языков относительно различных операций#.D0.9A.D0.BE.D0.BD.D0.BA.D0.B0.D1.82.D0.B5.D0.BD.D0.B0.D1.86.D0.B8.D1.8F|statement=Для множества работ конкатенации]] задаваемых ими языков <tex>L(G_1)L(G_2)</tex>. По аналогии с дедлайнами этим мы можем рассматривать язык <tex>L(G_1)\#L(G_2)\#</tex>, где <tex>\#</tex> {{---}} новый символ, не встречающийся в алфавите. Заметим, что пересечение языков непусто, то есть <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex>d_1, d_2тогда и только тогда, когда <tex>L(G_1)\#L(G_2)\ldots d_n#</tex> содержит [[Алгоритм Ландау-Шмидта#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|тандемный повтор]]. Аналогично можно заметить, что пересечение <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex> задача имеет решение тогда и только тогда, когда <tex>hL(1G_1) \leqslant m#L(G_2)^R</tex>содержит палиндром. Таким образом, мы имеем:{{Утверждение|proofstatement=Изначально алгоритм присваивает все стадии обработки каждой работы Пусть дана грамматика <tex>iG</tex> , <tex>L(то есть обработку на каждом станкеG) попарно различным временным интервалам= L</tex>. Тогда следующие задачи неразрешимы:# Содержит ли <tex>L</tex> тандемный повтор.# Содержит ли <tex>L</tex> палиндром.
}}
