Изменения

|statement= Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.|proof=Всегда существует оптимально расписание такое, что в нем Пусть <tex>C_i A = \{ (G_1, G_2) \mid L(G_1) \cap L(G_2) = \varnothing \leqslant m + i - 1}</tex> для любого . Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>i = 1 \ldots noverline{A}</tex>, где <tex>m</tex> {{таким образом показав, что дополнение проблемы неразрешимо. Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико---}} количество станковмножественных и алгебраических операций|замкнуты относительно дополнения]], то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.|proof=Рассмотрим оптимальное расписание Для любого экземпляра ПСП <tex>S^*(x_1, x_2, ..., x_n)</tex>, в котором для любого и <tex>i = 1 \ldots k - 1(y_1, y_2, ..., y_n)</tex> выполняется над алфавитом <tex>C_i \leqslant m + i - 1Sigma</tex>, но можно подобрать символ <tex>C_k > m + k - 1\# \notin \Sigma</tex>, где . Для каждого экземпляра построим грамматики:* <tex>kG_1 : S \rightarrow aSa \mid a\#a</tex> максимально. Для начала покажем, что для всех <tex>ka \in \Sigma</tex> не меньше . Тогда <tex>2L(G_1) = \{ w\#w^R \mid w \in \Sigma^* \}</tex>. Пусть есть оптимальное расписание, у которого где обозначение <tex>C_1 > mw^R</tex>. Это значит, что есть период времени {{---}} разворот <tex>tw</tex> такой, что первая работа выполняется в момент .* <tex>tG_2 : S \rightarrow x_iSy^R_i \mid x_i\#y^R_i</tex> и не выполняется в для всех <tex>t - i = 1, 2, \dots n</tex>. Поменяем эти периоды времени местами. То есть все работы, которые выполнялись в момент Тогда <tex>t - 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, i_2, \dots i_m \in \{ 1, 2, \dots n \}, m \geqslant 1\}</tex>. Если данный экземпляр ПСП имеет решение, будут выполняться на тех же станках, но в момент то <tex>tL(G_2)</tex>, и наоборот. Значение содержит хотя бы одну строку вида <tex>C_iw\#w^R</tex> для каждой работы , поэтому <tex>iL(G_1) \cap L(G_2) \ne \varnothing</tex> , и наоборот, если он не увеличитсяимеет решения, так как то <tex>C_1L(G_2)</tex> было минимальным из нихне содержит строк такого вида, а значит ни одна работа не могла быть закончена раньше периода времени соответственно <tex>tL(G_1) \cap L(G_2) = \varnothing</tex>. Будем продолжать этот процесс, пока не будет выполнено равенство  Таким образом мы свели проблему соответствий Поста к <tex>C_1 = m\overline{A}</tex>, следовательно, задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.

== См. также ==Таким образом, мы имеем:{{Утверждение* [[O2Cmax|statement= Пусть дана грамматика <tex>O2 \mid \mid C_{max}G</tex>]]* [[Opi1sumu|, <tex>O \mid p_{ij} L(G) = 1 \mid \sum U_iL</tex>]]. Тогда следующие задачи неразрешимы:* [[Opij1di|# Содержит ли <tex> O \mid p_{i, j} = 1, d_i \mid - L</tex>]]тандемный повтор.* [[Opij1sumwu|# Содержит ли <tex> O \mid p_{i, j} = 1 \mid - \sum w_{i} U_{i}L</tex>]]== Источники информации ==палиндром.* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 171-174 ISBN 978-3-540-69515-8 [[Категория: Алгоритмы и структуры данных]][[Категория: Теория расписаний]]