无法在 Z3 中使用数组定义递归类型

Question

我可以在 Z3 中定义以下递归数据类型：

(declare-datatypes ()
   ((Tree
      (leaf (content Int))
      (node (left Tree) (right Tree)))))

但我无法定义以下内容。我需要先声明什么吗？或者如果不允许，我如何获得等效定义（其中一个构造函数具有相同类型的任意字段，由整数索引）？

(declare-datatypes ()
   ((Tree
      (leaf (content Int))
      (node (children (Array Int Tree))))))

Answer 1

这个（四岁）问题与您的问题非常相关："a datatype contains a set in Z3". In the answers to that question, Leonardo de Moura says that this is not possible, and Nikolaj Bjørner gives a very detailed explanation about how one might work around the limitation. Probably you know they wrote the original paper presenting Z3 in 2008, see Z3: An Efficient SMT Solver。如果幸运的话，也许其中之一会验证递归混合数组和数据类型在 Z3 中仍然不受支持。

此外，您所要求的与 rise4fun Z3 tutorial 中标题 "Mutually recursive datatypes" 下提供的树示例非常相似，除了您的问题使用数组，而 rise4fun 上的示例使用一个列表。我想知道是否可以修改 rise4fun 上的 list-backed 示例以向每个列表节点添加索引。像这样：

(declare-datatypes () ((Tree leaf (node (value Int) (children TreeList)))
                        (TreeList nil (cons (car Tree) (cdr TreeList) (index Int)))))
(assert
    (forall ((treeList TreeList))
        (implies
            (and
                (distinct treeList nil)
                (distinct (cdr treeList) nil)
            )
            (=
                (index (cdr treeList))
                (+ 1 (index treeList))
            )
        )
    )
)
(check-sat)

不幸的是，Z3 给出了这个例子 unsat，所以显然这里有问题。

无法在 Z3 中使用数组定义递归类型

Cannot define recursive type with Array in Z3

arrays

function

algebraic-data-types

smt

z3