Obliczanie przecięcia dwóch NPDA tam, gdzie jest to możliwe

Odpowiada sugestii Rafaela dotyczącej przecięcia dwóch NPDA :

Niech i NPDA dla języków odpowiednio i . Zakładając, że wiemy, że jest kontekstu, czy możemy (skutecznie) skonstruować NPDA dla ? $A_1$ $A_2$ $L_1$ $L_2$ $L = L_1 \cap L_2$ $A$ $L$

Każdy typ algorytmu byłby do przyjęcia, ale im bardziej praktyczny, tym lepiej.

computability automata pushdown-automata

— soandos
źródło

przykład takiego L, w którym ani L1 / L2 nie są regularne, a przecięcie nie jest puste, może być pomocne, czy taki L istnieje? nieco podobne problemy z NPDA (testowanie pustki skrzyżowania, testowanie równości) są nierozstrzygalne. zasugeruj migrację / awans do tcs.se, jeśli nie pojawi się żadna odpowiedź

— dniu

@vzn Wierzę, że mam przykładowy stan ~ 50, postaram się znaleźć kogoś, kto jest bardziej minimalny

— soandos

Zbiór ciągów „co najmniej 1/3 1” i „mniej niż 2/3 1” nad alfabetem to oba DCFL, a ich przecięcie to CFL (a nie DCFL)

{0, 1}

$\{0,1\}$

— sjmc

@ sjmc czy możesz naszkicować dowód? nie dla mnie oczywiste. zagłosuje, jeśli opublikujesz go jako odpowiedź, mimo że nie jest to pełna odpowiedź, to jest pewien postęp

— vzn

aktualizacja wydaje się, że odpowiedź na to pytanie jest nierozstrzygalna w tcs.se na podstawie tego dowolnego obliczenia TM można wyrazić jako przecięcie dwóch CFL.

— dniu

Myślę, że jest to możliwe w przypadku podklasy CFL, które są niezmienne w permutacji za pomocą binarnego alfabetu.

Odpowiadają one językom kwantyfikatorów typu porównując liczności dwóch zbiorów. [1] charakteryzuje takie języki akceptowane przez DPDA za pomocą równoważnych zestawów półliniowych, i stwierdza na końcu, że języki kwantyfikatorów akceptowane przez NPDA są skończonymi logicznymi kombinacjami takich języków akceptowanymi przez DPDA. $\langle 1,1\rangle$

Twierdzenie van Benthema ([2]) mówi, że automaty pushdown akceptują kwantyfikatory typu definiowalne w arytmetyce Presburger'a (tj. Definiowane przez zestawy półliniowe). Tak więc, jeśli otrzymujesz dwa języki, które nie są deterministycznymi świetlówkami kompaktowymi (korzystając z pierwszego artykułu, aby wiedzieć, że masz takie przykłady), ich przecięcie powinno być również CFL według tego twierdzenia. $\langle 1,1\rangle$

Zestaw półliniowy, który jest ich przecięciem, może być nieco trudny do obliczenia ... ale jeśli tak, [3] (str. 11-12) podaje algorytm do tworzenia NPDA akceptującego język w oparciu o generatory odpowiadający mu zestaw półliniowy.

[1] Makoto Kanazawa. Monadyczne kwantyzatory rozpoznawane przez deterministyczne automaty wypychające . W Proceedings of the 19 Amsterdam Colloquium, strony 139-146, 2013.

[2] Johann van Benthem. Eseje w logice semantyki . Studies in Linguistics and Philosophy Tom 29, 1986, ss. 151-176.

[3] Marcin Mostowski. Semantyka obliczeniowa dla kwantowych monadycznych . Journal of Applied Non-Classical Logics, 8 (1-2): 107-121, 1998.

— sjmc
źródło