CODEWITHSUNDEEP
z3smt
BinTest1234
BinTest1234

Reputation: 55

How to code this in Z3

I'm trying to code in Z3 a very simple problem but I got confuse and I don't know how to solve it properly.

So I have an Array with these elements (Python syntax style code):

array = [0, -1, 1, 8, 43]

And I have an access to this array using an index:

x = array[index]

And finally I want to ask z3 what index I need to use to get the element 8, in my example the solution is index = 3 (starting at 0).

I am trying to code this problem in Z3, I wrote the next lines:

(declare-const x Int)
(declare-const index Int)

(assert (= x
           (ite (= index 0)
                0
           (ite (= index 1)
                -1
           (ite (= index 2)
                1
           (ite (= index 3)
                8
           (ite (= index 4)
                43
           999999)))))))
(assert (= x 8))
(check-sat)
(get-model)

And it is working, I had this solution:

sat
(model 
  (define-fun index () Int
    3)
  (define-fun x () Int
    8)
)

But I don't like the last else, the 999999. I needed to use a magic number to know when the value is not found. I tried to see if there is a "it" construction without the else, or a NULL/None/UNSAT or any special value to don't have this problem.

What is the correct way to solve this problem?

Thank you for the help!

Upvotes: 3

Views: 1020

Answers (1)

Patrick Trentin
Patrick Trentin

Reputation: 7342

I know nothing about the "correct" way to solve this problem, since one should probably define "correct" in the first place.

However, there are many ways in which you can encode it as an smt2 formula.

Example 0.

By simply forcing index to fall within the domain [0, 4], you can get the ite do what you want it to do without the need for any magic number.

(declare-const x Int)
(declare-const index Int)

(assert (= x
           (ite (= index 0)
                0
           (ite (= index 1)
                -1
           (ite (= index 2)
                1
           (ite (= index 3)
                8
           43))))))

(assert (and (<= 0 index) (<= index 4)))

(assert (= x 8))
(check-sat)
(get-model)

which returns you the desired model:

~$ z3 example_00.smt2 
sat
(model 
  (define-fun index () Int
    3)
  (define-fun x () Int
    8)
)

Example 1.

(declare-const x Int)
(declare-const index Int)

(assert (ite (= index 0) (= x 0) true))
(assert (ite (= index 1) (= x (- 1)) true))
(assert (ite (= index 2) (= x 1) true))
(assert (ite (= index 3) (= x 8) true))
(assert (ite (= index 4) (= x 43) true))

(assert (and (<= 0 index) (<= index 4)))

(assert (= x 8))
(check-sat)
(get-model)

which returns you the desired model:

~$ z3 example_01.smt2 
sat
(model 
  (define-fun index () Int
    3)
  (define-fun x () Int
    8)
)

Example 2.

(declare-const x Int)
(declare-const index Int)

(assert (or (not (= index 0)) (= x 0)))      ;; (= index 0) -> (= x 0)
(assert (or (not (= index 1)) (= x (- 1))))
(assert (or (not (= index 2)) (= x 1)))
(assert (or (not (= index 3)) (= x 8)))
(assert (or (not (= index 4)) (= x 43)))

(assert (and (<= 0 index) (<= index 4)))

(assert (= x 8))
(check-sat)
(get-model)

which returns you the desired model:

~$ z3 example_02.smt2 
sat
(model 
  (define-fun index () Int
    3)
  (define-fun x () Int
    8)
)

Example 3.

Using the Theory of Arrays

(declare-fun x () Int)
(declare-fun index () Int)
(declare-const ar (Array Int Int))

  ; array's locations initialization
(assert (= (store ar 0 0)     ar))
(assert (= (store ar 1 (- 1)) ar))
(assert (= (store ar 2 1)     ar))
(assert (= (store ar 3 8)     ar))
(assert (= (store ar 4 43)    ar))

  ; x = ar[index]
(assert (= (select ar index) x))

  ; bound index to fall within specified locations
(assert (and (<= 0 index) (<= index 4)))

  ; x = 8
(assert (= x 8))

  ; check
(check-sat)
(get-model)

which returns you the desired model:

~$ z3 example_03.smt2
sat
(model 
  (define-fun x () Int
    8)
  (define-fun ar () (Array Int Int)
    (_ as-array k!0))
  (define-fun index () Int
    3)
  (define-fun k!0 ((x!0 Int)) Int
    (ite (= x!0 2) 1
    (ite (= x!0 3) 8
    (ite (= x!0 1) (- 1)
    (ite (= x!0 0) 0
    (ite (= x!0 4) 43
      5))))))
)

Other examples are possible.

Ideally one would pick the encoding for which z3 has the best performance in solving your formula. On this regard I can not help you, since I typically deal with other SMT solvers.

In general, using more complex theories (e.g. Theory of Arrays) results in the run-time executing more expensive routines so one could think that it's best to avoid it. However, I would say that in my experience this is not a general rule of thumb, since even slight variations of the encoding can result in significant performance differences and very poor or naive encodings can perform pretty bad. Therefore, it's always best to perform extensive bench-marking on various candidate encodings.

Upvotes: 3

Related Questions