Dolne granice wielkości CFG dla określonych języków skończonych


14

Rozważ następujące naturalne pytanie: Biorąc pod uwagę skończony język , jaka jest najmniejsza bezkontekstowa gramatyka generująca ?L.L.

Możemy uczynić pytanie bardziej interesującym, określając sekwencję języków , na przykład jest zbiorem wszystkich permutacji : intuicyjnie, CFG dla „musiałby” mieć rozmiar . Jesteśmy więc zainteresowani asymptotycznym rozmiarem najmniejszych CFG dla języków.L.nL.n{1,,n}L.nΩ(n!)

Podobne pytania zostały poruszone w kilku artykułach:

  • Charikar i in. („Aproksymacja najmniejszej gramatyki: złożoność Kołmogorowa w modelach naturalnych”) zastanów się, jak trudno jest oszacować wielkość najmniejszej CFG generującej dane słowo .
  • Dalsze prace w tym kierunku to Arpe i Reischuk, „O złożoności kompresji opartej na optymalnej gramatyce”.
  • Peter Asveld ma kilka artykułów na ten temat (np. „Generowanie wszystkich permutacji przez gramatyki bezkontekstowe w normalnej formie Chomsky'ego”). Próbuje zoptymalizować niektóre parametry na określonych typach gramatycznych, generując zestaw wszystkich permutacji, w szczególności form normalnych Chomsky'ego i Greibacha.

Jednak do tej pory nie udało mi się znaleźć żadnego papieru, który próbowałby udowodnić powiązanie Wielkości CFG generującej .Ω(n!)L.n

Czy istnieją artykuły określające dolne granice wielkości gramatyk bezkontekstowych dla określonych języków skończonych?

W odpowiedzi na kilka pytań na tej stronie, a także na stronie math.stackexchange, opracowałem prostą metodę, która jest w stanie udowodnić wykładnicze dolne granice CFG dla określonych języków, na przykład . Czy te wyniki są nowe? Trudno mi w to uwierzyć i chętnie zdobędę wskazówki dotyczące literatury.L.n


(usunięto poprzedni komentarz dotyczący usuniętego pytania). sformułował ten problem kompresji w taki sposób, że może być bardzo istotny lub przydatny w dowodzeniu kompresji cfg w dolnych granicach, prawdopodobnie za pomocą technik diagonalizacji i (także być może wiążących się ze złożonością Kołmogorowa).
dniu

Odpowiedzi:


11

Miły recenzent przysłał mi artykuł, który dowodzi dokładnie tej samej dolnej granicy, co ja, dokładnie w ten sam sposób. Papier jest

K. Ellul, B. Krawetz, J. Shallit, M.-w. Wang, Wyrażenia regularne: nowe wyniki i otwarte problemy , J. Autom. Lang. Grzebień. 10 (2005), 407–432.

Wynikiem jest Twierdzenie 30 w artykule.


Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.