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

13

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 ?A1A2L1L2L=L1∩L2AL

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
1
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}
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

Odpowiedzi:

6

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.⟨1,1⟩

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.⟨1,1⟩

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