Вычисление пересечения двух NPDA, где это возможно

По поводу предложения Рафаэля о пересечении двух NPDA :

Пусть и NPDA для контекстно-свободных языков и соответственно. Предполагая, что мы знаем, что зависит от контекста, можем ли мы (эффективно) построить NPDA для ? $A_1$ $A_2$ $L_1$ $L_2$ $L = L_1 \cap L_2$ $A$ $L$

Любой тип алгоритма будет приемлемым, но чем практичнее, тем лучше.

computability automata pushdown-automata soandos
источник

Пример такого L, где ни L1 / L2 не являются регулярными, а пересечение не пустое, может быть полезным, существует ли такой L? Отчасти схожие проблемы с NPDA (проверка пустоты пересечения, проверка равенства) неразрешимы. предложите перенести / продвинуть на tcs.se, если не получится ответа

vzn

@vzn Полагаю, у меня есть пример из ~ 50 штатов, я постараюсь найти кого-нибудь более минимального

soandos

Набор строк «не менее 1/3 1» и «менее 2/3 1» в алфавите

- оба DCFL, и их пересечение - это CFL (а не DCFL)

{0, 1}

$\{0,1\}$

sjmc

@sjmc ты можешь набросать доказательства? не очевидно для меня. будет голосовать, если вы опубликуете его как ответ, хотя это и не полный ответ, а некоторый прогресс

vzn

обновить это, кажется, ответ как неразрешимый в tcs.se на основе того, что произвольное вычисление TM может быть выражено как пересечение двух CFL.

vzn

Ответы:

Я думаю, что это возможно для подкласса КЛЛ, которые инвариантны к перестановке с двоичным алфавитом.

Это соответствует типу языки кванторных сравнивающие Мощности двух множеств. [1] характеризует такие языки, принятые DPDA эквивалентными полулинейными наборами, и в конце утверждает, что языки квантификаторов, принятые NPDA, представляют собой конечные логические комбинации таких языков, принятые DPDA. $\langle 1,1\rangle$

Теорема ван Бентемый ([2]) говорит , что магазинные автоматы принимают вид квантификаторы определимы в Пресбургере арифметике (т.е. определяемой полулинейных множеств). Итак, если вы получаете два языка, которые являются недетерминированными CFL (используя первую статью, чтобы узнать, что у вас есть такие примеры), их пересечение также должно быть CFL по этой теореме. $\langle 1,1\rangle$

Полулинейное множество, являющееся их пересечением, может быть немного сложным для вычисления ... но, если у вас есть это, [3] (стр. 11-12) дают алгоритм для создания NPDA, принимающего язык, основанный на генераторах соответствующий полулинейный набор.

[1] Макото Канадзава. Монадические кванты, распознаваемые детерминированными автоматами . В материалах 19-го Амстердамского коллоквиума, стр. 139-146, 2013.

[2] Иоганн ван Бентем. Очерки логической семантики . Исследования по лингвистике и философии том 29, 1986, с. 151-176.

[3] Марчин Мостовский. Вычислительная семантика для монадических квантов . Журнал прикладной неклассической логики, 8 (1-2): 107-121, 1998.

SJMC
источник