Jakie są odpowiednie izomorfizmy między językami formalnymi?

Język formalny nad alfabetem jest podzbiorem , czyli zbiór słów nad tym alfabecie. Dwa formalne języki i są sobie równe, jeśli odpowiadające im zbiory są ponadto równe jako podzbiory . W teorii złożoności można używać języków, aby sformalizować pojęcie „problemu”. Można narzekać, że „ogólnie” ekstensywna równość jest nierozstrzygalna, ale wierzę, że byłoby to mylne.$L$$\Sigma$$\Sigma^*$$L$$L'$$L\cup L'$

Ja rozważając poniższy problem, ponieważ od pewnego czasu: dwa języki i przez alfabetów i (gdzie , , i$L$$L'$$\Sigma=\{a,b\}$$\Sigma'=\{c,d\}$$a$$b$$c$$d$to odrębne litery), nigdy nie mogą być równe, nawet jeśli opisują „dokładnie” ten sam „problem”. Ale powinny być izomorficzne, jeśli naprawdę opisują „dokładnie” ten sam „problem”. Chciałbym wiedzieć, jakie są możliwe pojęcia izomorfizmu odpowiednie dla teorii złożoności. Początkowo myślałem, że słaby obliczeniowo „tłumacz”, taki jak maszyna o stanie skończonym, może być użyty do zdefiniowania dozwolonych izomorfizmów, ale wydaje się, że już to się psuje w przypadku trywialnych tłumaczeń składniowych między równoważnymi formułami logicznymi. (Zobacz na przykład tę tabelę z definicją składniową podwójnego w logice liniowej$A^\bot$ ).

Dzisiaj wpadłem na następujący pomysł: definicja języka odpowiadająca określonemu „problemowi decyzyjnemu” często składa się z dwóch części: (1) kodowania dozwolonych wystąpień problemu jako skończonych ciągów symboli oraz (2) definicji „ zaakceptowane ”przypadki problemów, które należą do języka. Jeśli sprawdzenie, czy dany ciąg znaków jest kodowaniem dozwolonej instancji problemu, wymaga już maszyny obliczeniowej silniejszej niż maszyna stanu skończonego, to ta silniejsza maszyna powinna również zostać użyta do definicji dozwolonych izomorfizmów.

Pytania: Czy ta linia rozumowania ma szansę „rozwiązać” mój problem? Czy mój problem został już rozwiązany, więc muszę tylko przeczytać odpowiednie referencje? Czy sam mój problem ma jakiś sens, czy jest to tak samo mylne, jak narzekanie na nierozstrzygalność ekstensywnej równości?

Edytuj (jeszcze nie odpowiedź) Zauważyłem, że „(1) Kodowanie dozwolonych wystąpień problemów jako skończonych ciągów symboli” zawiera już (ukryte) założenie znormalizowanego wejścia. Bez tego założenia dwa różne ciągi skończone mogą odpowiadać tej samej instancji problemu. Zamiast sprawdzania, czy dany ciąg skończony jest prawidłowy, sprawdzanie może wygenerować znormalizowany sygnał wejściowy (i odwzorować niepoprawne ciągi na ciąg specjalny).

To ustawienie ma tę zaletę, że maszyna wykonująca sprawdzanie / normalizację jest już wyposażona w środki do przekształcania łańcuchów skończonych na inne łańcuchy skończone. Dozwolona maszyna (klasa złożoności) dla tego zadania może być częścią definicji problemu, a (izo) morfizmy wykorzystywałyby tę samą maszynę (klasa złożoności). (Sugestia „wielokrotnych redukcji wielokrotnych” z komentarza Raphaela byłaby rzeczywiście jedną z możliwości wystąpienia problemów w .)$\mathsf{P}$

Wadą jest to, że ten sposób specyfikacji może być odpowiedni tylko dla maszyn deterministycznych. Maszyny niedeterministyczne mogą wymagać bardziej elastycznych sposobów określania / decydowania, czy dwa ciągi wejściowe odpowiadają tej samej instancji problemu.

Czy mój problem został już rozwiązany, więc muszę tylko przeczytać odpowiednie referencje?

Istotna jest teoria abstrakcyjnej rodziny języków . Na przykład morfizmy zdefiniowane przez przetworniki skończonego stanu prowadzą do rodziny stożków . Krótkie przemówienie ICM Eilenberga z 1970 r. Ładnie wyjaśnia te ramy, patrz także rozdział 11 „Właściwości zamykania rodzin języków” z Wstępu do teorii automatów, języków i obliczeń (wydanie pierwsze) J. Hopcroft i J. Ullman z 1979 r. Jednak , tylko niedeterministyczne języki pasują do tej struktury ¹ . Ostatecznie książka Teoria kodów J. Berstela i D. Perrina z 1985 roku pomogła mi znaleźć rozsądne rozwiązania mojego problemu. Kody i automatyJ. Berstela, D. Perrina i C. Reutenauera z 2009 roku jest znaczącą wersją tej książki o znacznie szerszym zasięgu.

