Вопрос по – список конкат в z3

2

Есть ли способ объединить два списка в z3? Похоже на оператор @ в ML? Я думал о том, чтобы определить это сам, но я не думаю, что z3 поддерживает определения рекурсивных функций, т.е.

<code>define-fun concat ( (List l1) (List l2) List 
   (ite (isNil l1) (l2) (concat (tail l1) (insert (head l1) l2)) )
)
</code>

Ваш Ответ

2   ответа
2

что SMT-Lib2 не допускает определения рекурсивных функций. (В SMT-Lib2 определения функций больше похожи на макросы, они хороши для сокращений.)

Обычный Трюк должен объявлять такие символы как неинтерпретированные функции, а затем утверждать определяющие уравнения как количественные аксиомы. Конечно, как только в игру вступают квантификаторы, решатель может начать возвращатьсunknown илиtimeout для "сложных" запросов. Тем не менее, Z3 довольно хорош во многих целях, возникающих из типичных задач проверки программного обеспечения, поэтому он должен быть в состоянии доказать многие свойства, представляющие интере

Вот пример, иллюстрирующий, как вы можете определитьlen а такжеappend списки, а затем доказать некоторые теоремы о них. Обратите внимание, что если для доказательства требуется индукция, то Z3, скорее всего, истечет по тайм-ауту (как во втором примере ниже), но будущие версии Z3 также смогут обрабатывать индуктивные доказательства.

Вот постоянная ссылка на этот пример на веб-сайте Z3, если вы хотите поиграть:http: //rise4fun.com/Z3/RYm

; declare len as an uninterpreted function
(declare-fun len ((List Int)) Int)

; assert defining equations for len as an axiom
(assert (forall ((xs (List Int)))
          (ite (= nil xs)
               (= 0                     (len xs))
               (= (+ 1 (len (tail xs))) (len xs)))))

; declare append as an uninterpreted function
(declare-fun append ((List Int) (List Int)) (List Int))

; assert defining equations for append as an axiom
(assert (forall ((xs (List Int)) (ys (List Int)))
            (ite (= nil xs)
                 (= (append xs ys) ys)
                 (= (append xs ys) (insert (head xs) (append (tail xs) ys))))))

; declare some existential constants
(declare-fun x () Int)
(declare-fun xs () (List Int))
(declare-fun ys () (List Int))

; prove len (insert x xs) = 1 + len xs
; note that we assert the negation, so unsat means the theorem is valid
(push)
(assert (not (= (+ 1 (len xs)) (len (insert x xs)))))
(check-sat)
(pop)

; prove (len (append xs ys)) = len xs + len ys
; note that Z3 will time out since this proof requires induction
; future versions might very well be able to deal with it..
(push)
(assert (not (= (len (append xs ys)) (+ (len xs) (len ys)))))
(check-sat)
(pop)
Статья Рустана Лейно "Автоматизация индукции с помощью SMT Solver" Research.microsoft.com / EN-US / гм / люди / Лейно / документы / krml218.pdf) также может быть здесь интересно, хотя это не имеет прямого отношения к кодированию индуктивных доказательств в Z3. Malte Schwerhoff
2

если вы хотите установить границу глубины рекурсии, у Z3 обычно гораздо меньше проблем с вашими утверждениями. Вам даже не нужно полагаться на MBQI, который часто занимает слишком много времени, чтобы быть практичным. Концептуально, вы захотите сделать:

; the macro finder can figure out when universal declarations are macros
(set-option :macro-finder true)

(declare-fun len0 ((List Int)) Int)
(assert (forall ((xs (List Int))) (= (len0 xs) 0)))

(declare-fun len1 ((List Int)) Int)
(assert (forall ((xs (List Int))) (ite (= xs nil)
                                       0
                                       (+ 1 (len0 (tail xs))))))

(declare-fun len2 ((List Int)) Int)
(assert (forall ((xs (List Int))) (ite (= xs nil)
                                       0
                                       (+ 1 (len1 (tail xs))))))

... и так далее. Записывать все это вручную, вероятно, будет непросто, поэтому я бы рекомендовал использовать программный API. (Бесстыдная вилка: я работаю над Привязки к ракеткам а такжевот ка ты бы сделал это там.)

Похожие вопросы