Czy istnieje najtrudniejszy DCFL?

Greibach pokazowo zdefiniował język , tzw niedeterministycznych wersję z , tak że każdy CFL odwrotna morficznego obraz . Czy istnieje podobne stwierdzenie dotyczące DCFL, być może z dopuszczalnymi ograniczeniami morfizmów? $H$ $D_2$ $H$

(Patrz np. M. Autebert, J. Berstel i L. Boasson. Języki bezkontaktowe i automaty wypychające. W red. R. Rozenberg i A. Salomaa, Handbook of Formal Languages, tom I, rozdział 3. Springer Verlag , 1997.)

fl.formal-languages open-problem context-free nondeterminism hard-instances Michaël Cadilhac
źródło

Odpowiedzi:

Identyczna charakterystyka homomorfizmu DCFL nie wydaje się możliwa. Poniższy fragment pochodzi z oryginalnej pracy Greibacha .

Pokazujemy, że każdy język bezkontekstowy może być wyrażony jako lub dla homomorfizmu . Algebraiczne stwierdzenie brzmi: rodzina języków bezkontekstowych jest głównym AFDL; ... Dla kontrastu, rodzina deterministycznych języków bezkontekstowych nie jest głównym AFDL [7]. $h^{-1}(L_0)$ $h^{-1}(L_0-\{e\})$ $h$

Papier 7 jest wersja konferencyjna na papierze. W wersji konferencyjnej Twierdzenie 4.2 stwierdza, że „rodzina deterministycznych języków bezkontekstowych nie jest głównym AFDL”.

Jednak pewna analogowa charakterystyka może być nadal możliwa. Okhotin przedstawił homomorficzną charakterystykę gramatyki spójnej i logicznej. W przypadku DCFL problem wydaje się być otwarty. Oto wniosek z pracy Okhotina (z 2013 r.).

Każda rodzina języków zamkniętych w odwrotnych homomorfizmach może potencjalnie mieć analogię do odwrotnej homomorficznej charakterystyki Greibacha. Pytanie brzmi, które rodziny to mają? Czy może istnieć dla liniowych, deterministycznych lub jednoznacznych wariantów zwykłych (bezkontekstowych) gramatyk? Czy mogłaby istnieć taka charakterystyka liniowych gramatyk spójnych, jednoznacznych gramatyk spójnych itp.?

Mateus de Oliveira Oliveira
źródło

Dzięki! Wiem jednak, że DCFL nie są główne; dlatego w razie potrzeby pozwalam na ograniczenie morfizmów - mogę dokładniej sformułować moje pytanie jako: jaka jest najmniejsza klasa funkcji F, dla której istnieje język H, gdzie F (H) jest zbiorem wszystkich DCFL - dawać lub przyjmować dodatkowe zamknięcia.

Michaël Cadilhac

Dobrze. Zredagowałem swoją odpowiedź. Wydaje się, że dla DCFL jest to otwarty problem.

Mateus de Oliveira Oliveira

Co zabawne, znam bardzo dobrze artykuł Okhotina, ale nie zauważyłem, że wyraźnie odnosi się do problemu! Więc nie jestem pewien, co tu robić; pewny, że jest to ważna odpowiedź na chwilę , ale należy pozostawić otwarte aż rozwiązany?

Michaël Cadilhac

Nie wiem, na czym polega policja na stronie, szukając rozwiązań trudnych problemów. Osobiście, jeśli ktoś wskazałby mi, że problem, który mnie interesuje, jest otwarty przez wiele lat, zaakceptowałbym odpowiedź. Moim zdaniem w tym przypadku bardziej odpowiednie jest postrzeganie pytania jako wniosku o referencję. Jednak w związku z tym mogą istnieć rozbieżne punkty widzenia. Myślę, że ta dyskusja w meta.cstheory może być pomocna meta.cstheory.stackexchange.com/questions/1058/…

Mateus de Oliveira Oliveira

Oczywiście nie mam nic przeciwko, że akceptujesz odpowiedź. Rzeczywiście jest to bardzo interesująca odpowiedź. Jednak, chociaż odpowiedź w pewnym stopniu pasuje do tytułu, różni się ona bardzo od samego pytania, ponieważ redukcje przestrzeni logicznej są znacznie silniejsze niż homomorfizmy.

Mateus de Oliveira Oliveira

$L_0^{(2)}$ $\{a, \bar{a}, b, \bar{b}, \#, [, ]\}$

γ_{0} [\bar{a} γ_{a}^{(1)} # \bar{b} γ_{b}^{(1)}] \dots [\bar{a} γ_{a}^{(k)} # \bar{b} γ_{b}^{(k)}],

$\gamma_0\;[\bar{a}\gamma_a^{(1)}\#\bar{b}\gamma_b^{(1)}]\;\cdots\; [\bar{a}\gamma_a^{(k)}\#\bar{b}\gamma_b^{(k)}]\enspace,$

$\gamma_0, \gamma_a^{(i)}, \gamma_b^{(i)}$ $\{a, \bar{a}, b, \bar{b}\}$ $w_1w_2\cdots w_k \in \{a, b\}^k$ $\gamma_0 \; \bar{w_1}\gamma_{w_1}^{(1)} \cdots \bar{w_k}\gamma_{w_k}^{(k)}$

$L_0^{(2)}$ $L_0^{(2)}$ $L_0^{(2)}$

Jak wspomniał współpracownik Mateus de Oliveira Oliveira, DCFL nie jest głównym AFL i nie wiadomo, czy istnieje dokładna charakterystyka obejmująca zamknięcie jednego języka w ramach niektórych operacji.

Michaël Cadilhac
źródło

Papier

J.-M. Autebert, Une note sur le cylindre des langages déterministes, Theoretical Computer Science 8 (1979), 395-399

daje krótki dowód na następujący wynik (przypisany do Greibacha), który wydaje się odpowiadać na twoje pytanie:

$L$ $C$ $h$ $R$ $C = h^{-1}(L)\cap R$

J.-E. Kołek
źródło