Czy ten sposób rozumowania ma jakąkolwiek szansę na „rozwiązanie” mojego problemu? Czy sam mój problem ma jakiś sens, czy jest to tak samo mylne jak ...?

Założenie, że istnieje jedna poprawna kategoria do modelowania izomorfizmów między językami w celu „sformalizowania koncepcji problemu” jest błędne. Istnieje wiele różnych kategorii, które mogą być interesujące w kontekście języków formalnych.

Oto trzy interesujące kategorie związane z redukcjami wielokrotnymi, które będą określane jako całkowite , częściowe i relacyjne . Obiektami kategorii są pary skończonego alfabetu i języka słów nad . W sumie morfizmy między obiektem źródłowym a obiektem docelowym są funkcjami sumarycznymi z . Na częściowe , gdy morfizmami to funkcja częściowa$(\Sigma, L)$$\Sigma$$L\subset\Sigma^*$$\Sigma$$(\Sigma, L)$$(\Sigma', L')$$f : \Sigma^* \to \Sigma'^*$$L=f^{-1}(L')$$f : \Sigma^* \to \Sigma'^*$ z , gdzie dwie funkcje cząstkowe , są uważane za równe (jako morfizmy), jeśli dla wszystkich . W przypadku relacji morfizmy są relacjami z , a dowolne dwa morfizmy między tym samym źródłem i celem są uważane za równe . Zestaw dozwolonych funkcji lub relacji można ograniczyć do różnych prostych „tłumaczy”, aby uzyskać kategorie z interesującymi izomorfizmami.$L=f^{-1}(L')$$f$$g$$f(x)=g(x)$$x\in L$$R\subset \Sigma^* \times \Sigma'^*$$L=R^{-1}(L')$

• Homomorfizmy monoidów od do dają bardzo podstawową kategorię całkowitą . Izomorfizmy tej kategorii to w zasadzie tylko bijections między i . Każda rozsądna rodzina języków powinna lepiej szanować te izomorfizmy, tj. Być zamknięta w odwrotnych homomorfizmach.$\Sigma^*$$\Sigma'^*$$\Sigma$$\Sigma'$
• Funkcje cząstkowe zdefiniowane przez deterministyczne translatory przestrzeni logów maszyny Turinga dają całkiem naturalną kategorię cząstkową . Jest w stanie przeprowadzić wiele trywialnych przekształceń składniowych (takich jak stosowanie praw De Morgana do przenoszenia negacji na atomy), obejmuje morfizm określony przez funkcjonalne przetworniki skończonego stanu ¹ , a także potrafi sortować. Mimo to nie zidentyfikuje dwóch całkowicie niepowiązanych języków jako izomorficznych, ponieważ równość składu dwóch morfizmów z morfizmem tożsamości jest znacznie silniejszym wymogiem niż samo istnienie wielokrotnych redukcji w obu kierunkach.
• Relacje zdefiniowane przez niedeterministycznych tłumaczy logów maszyny Turinga dają interesującą kategorię relacyjną . W tej kategorii SAT jest izomorficzny w stosunku do HORNSAT, ale pozostaje otwarte pytanie, czy TAUTOLOGIA, czy jakikolwiek inny wspólny NP-problem jest izomorficzny w stosunku do HORNSAT.

Dwa języki i nad alfabetami i (gdzie , , i to różne litery) nigdy nie mogą być równe, nawet jeśli opisują „dokładnie” ten sam „problem”. Ale powinny być izomorficzne, jeśli naprawdę opisują „dokładnie” ten sam „problem”.$L$$L'$$\Sigma=\{a,b\}$$\Sigma'=\{c,d\}$$a$$b$$c$$d$

Opisana powyżej bardzo podstawowa kategoria całkowita rozwiązuje ten problem.

Problem staje się bardziej interesujący, jeśli „dokładnie to samo” zostanie zastąpione przez „prawie takie samo dla najbardziej praktycznych celów”: Niech będzie językiem nad i niech będzie język ponad uzyskany z przez podstawienie , , i . Zauważ, że we wszystkich kategoriach całkowitych i nie są izomorficzne dla . To samo dotyczy kategorii częściowych , jeśli część „gdzie dwie funkcje częściowe$L$$\Sigma=\{U,C,A,G\}$$L'$$\Sigma'=\{0,1\}$$L$$U \to 00$$C \to 01$$A \to 10$$G \to 11$$L$$L'$$L=\Sigma^*$$f$, uważa się za równe (jako morfizmy), jeśli dla wszystkich "pominięto w definicji.$g$$f(x)=g(x)$$x\in L$

