Pytania otagowane jako lo.logic

Logika obliczeniowa i matematyczna.

1
Dobre referencje na temat przybliżonych metod rozwiązywania problemów logicznych
Wiadomo, że wiele problemów logicznych (np. Problemy satysfakcji kilku logik modalnych) nie są rozstrzygalne. Istnieje również wiele nierozstrzygalnych problemów w teorii algorytmów, np. W optymalizacji kombinatorycznej. Ale w praktyce heurystyki i algorytmy przybliżone działają dobrze w przypadku algorytmów praktycznych. Można więc oczekiwać, że odpowiednie będą również algorytmy przybliżone dla problemów …
1
Formuła 3-CNF, która wymaga szerokości rozdzielczości
Przypomnijmy, że szerokość o rozdzielczości odrzucenia o wzorze CNF jest maksymalna liczba literałach w klauzuli występującego w . Dla każdego istnieją niezadowalające wzory w 3-CNF st. Każde odrzucenie rozdzielczości wymaga szerokości co najmniej .F.RRRfaFFw F F wRRRwwwfaFFfaFFwww Potrzebuję konkretnego przykładu niezadowalającej formuły w 3-CNF (tak małej i prostej, jak to …
1
Terminy Lambda-Calculus, które redukują się do siebie
W mojej ciągłej próbie nauki rachunku różniczkowego lambda, „Lambda-Calculus and Combinators an Introduction” Hindleya i Seldina wymienia następujący artykuł (autorstwa Bruce'a Lerchera), który dowodzi, że jedynym redukowalnym wyrażeniem jest to samo (konwersja modulo alfa) to: .( λ x . x x ) ( λ x . x x )(λx.xx)(λx.xx)(\lambda x.xx)(\lambda …
6
Jakie są praktycznie obliczalne właściwości znakowanych układów przejściowych?
Znalazłem systemy przejściowe oznaczone jako dobry model dla mojej aplikacji, a mianowicie jest artykuł na temat modelowania przypadków użycia przy użyciu LTS. Pytanie brzmi: co można łatwo udowodnić w LTS? Chciałbym ponownie wykorzystać istniejące rozwiązania, aby sprawdzić, czy są one przydatne w mojej aplikacji. Chciałbym wiedzieć, jakie właściwości LTS (i …
1
Praktyczne zastosowania gier parzystości
Czy istnieją przykłady praktycznych zastosowań gier parzystych, tj. Systemów w świecie rzeczywistym, które można przedstawić jako gry parzyste? Zwykle powiązana dokumentacja dotycząca gier z parzystością prawie nigdy nie jest praktycznym przykładem tej aplikacji.
3
Zastosowania kategorii
Nie jestem teoretycznym informatykiem. Jestem stabilnym teoretykiem homotopii, posługującym się kategoriami . Widziałem zastosowań teorii teorii kategorii i topos teoretycznej informatyki, a ja zastanawiałem się, czy istnieje jakikolwiek sposób można użyć ∞ -categories (i korzystnie dla mnie, stabilny teorii homotopii) w teoretycznej informatyki. Myślę, że HoTT może być jedną z …
1
Twierdzenie Schaefera i CSP o nieograniczonej szerokości
Twierdzenie dychotomii Schaefera pokazuje, że każdy problem CSP powyżej można rozwiązać w czasie wielomianowym lub jest on NP-kompletny. Dotyczy to tylko problemów CSP o ograniczonej szerokości, z wyłączeniem na przykład SAT i Horn-SAT. Ogólne problemy CSP o nieograniczonej szerokości mogą być bardzo trudne (nawet nieobliczalne), więc ograniczmy się do problemów, …
3
Jak definiuje się dualność typów?
W Wadler's Recursive Types za darmo! [1], zademonstrował dwa typy, i i twierdził, że są podwójne . W szczególności wskazał, że typ nie jest dualistą poprzedniej. Wydaje się, że dualność, o której tu mowa, różni się logicznie od dualności De Morgana. Zastanawiam się, w jaki sposób definiuje się dualność typów, …
2
Ekspresyjność Büchi vs CTL (*)
Jaki jest związek między ekspresyjnością LTL , Büchi / QPTL , CTL i CTL * ? Czy możesz podać odniesienia, które obejmują tak wiele logiki czasowej, jak to możliwe (szczególnie między czasem liniowym a rozgałęzieniem)? Idealny byłby diagram Venna z logiką czasową i pewnymi praktycznymi właściwościami jako przykładami. Na przykład: …
1
Dowód Barendregta na redukcję podmiotu dla
Znalazłem problem w dowodzie Barendregta na redukcję podmiotu (Thm 4.2.5 rachunku Lambda z typami ). Ostatni krok dowodu (strona 60) mówi: „a zatem przez Lemma 4.1.19 (1), Γ,x:ρ⊢P:σ′Γ,x:ρ⊢P:σ′\quad\Gamma,x:\rho\vdash P:\sigma' . ” Jednak zgodnie z Lemmą 4.1.19 (1) powinno to być Γ[α⃗ :=τ⃗ ],x:ρ⊢P:σ′Γ[α→:=τ→],x:ρ⊢P:σ′\Gamma[\vec{\alpha}:=\vec{\tau}],x:\rho\vdash P:\sigma' , ponieważ podstawienie następuje w całym …
2
Logika modalna aksjatyzowana z taką głębokością zagnieżdżenia, która raczej nie znajdzie się w PSPACE?
Szukam logiki modalnej, która jest aksjatyzowana przez skończony zestaw aksjomatów modalnej głębokości zagnieżdżenia, i których problem z zadowalalnością / pochodnością jest mało prawdopodobny w PSPACE. Bez ograniczenia modalnej głębokości zagnieżdżania nie stanowi to problemu, patrz na przykład PDL. Wydaje się jednak, że dowodząc na przykład twardości WYJĄTKOWEJ poprzez redukcję do …
6
Dowód asystent do pisania matematyki
Chciałbym pisać matematyczne dowody przy pomocy asystenta dowodu. Wszystko zostanie napisane przy użyciu logiki pierwszego rzędu (z równością) i naturalnej dedukcji. Tłem jest teoria mnogości (ZF). Na przykład, jak mogę napisać następujący dowód? Aksjomat:∀ x ∀ y( x = y↔ ∀ z( z∈ x ↔ z. Y) )∀x∀y(x=y↔∀z(z∈x↔z∈y))\forall x\forall y(x=y\leftrightarrow\forall …
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.