Pytania otagowane jako lo.logic

Logika obliczeniowa i matematyczna.

1
Znalezienie półcienia problemu satysfakcji z ograniczeń
Podczas testowania bezpieczeństwa systemu lub modelu wielokrotnie pojawiło się następujące pytanie . Motywacja: Wady bezpieczeństwa oprogramowania często nie wynikają z błędów spowodowanych prawidłowymi danymi wejściowymi, ale z błędów wynikających z nieprawidłowych danych wejściowych, które są wystarczająco zbliżone do prawidłowych danych wejściowych, aby przejść przez wiele prostych kontroli poprawności. Klasycznym przykładem …
12 lo.logic  csp  security 
3
Czy istnieje naturalne ograniczenie logiki VO, która przechwytuje P lub NP?
Papier Lauri Hella i José María Turull-Torres, Obliczanie zapytań z logiką wyższego rzędu , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009 proponuje logikę VO, logikę zmiennego rzędu. Umożliwia to kwantyfikację zamówień ponad zmiennymi. VO jest dość potężny i może wyrażać niektóre zapytania, które nie są obliczalne. (Jak wskazał Arthur …
2
Dziedziczna substytucja z hierarchią wszechświata
Czytałem o dziedzicznej zamianie na prosty rachunek Lambda i na logiczną strukturę z odrębnymi terminami i typami. Zastanawiam się, czy są jakieś przykłady dziedzicznej substytucji w systemie o typie zależnym i hierarchii wszechświata? tzn. gdzie True:Set0:Set1:Set2True:Set0:Set1:Set2 True : Set_0 : Set_1:Set_2 itd. Zastanawiam się w szczególności, jak ustalić miarę indukcyjną …
2
Najnowocześniejszy w klasie Monadic?
Monadyczna logika pierwszego rzędu, znana również jako monadyczna klasa problemu decyzyjnego, jest miejscem, w którym wszystkie predykaty biorą jeden argument. Został rozstrzygnięty przez Ackermanna i jest NEXPTIME-complete . Jednak problemy takie jak SAT i SMT mają szybkie algorytmy do ich rozwiązania, pomimo teoretycznych ograniczeń. Zastanawiam się, czy istnieją badania analogiczne …
5
Reprezentowanie powiązanych zmiennych za pomocą funkcji od zastosowań do segregatorów
Problem reprezentowania zmiennych powiązanych w składni, a zwłaszcza podstawiania unikania przechwytywania, jest dobrze znany i ma wiele rozwiązań: zmienne nazwane z równoważnością alfa, wskaźniki de Bruijna, lokalna bezimienność, zbiory nominalne itp. Ale wydaje się, że istnieje inne dość oczywiste podejście, którego jednak nigdzie nie widziałem. Mianowicie, w podstawowej składni mamy …
2
Czy teoria pierwszego rzędu struktury skończonej ograniczyła rangę kwantyfikatora?
Niech będzie dowolną skończoną strukturą. Czy jego teoria pierwszego rzędu ograniczyła rangę kwantyfikatora w tym sensie, że istnieje taki, że dla wszystkich z jest z i ?AA\mathfrak{A} T:=TH(A)T:=TH(A) \mathfrak{T} := \mathfrak{TH}(\mathfrak{A}) q∈Nq∈N q\in\mathbb{N} φ∈Tφ∈T \varphi\in\mathfrak{T} qr(φ)>qqr(φ)>q qr(\varphi) > q φ′∈Tφ′∈T \varphi'\in\mathfrak{T} qr(φ′)≤qqr(φ′)≤q qr(\varphi')\leq q φ′≡φφ′≡φ \varphi'\equiv\varphi
1
Jaka intuicja kryje się za logiką liniową?
Próbuję zrozumieć logikę liniową, aby lepiej zrozumieć systemy typu liniowego. Jednak kiedy czytam zasady, nie rozumiem za tym intuicji, jak to zrobiłem w logice modalnej - oznacza, że A jest wymagane, ponieważ w ramkach Kripke A jest wymagane dla każdego osiągalnego świata [ ◊ A to A jest możliwe mutatis …
1
Czy prawo wykluczenia środkowego implikuje aksjomat K w teorii typów wewnętrznych Intela Martina-Löfa?
Zastanawiam się więc, czy Prawo Wykluczonego Środka (LEM) implikuje tak zwany Axiom K w Intranice Teorii Typów Martina-Löfa. Aksjomat K stwierdza, że W rzeczywistości próbowałem udowodnić bardziej ogólne stwierdzenie, że ale po zredukowaniu do przez indukcję równości utknąłem w pierwszym problemie. Próbowałem też postępować w sprzeczności, ale wydaje się, że …
1
Entscheidungsproblem vs. Unvollständigkeitssatz (miękkie pytanie)
Pierwszy termin jest używany przez Hilberta w swojej pracy z 1928 roku, ale w późniejszej pracy Gödela to samo nazywa się Unvollständigkeitssatz („twierdzenie o niekompletności”). Dla dzisiejszych niemieckich badaczy CS wydaje się, że częściej stosuje się Unvollständigkeitssatz , a Entscheidungsproblem („problem decyzyjny”) jest nadal rozumiany, ale niekoniecznie związany z das …
3
Rozgałęzienie teorii typu impredykatywnego
Większość teorii typów, które znam, są predykcyjne, przez co mam na myśli to Void : Prop Void = (x : Prop) -> x nie jest dobrze wpisany w większość dowodów twierdzeń, ponieważ ten typ pi należy do tego samego wszechświata co Propi tak nie jest Prop : Prop. To czyni …
1
Ramy logiczne a teoria typów
Jaka jest różnica między strukturą logiczną a teorią typów? Oba mają typy, terminy i są oparte na rachunku lambda zależnym od typu. Mamy Edinburg LF, który opiera się na rachunku lambda-pi, jednak wydaje mi się, że istnieje tam subtelna różnica.
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.