Дискретные временные шаги в Z3 / CVC4 / SMT-LIB

Question

Я определяю временные шаги, используя Int в SMT-LIB, что заставляет меня утверждать, что ничего не происходит в негативах:

(declare-sort Pkg) ; A package
(define-sort Time () Int) ; The installation step
; ...
(assert (forall ((t Time) (p Pkg)) (=> (< t 0) (not (installed p t)))))

Я видел, что в Z3 мы можем определить индуктивный Natв обычном стиле. Было бы хорошо использовать индуктивное определение Nat или есть лучший способ сделать то, что я пытаюсь сделать выше?

Answer 1

Вы должны действительно придерживаться Intи положить в >= 0 ограничения соответственно. Z3 много знает о Int, имеет все виды правил доказательства и хитрости, чтобы справиться с этим. Хотя вы действительно можете определить индуктивный Nat типа, вы потеряете все внутренние механизмы для работы с целыми числами, и из-за рекурсивного определения процедуры принятия решений в Z3 будут менее эффективными; особенно в сочетании с другими теориями.

Сказав это, невозможно узнать, если вы не попробуете: могут быть некоторые проблемные области, в которых индуктивное определение может лучше соответствовать. Но, просто взглянув на то, с какими проблемами ты имеешь дело, старый добрый Int кажется, правильный выбор для вас.

Также см. Этот связанный вопрос: Представление временных ограничений в SMT-LIB, которое определенно уместно в вашем контексте.