Rozstrzygalność równości świetlówek kompaktowych

Rozstrzyga się następujący problem:

Biorąc pod uwagę bezkontekstową gramatykę , czy ?L ( G ) = $G$$L(G) = \varnothing$

Następujący problem jest nierozstrzygalny:

Biorąc pod uwagę bezkontekstową gramatykę , czy L (G) = A ^ {\ ast} ?L ( G ) = A $G$$L(G) = A^{\ast}$

Czy istnieje charakterystyka języków bezkontekstowych $M$ z rozstrzygającą równością $L(G) = M$ ?

Nie jestem pewien, czy istnieje jakakolwiek ogólna charakterystyka równoważności, ale następujące artykuły Hopcroft, Hunt i Rosenkrantz i. może być dobry początek:

• John E. Hopcroft, O problemach z równoważnością i ograniczaniem dla języków bezkontekstowych, Theory of Computing Systems 3 (2): 119-124, doi: 10.1007 / BF01746517 ;
• Harry B. Hunt, III i Daniel J. Rosenkrantz, O problemach równoważności i ograniczania języków formalnych, Journal of the ACM 24 (3): 387--396, 1977, doi: 10.1145 / 322017.322020 .

Hopcroft pokazuje w szczególności, że jeśli jest regularne, to jest rozstrzygalne iff jest ograniczone, tj. Istnieje słów st .L ( G ) = M M n w 1 , w 2 , … , w n M ⊆ w ∗ 1 w ∗ 2 ⋯ w ∗ $M$$L(G)=M$$M$$n$$w_1,w_2,\ldots,w_n$$M\subseteq w_1^\ast w_2^\ast\cdots w_n^\ast$

Przepraszamy za stary wątek. Ale jest coś, co może być istotne.

Niech pCFL będzie klasą świetlówek kompaktowych zamkniętych permutacją. Problem równości dla pCFL jest rozstrzygalny.

Biorąc pod uwagę w Σ = { σ 1 , … , σ n } , niech W L = { ⟨ # a 1 ( w ) , … , # a n ( w ) ⟩ ∣ w ∈ L } . Zgodnie z twierdzeniem Parikha W L jest półliniowe, ilekroć L jest pozbawione kontekstu.$L$$\Sigma = \{ \sigma_1 , \dots , \sigma_n \}$$W_L = \{ \langle \#_{a_1}(w) , \dots , \#_{a_n}(w) \rangle \mid w \in L\}$$W_L$$L$

Teraz, jeżeli jest w pCFL , że mamy w ∈ L wtw ⟨ # 1 ( wagowo ) , ... , # a n ( szer ) ⟩ ∈ W l . Tak więc, dla L 1 , L 2 , w pCFL , L 1 = L 2 IFF W L 1 = W L 2 . Ale równość zbiorów półliniowych jest rozstrzygalna; widzieć:$L$$w \in L$$\langle \#_{a_1}(w) , \dots , \#_{a_n}(w) \rangle \in W_L$$L_1 , L_2$$L_1 = L_2$$W_{L_1} = W_{L_2}$

• Huynh 1980 „Złożoność zestawów półliniowych”: http://link.springer.com/chapter/10.1007%2F3-540-10003-2_81#

Rodzi to pytanie, na które chciałbym poznać odpowiedź: czy można rozstrzygnąć, czy dany język bezkontekstowy jest zamknięty na permutację?