Symmetriebrechung für Z3 - Im Kontext der UFBV -Logik (neue Version)

Question

(Dies ist mein zweiter Versuch, Hilfe zu erhalten. Wenn die Frage/der Ansatz keinen Sinn machen oder nicht, lassen Sie es mich einfach wissen. Ich würde mich auch über einen kleinen Hinweis oder eine Referenz freuen, die mir helfen kann, das Verhalten von Z3 mit meinen SBAs)

Ich arbeite an der begrenzten Überprüfung der relationalen Spezifikation unter Verwendung der UFBV Z3 -Logik. Das aktuelle Problem, das ich untersuche, erfordert die Fälschung aller möglichen Modelle (aufgrund einer negativen Verwendung eines Prädikats der Erreichbarkeit), das die Löserleistung in höheren Grenzen abtötet.

Da nur ein Teil der möglichen Modelle in der Tat interessant sind (nicht isomorph für andere), versuche ich, Symmetrie -Bruchtechniken (im SAT -Bereich bekannt) einzuführen.

Die Verwendung dessen, was ich als Symmetrie nenne, kann in einigen Fällen die Leistung von Z3 verbessern, aber das allgemeine Verhalten des Lösers wird instabil.

Einer meiner Ansätze (ich denke der vielversprechendste), basiert darauf, die Symmetrie über die Beziehungen zu brechen. Es führt die einzelnen Domänen d einer Beziehung r und jedes Atom a in d axioms ein, die eine Reihenfolge für die binäre Darstellung von r^{m} und r^{m [a+1/a]} erzwingen, wobei m ist Ein Modell für die Spezifikation. Für homogene Beziehungen sind die Axiome entspannt.

Sei r subset axa eine Beziehung. Meine entspannte Symmetrie brechen Axiome für R wie folgt:

;; SBA(R, A)_upToDiag
(assert
 (forall ( (ai A) (aj A) )
  (=>
   (bvult ai aj)
   (=>
    (forall ((x A))
     (=>
       (bvult x aj)
       (= (R ai x) (R (bvadd ai (_ bv1 n)) x)) 
     )
    )
    (=>
     (R ai aj)
     (R (bvadd  ai  (_ bv1 n)) aj)
)))))    

;; SBA(R, A)_diag
(assert
 (forall ( (ai A) )
  (=>
   (forall ((x A))
    (=>
      (bvult x ai)
      (= (R ai x) (R (bvadd ai (_ bv1 n)) x)) 
    )
   )
   (=>
    (R ai ai)
    (R (bvadd  ai  (_ bv1 n)) (bvadd  ai  (_ bv1 n)))
)))) 

Mein Problem ist, dass der Effekt der Verwendung dieses SBAs nicht stabil/konsistent ist. Es unterscheidet sich von gebundenen und Formspezifikation zu einem anderen. Auch die Verwendung aller oder nur eines der SBAs beeinflusst die Leistung.

Im SAT-Kontext der Erfolg der sogenannten Symmetrie-Breaking-Prädikat-Annäherungsbasis auf der Backtracking-Fähigkeit des SAT-Solvers, die (irgendwie) garantiert, dass der Suchraum, wenn der Löser zurück-Track, den Suchraum verwendet wird, mithilfe. unter anderem die SBPs.

• Was sind die Unterschiede (falls vorhanden) im Kontext von Z3?
• Wie kann ich die Lösung erzwingen, um diese Axiome zu verwenden, um den Suchraum zu beschneiden (wenn es zurück ist)?
• Würde die Verwendung von (Quantifizierer-) Mustern für meine SBAs helfen?

Grüße,

Aboubakr Achraf El Ghazi

Answer 1

In Z3 3.2 gibt es zwei Hauptmotoren zum Umgang mit quantifizierten Formeln: E-Matching und MBQI (modellbasierte Quantifikator-Instanziierung). E-Matching ist nur in unbefriedigenden Formeln wirksam. Z3 kann nicht zeigen, dass eine Formel mit dieser Motor befriedigend ist. MBQI ist teurer, aber es kann zeigen, dass mehrere Klassen von Formeln (mit Quantifizierern) zufrieden sind. Das Z3 -Leitfaden beschreibt diese beiden Motoren (und andere Optionen). Um Z3 effektiv für nicht triviale Probleme zu verwenden, ist es sehr nützlich zu verstehen, wie diese beiden Motoren funktionieren.

Das Brechen des Symmetries ist normalerweise eine sehr effektive Möglichkeit, den Suchraum zu verringern. Es ist schwer genau zu bestimmen, was in Ihrem Problem vor sich geht. Ich kann die folgenden Erklärungen für das nicht stabile Verhalten sehen:

• MBQI fällt es schwer, ein Modell zu erstellen, das die SBAs erfüllt. Obwohl der SBAs den Suchraum beschnitten, versucht Z3, wenn das Problem befriedigt ist, eine Interpretation (Modell) aufzubauen, die sie erfüllt. In diesem Fall ist die SBA also gerade über sich. Dies gilt insbesondere, wenn die Eingabeformel sehr einfach zu befriedigen ist, aber schwierig wird, wenn Sie die SBAs hinzufügen. Sie können diese Hypothese mithilfe der Option bestätigen MBQI_TRACE=true. Z3 zeigt Nachrichten an wie: [mbqi] failed k!18. Wo k![line-number] ist die Quantifizierer -ID. Sie können Ihre eigenen IDs mit dem Tag zuweisen :qid. Hier ist ein Beispiel:

  (Assert (forall ((x t) (y t)) (! (=> (und (Subtyp xy) (Subtyp yx)) (= xy)): QID -Antisymmetrie)))))

Übrigens können Sie das MBQI -Modul verwenden MBQI=false.

In zukünftigen Versionen von Z3 planen wir eine Option, MBQI für einige quantifizierte Formeln zu deaktivieren. Diese Funktion kann für SBAs nützlich sein.

• Eine weitere Erklärung ist, dass E-Matching zu viele Instanzen der SBAs erstellt. Sie können dies bestätigen, wenn Sie die Option verwenden QI_PROFILE=true. Z3 wird Informationen wie:

quantifier_instances] Antisymmetrie: 12: 1: 2.00

Die erste Zahl ist die Anzahl der generierten Instanzen. Wenn dies die Quelle des Problems ist, besteht eine Lösung darin, restriktive Muster für die SBAs zuzuweisen, die zu viele Instanzen generieren. Zum Beispiel wird Z3 verwendet (R ai aj) als Muster für SBA(R, A)_upToDiag. Diese Art von Muster kann eine quadratische Anzahl von Instanzen erzeugen. Ein weiteres Experiment besteht darin, die E-Matching zu deaktivieren. Beispiel die Option

AUTO_CONFIG=false EMATCHING=false MBQI=true

Sie können auch versuchen, die Relevanzausbreitung in der obigen Konfiguration zu deaktivieren, Option: RELEVANCY=0.

Eine andere Option besteht schließlich darin, die Instanzen der SBAs zu generieren, von denen Sie glauben, dass sie nützlich sind, und die quantifizierten Formeln zu entfernen.