SMT'de nicelleştirilmiş aritmetikte akıl yürütmenin sınırları nelerdir? Aşağıdaki görünüşte önemsiz kriter üzerinde

Question

denedim birkaç SMT çözen (CVC3, KVK4 ve Z3):

(set-logic LIA) 
(set-info :smt-lib-version 2.0) 
(assert (forall ((x Int)) (forall ((y Int)) (= y x)))) 
(check-sat) 
(exit) 

çözücüler tüm bilinmeyen döner. Bunun, kararsız bir parça olduğunu (iyi doğrusal olmayan) anlıyorum ama bunu çözebilecek basit bir basit sezgisel keşif olacağını tahmin ediyordum. Ayrıca sabitlerle bazı ekstra iddialar eklemeyi denedim ama yardımcı olmadı.

Bu sorunlara saldırmanın bir yolu var mı ve SMT'de nicelleştirilmiş aritmetikte mantık yürütmenin sınırları nedir?

Answer 1

Örneğiniz, Doğrusal Tamsayı Aritmetik (LIA) kategorisine girer. Qe prosedürlerinin zaman karmaşıklığı oldukça yüksek olmasına rağmen, nicelleştirici eliminasyonunu (qe) kabul eder (0).

Ben LIA için CVC3 ve KVK4 destek nicelik eleme, ancak Z3 sen Rise4Fun execution itibaren

(set-logic LIA) 
(set-info :smt-lib-version 2.0) 
(assert (forall ((x Int)) (forall ((y Int)) (= y x)))) 
(check-sat-using (then qe smt)) 

yapabilirsiniz emin değilim, unsat sonuç var.

Burada qe taktiği, son oyun taktiği smt uygulanmadan önce bir ön işlem adımıdır.

Answer 2

Tampon doğruysa, qe önişlemcisi oldukça pahalı olabilir. Ayrıca, VCC, Poirot, Dafny, VeriFast, Why3 ve ESCJava2 gibi yazılım doğrulama araçlarından gelen formüllerde etkili değildir. Bu uygulamalar tarafından üretilen formüller ayrıca, yorumlanmamış işlevler, diziler, vb. Içermediğinden etkili değildir.

Pad'in cevabının önerdiği gibi Z3, bir motor grubudur. Kullanıcıların bir problemi çözmek için hangi motorun (veya motor kombinasyonunun) kullanılacağını seçmelerine izin veren API'ler ve komutlar sağlar. Kullanıcı sadece (check-sat) diyorsa, giriş formülünü çözmek için en iyi motorun ne olduğunu tahmin etmeye çalışır. Tahmin, kullanıcı tarafından sağlanan giriş formülü ve ek açıklamaların yapısına dayanmaktadır (örnek: set-logic komutu). Otomatik olarak tespit edilen parça setini ve sunduğumuz motor setini sürekli olarak genişletiyoruz.

Z3'ün, LIA gibi bir parçayı kaçırdığı ve qe prosedürünü otomatik olarak uygulanmadığı utanç verici. LIA formülleri için, qe genellikle en iyi seçenektir. E-eşleştirmeye veya MBQI'ye dayalı alternatifler, tamamen farklı parçalara yönelik oldukları için etkili değildir.

Sadece committed code LIA algılayan ( set-logic kullanılmasa bile)

. Değişiklik zaten unstable (devam etmekte olan) dalında kullanılabilir. Yarın gece yapımlarında ve bir sonraki resmi sürümde sunulacak.