Pytania otagowane jako reference-request

Pytania wymagające literatury na temat konkretnych, wąskich zagadnień.

2
Jaki jest obecny stan równoległych lub współbieżnych programów w izomorfizmie Curry-Howarda?
W Dowodach i typach Girarda możemy przeczytać: Z algorytmicznego punktu widzenia rachunek sekwencyjny nie ma izomorfizmu Curry'ego-Howarda ze względu na wiele sposobów pisania tego samego dowodu. To uniemożliwia nam użycie go jako maszynopisu -calculus, chociaż dostrzegamy jakąś głęboką strukturę tego rodzaju, prawdopodobnie związaną z równoległością.λλ\lambda Dowody i typy , JY …
1
Sztuczka zastosowana w dowodzie podwójnie wykładniczej złożoności arytmetyki Presburger'a
Wysłałem to na MathUnderflow, ale nie otrzymałem odpowiedzi, więc pomyślałem, że spróbuję tutaj, Czytam stary artykuł Rabina i Fischera [opublikuje link, jeśli to możliwe], gdzie między innymi udowodniono podwójnie wykładniczą złożoność arytmetyki Presburger'a. Dowód opiera się na istnieniu formuły jan( x )In(x)I_{n}(x) nieformalne stwierdzenie „x &lt;2)2)k x + 1x&lt;22kx+1x < …
1
Unikalne dualne triangulacje prostych wielokątów
Biorąc pod uwagę triangulację (bez punktów Steinera) prostego wielokąta , można rozważyć podwójność tej triangulacji, która jest zdefiniowana następująco. Tworzymy wierzchołek dla każdego trójkąta w naszej triangulacji i łączymy dwa wierzchołki, jeśli odpowiednie trójkąty mają wspólną krawędź. Podwójny wykres jest znany jako drzewo o maksymalnym stopniu trzecim.P.PP W przypadku mojej …
4
Dlaczego wyszukiwanie binarne nazywa się wyszukiwaniem binarnym?
Słyszałem kilka możliwych wyjaśnień, dlatego chciałbym uzyskać pewne wiarygodne odniesienia. Aktualizacja 05.19: Interesuje mnie to pytanie, ponieważ jeden z moich studentów napisał w swojej pracy, że nazwa pochodzi od poniższego wyjaśnienia (1). Do tej pory myślałem / słyszałem, że pochodzi z wyjaśnienia (2). Byłoby mi przykro zarówno z powodu pozostawienia …
3
Równoważność analizy przepływu danych, abstrakcyjna interpretacja i wnioskowanie o typie?
Odpowiedź Babou na ostatnie pytanie przypomina mi, że kiedyś myślę, że przeczytałem artykuł na temat równoważności (zarówno pod względem faktów, które można wywnioskować lub udowodnić, jak i złożoności czasowej działania algorytmu wnioskowania) analizy przepływu danych , abstrakcyjna interpretacja i wnioskowanie typu . W niektórych pod-przypadkach (jak między kontekstową analizą przepływu …
1
Jakie istnieją algorytmy rozwiązywania układów liniowych z liczbami naturalnymi?
Patrzę na następujący problem: Biorąc pod uwagę wymiarowe wektory liczb naturalnych i niektóre wektory wejściowe , czy jest liniową kombinacją z współczynnikami liczb naturalnych?nnnv1,…,vmv1,…,vmv_1, \ldots, v_muuuuuuviviv_i tzn. czy są jakieś gdzie ?t1,…,tm∈Nt1,…,tm∈Nt_1, \ldots, t_m \in \mathbb{N}u=t1v1+⋯+tmvmu=t1v1+⋯+tmvmu = t_1 v_1 + \dots + t_m v_m Oczywiście rzeczywistą wersję tego problemu można …
1
Rozkłady prawdopodobieństwa i złożoność obliczeniowa
To pytanie dotyczy przecięcia teorii prawdopodobieństwa i złożoności obliczeniowej. Jednym kluczowym spostrzeżeniem jest to, że niektóre rozkłady są łatwiejsze do wygenerowania niż inne. Na przykład problem Biorąc pod uwagę liczbę nnn, zwróć równomiernie rozłożoną liczbę jaii z 0 ≤ i &lt; n0≤i&lt;n0 \leq i < n. jest łatwy do rozwiązania. …
1
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ę, …
1
Różnica między językami akceptowanymi przez dwa DFA o różnych stanach początkowych / stanach akceptacji?
Ostatnio zadałem pytanie na temat Math SE. Na razie brak odpowiedzi. To pytanie jest związane z tym pytaniem, ale bardziej technicznymi szczegółami w kierunku informatyki. Biorąc pod uwagę dwa DFA i gdzie zbiór stanów, alfabet wejściowy i funkcja przejścia i są takie same, stany początkowe i stany końcowe (akceptujące) mogą …
2
Wprowadzenie do weryfikacji logicznej pierwszego rzędu
Próbuję nauczyć się różnych podejść do weryfikacji oprogramowania. Przeczytałem kilka artykułów. O ile się dowiedziałem, logika zdaniowa z temporalnym na ogół wykorzystuje sprawdzanie modelu za pomocą solverów SAT (w systemach trwających - reaktywnych), ale co z logiką pierwszego rzędu z temporalną? Czy wykorzystuje dowody twierdzeń? Czy może również używać SAT? …
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.