Вариант почтовой корреспонденции

Это, вероятно, довольно просто, но рассмотрим стандартную проблему почтовой корреспонденции:

Учитывая и , найдите последовательность индексов такую, что . Это, конечно, неразрешимо.β 1 , … , β N i 1 , … , i K α i 1 ⋯ α i K = β i 1 ⋯ β i $\alpha_1, \ldots, \alpha_N$$\beta_1, \ldots, \beta_N$$i_1, \ldots, i_K$$\alpha_{i_1}\cdots \alpha_{i_K} = \beta_{i_1}\cdots \beta_{i_K}$

Теперь я называю это «вариантом», но это не совсем так - по сути, он выбрасывает «корреспонденцию». В любом случае рассмотрим следующий вариант:

Учитывая и , найдите две последовательности индексов i_1, \ ldots, i_K, j_1, \ ldots, j_ {K}, таких что \ alpha_ {i_1} \ cdots \ alpha_ {i_K} = \ beta_ {j_1} \ cdots \ beta_ {j_ {K}} . Что можно сказать об этом варианте? Если это тривиально, мои извинения!β 1 , … , β $\alpha_1, \ldots, \alpha_N$$\beta_1, \ldots, \beta_N$ α i 1 ⋯ α i K = β j 1 ⋯ β j $i_1, \ldots, i_K, j_1, \ldots, j_{K}$$\alpha_{i_1}\cdots \alpha_{i_K} = \beta_{j_1}\cdots \beta_{j_{K}}$

Эта новая версия - где $K = K'$ - разрешима.

Покажем, что язык $L := \bigcup_{k \geq 1} (A^k \ \cap \ B^k)$ является КЛЛ. Тогда разрешимость следует из разрешимости пустоты КЛЛ.

Мы будем разрабатывать КПК принимать . На входе , этот КПК будет пытаться построить два факторизации , один с использованием слова , и другие , используя слова . Он будет использовать счетчик в стеке, чтобы гарантировать, что эти две факторизации имеют одинаковую длину. Концептуально я буду ссылаться на факторизацию так, чтобы она находилась на вершине а факторизация на сидение внизу . Тогда в стеке будет счетчиков, если абсолютное значение разности числа слов, сопоставленных сверху, минус количество слов снизу равноx x A B A x x B x n n n A $L$$x$$x$$A$$B$$A$$x$$x$$B$$x$$n$$n$ . Нам нужно другое состояние PDA, чтобы записать, какой соответствующий знак соответствует (который говорит нам, если -факторизация длиннее, чем -факторизация, или наоборот).$n$$A$$B$

Просматривая буквы , мы недетерминированно угадываем слово из и слово из с которого начинается эта буква. Как только мы угадаем, мы стремимся сопоставить остальные и с ; если в какой-то момент наше совпадение окажется неудачным, мы остановимся на этом недетерминированном выборе. Таким образом, мы также поддерживаем в состоянии нашего КПК суффикс и который остается соответствующим.t A u B t u x t $x$$t$$A$$u$$B$$t$$u$$x$$t$$u$

Поскольку мы сканируем дальнейшие буквы, мы продолжаем сопоставление, пока не достигнем конца или конца (или обоих). Когда мы достигаем конца слова, мы соответствующим образом обновляем стек, а затем подбираем новое слово для соответствия либо сверху, либо снизу (или обоим).$t$$u$

Мы принимаем, если суффиксы, оставшиеся для сопоставления, пусты как сверху, так и снизу, и в стеке нет счетчиков.

Мы можем эффективно построить этот КПК, поэтому мы можем эффективно решить, принимает ли он что-нибудь или нет (например, путем эффективного преобразования в грамматику и последующего использования обычного метода, чтобы увидеть, генерирует ли G что-нибудь).$G$

Изменить: Можно также превратить это в верхнюю границу, насколько большой может быть, в худшем случае. Я думаю , он должен дать верхнюю границу чего - то примерно как , где есть сумма длин слов в и .2 O ( l 2 ) l A $k$$2^{O(l^2)}$$l$$A$$B$

Редактировать: теперь я вижу, что требование, чтобы и были конечными множествами, также могло быть ослаблено, к требованию, чтобы и были регулярными (возможно, бесконечными). В этом случае вместо сохранения суффикса, оставшегося для сопоставления в «верхнем» и «нижнем», вместо этого мы сохраняем состояния соответствующего DFA, в котором мы находимся, после обработки префикса возможного сопоставленного слова. Если мы достигаем конечного состояния в «верхнем» или «нижнем», мы можем недетерминированным образом вернуться к начальному состоянию для нового угаданного слова. B A $A$$B$$A$$B$

Изменить: это решает более раннюю версию, в которой мы должны решить, есть ли равенство в форме . Новая версия имеет . K = K $\alpha_{i_1} \cdots \alpha_{i_K} = \beta_{j_1} \cdots \beta_{j_{K'}}$$K = K'$

Язык сгенерированный всеми строками вида является регулярным. Язык сгенерированный всеми строками вида является регулярным. Вы спрашиваете, пусто лиТак как регулярны, это разрешимо (фактически, в самое большее экспоненциальное время).α i 1 ⋯ α i K B β j 1 ⋯ β j K $A$$\alpha_{i_1} \cdots \alpha_{i_K}$$B$$\beta_{j_1} \cdots \beta_{j_{K'}}$, $A \cap B$$A,B$