Pytania otagowane jako program-verification

Biorąc pod uwagę specyfikację, czy program ją spełnia?

4
Związek między umowami a pisaniem zależnym
Czytałem kilka artykułów na temat typów zależnych i umów programowych. Z większości tego, co przeczytałem, wydaje się, że kontrakty są sprawdzane dynamicznie, a typy zależne sprawdzane statycznie. Było kilka dokumentów, które skłoniły mnie do myślenia, że ​​możliwe są kontrakty częściowo sprawdzane statycznie: Hybrid Type Checking (C. Flanagan - 2006) Unifying …

1
Jak ustalić, czy dowód wymaga „technik wnioskowania wyższego rzędu”?
Pytanie: Załóżmy, że mam specyfikację problemu składającego się z aksjomatów i celu (tj. Powiązanym problemem dowodowym jest to, czy cel jest zadowalający, biorąc pod uwagę wszystkie aksjomaty). Załóżmy również, że problem nie zawiera żadnych niespójności / sprzeczności między aksjomatami. Czy istnieje sposób na wcześniejsze ustalenie (tj. Bez uprzedniego zbudowania pełnego …

2
Pełna kompletność a pełna abstrakcja tłumaczenia programu
Wysiłki związane z weryfikacją kompilatora często sprowadzają się do udowodnienia, że ​​kompilator jest w pełni abstrakcyjny: zachowuje i odzwierciedla (kontekstowe) równoważności. Zamiast dostarczania pełnych dowodów abstrakcji, niektóre ostatnie (oparte na kategoriach) prace weryfikacyjne kompilatora Hasegawy [ 1 , 2 ] i Egger i in. glin. [ 3 ] udowodnić pełną …


2
Formalna semantyka OCaml w Coq
Semantyka dużego podzbioru OCaml, zwanego OCamllight , została sformalizowana w HOL przez Owensa kilka lat temu. Niedawno Kreitz, Hayden i Hickey zaimplementowali w Nuprl teoretyczną semantykę typu mniejszego podzbioru OCaml . Czy istnieje podobny rozwój w Coq?

3
Jak trudno jest zredukować terminację do częściowej poprawności?
Jeśli jesteś zaznajomiony z weryfikacją programu, prawdopodobnie wolisz przeczytać pytanie przed tłem . Jeśli nie jesteś zaznajomiony z weryfikacją programu, być może nadal będziesz w stanie odpowiedzieć na to pytanie, ale prawdopodobnie wolisz najpierw przeczytać tło . tło Często mówi się, że sprawdzenie częściowej poprawności jest nierozstrzygalne. Dla celów dyskusji …

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 …

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 …

1
Wpisz systemy zapobiegające wyciekom pamięci związanym z lenistwem?
Być może głównym źródłem problemów z wydajnością w Haskell jest przypadek, gdy program nieumyślnie tworzy masę nieograniczonej głębokości - powoduje to wyciek pamięci i potencjalne przepełnienie stosu podczas oceny. Klasycznym przykładem jest definiowanie sum = foldr (+) 0w Haskell. Czy są jakieś systemy typów, które statycznie wymuszają brak takich udarów …

1
Dlaczego Proof Checker jest wymagany w Proof Carry Code?
W klasycznym dokumencie PLDI'98 autorstwa Neculi „Projekt i implementacja kompilatora certyfikującego” weryfikator wysokiego poziomu wykorzystuje: VCGen generuje warunki weryfikacji (prognozy bezpieczeństwa) Dowódca logiki twierdzenia pierwszego rzędu, aby udowodnić warunki Kontroler sprawdzania LF, aby sprawdzić dowód od kroku (2) Jestem trochę zdezorientowany krokiem (3). Dlaczego w ogóle jest to wymagane? Czy …

1
Jaka jest właściwa rola weryfikacji w próbkowaniu kwantowym, symulacji i testowaniu metodą rozszerzonego kościoła-Turinga (ECT)?
Ponieważ nie udzielono odpowiedzi, ustawiono flagę z prośbą o przekształcenie tego pytania w wiki społeczności. Komentarze Aarona Sterlinga, Sasho Nikolova i Vora zostały zsyntetyzowane do następującej rozdzielczości, która jest otwarta na dyskusję wiki społeczności: Rozwiązane: W odniesieniu do klasycznych algorytmów, które generują liczby, próbki lub trajektorie symulacji, ścisła logika matematyczna …
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.