Zupełnie naturalna kategoria częściowa opisana powyżej jest wystarczająca do uczynienia i izomorficznymi. Byłoby miło mieć bardziej podstawową (tj. Bardziej restrykcyjną) kategorię, która czyni je izomorficznymi. Następujące (kolejno bardziej restrykcyjne) kategorie wydają mi się rozsądne:$L$$L'$

• Funkcje cząstkowe realizowane przez jednoznaczne przetworniki stanu skończonego ^{2, w} których jedynym stanem akceptującym jest stan początkowy. Izomorfizmy tej częściowej kategorii są (podzbiorem) bijections między rozpoznawalnymi kodami o zmiennej długości .
• Funkcje cząstkowe realizowane przez deterministyczne przetworniki stanu skończonego, w których jedynym stanem akceptującym jest stan początkowy. Izomorfizmy tej częściowej kategorii są (podzbiorem) bijections między kodami prefiksów .
• Funkcje cząstkowe realizowane jednocześnie przez deterministyczny przetwornik do przodu i do tyłu, w których jedynym stanem akceptującym jest stan początkowy. Izomorfizmy tej częściowej kategorii są (podzbiorem) bijections między kodami bifix .
• Sensowne może być również dalsze ograniczenie funkcji częściowych, tak że izomorfizmy są (podzbiorem) bijectmów między kodami blokowymi .

W teorii złożoności można używać języków, aby sformalizować pojęcie „problemu”.

Jeszcze zanim poznałem teorię kategorii, zastanawiałem się, czy istnieją „bardziej wierne” sposoby sformalizowania pojęcia „problemu”. Po zapoznaniu się z teorią kategorii czasami próbowałem wymyślić możliwe rozwiązania, ale zawsze szybko się poddawałem przy pierwszym potknięciu (bo i tak nikogo to nie obchodzi). Wiem, że Jurij Gurewicz rozwiązał kilka powiązanych pytań, ale jego rozwiązania mają praktyczne zastosowanie, podczas gdy ja szukałem czegoś ładnego i abstrakcyjnego, niezależnego od praktycznego zastosowania.

Większość mojego wolnego czasu przez ostatnie trzy tygodnie poświęciłem w końcu na pewne postępy w tym problemie. Najczęściej spędzałem czas na znajdowaniu irytujących problemów w możliwych rozwiązaniach, które miałem na myśli. Poczucie postępu wynikało z czytania (starych) książek i artykułów oraz poznawania wielu podstawowych pojęć i faktów na temat przetworników i zestawów racjonalnych. W końcu nauczyłem się pojęć kodu przedrostka i kodu bifix (wcześniej kod biprefiksu w książce Berstela), co pozwoliło mi wymyślić rozsądne ³ kategorie opisane powyżej.

Może być trudno docenić te (związane z kodem) kategorie, nie widząc problemów z bardziej oczywistymi kategoriami. Ogólnym problemem jest to, że zamknięcie w składzie może utrudnić zdefiniowanie ładnie ograniczonej klasy funkcji częściowych. Inna kwestia związana jest z faktem, że dodanie jednego (lub pomnożenie przez stałą) jest „funkcją łatwą do obliczenia”, jeśli cyfry liczby podane są w niskiej kolejności, ale nie, jeśli cyfry podano dużą Endian Order.

1 _{Funkcjonalny przetwornik stanu skończonego jest niedeterministycznym przetwornikiem stanu skończonego, który realizuje funkcję częściową. Te funkcje cząstkowe nie mogą być realizowane przez deterministyczne przetworniki stanu skończonego. Można je zrealizować za pomocą deterministycznych bimachin , ale mogą one wymagać skanowania do przodu i do tyłu na wejściu, jeśli chcą działać w przestrzeni .$O(n)$$O(1)$}

2 _{Jednoznaczny przetwornik stanu skończonego jest niedeterministycznym przetwornikiem stanu skończonego z co najmniej jedną ścieżką akceptacji dla każdego wejścia. Realizuje funkcję częściową, dlatego jest również funkcjonalnym przetwornikiem stanu skończonego. Można rozstrzygnąć, czy dany przetwornik stanu skończonego jest jednoznaczny.}

3 _{Nie jestem pewien, jak uzasadnione są przedstawione powyżej sumy i kategorie relacji . Chciałem tylko pokazać proste alternatywy dla częściowej kategorii. Łatwo jest znaleźć więcej alternatyw, na przykład ko-relacyjnych , gdzie morfizmy są relacjami z , a wszelkie dwa morfizmy między tym samym źródłem i celem są uważane za równe. $R\subset \Sigma^* \times \Sigma'^*$$L=R^{-1}(L')-R^{-1}(\Sigma'^*-L')$}