Rottura di simmetria per Z3 - nel contesto della logica UFBV (nuova versione)

Question

(Questo è il mio secondo tentativo per ottenere aiuto. Se la domanda / approccio non ha senso o non è chiaro, per favore fatemelo sapere. Vorrei anche essere contenti qualsiasi piccolo suggerimento o riferimento, che può aiutarmi a capire il comportamento di Z3 con i miei SBA)

Sto lavorando sulla verifica limitata della specifica relazionale utilizzando la logica UFBV Z3. Il problema attuale sto studiando, ha bisogno la falsificazione di tutte le possibili modelli (a causa di un uso negativo di un predicato raggiungibilità), che uccide le prestazioni risolutore in limiti più elevati.

Perché solo una parte dei possibili modelli sono davvero interessanti (non isomorfi agli altri), sto cercando di introdurre tecniche di rottura di simmetria (noto nella zona SAT).

Tuttavia l'uso di quello che io chiamo rottura della simmetria assiomi in grado di migliorare le prestazioni di Z3, in alcuni casi, ma il generale, il comportamento del solutore diventa instabile.

Uno dei miei approcci (credo che la più promettente), basi a rompere la simmetria sui rapporti w.r.t. i loro domini. Si introduce di ciascuna domini D di una relazione R e ogni atomo un \ a D assiomi, che esecuzione di una decisione sulla rappresentazione binaria di R ^ {M} e R ^ {M [a + 1 / a]}, dove M è un modello per la specifica. Per le relazioni omogenei gli assiomi sono rilassati.

Si vada R \ subset AxA una relazione. La mia simmetria rilassato rottura assiomi per un look R in questo modo:

;; 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)))
)))) 

Il mio problema è, che l'effetto di utilizzo di questo SBA non è stabile / coerente. Si differenzia da legato al limite e la forma specifica ad un'altra. Anche l'uso di tutte o solo una delle ASA influisce sulle prestazioni.

Nel contesto SAT successo della cosiddetta rottura della simmetria predicato (SBP) basi di approccio sulla capacità backtracking della SAT risolutore, che (in qualche modo) di garanzia, che se la pista risolutore posteriore, sarà poi potare la ricerca spazio utilizzando, tra gli altri, i SBPS.

• Qual è la differenza (se presenti) nel contesto della Z3?
• Come faccio a far rispettare la risolvere per utilizzare questi assiomi per potare lo spazio di ricerca (quando la pista)?
• Sarebbe l'uso di (quantificatori) modelli per la mia SBA aiuta?

Saluti,

Aboubakr Achraf El Ghazi

Answer 1

In Z3 3.2, ci sono due motori principali per la gestione delle formule quantificati: E-matching e MBQI (di istanza quantificatore modello basato). E-matching è efficace solo nelle formule insoddisfacibile. Z3 non sarà in grado di dimostrare che una formula è soddisfacibile utilizzando questo motore. MBQI è più costoso, ma si può dimostrare che diverse classi di formule (contenenti quantificatori) sono soddisfacibile. La href="http://rise4fun.com/z3/tutorial/guide" guida Z3 descrive questi due motori (e altre opzioni). Per utilizzare in modo efficace Z3 sui problemi non banali, è molto utile per capire come funzionano questi due motori.

La simmetria di rottura è di solito modo molto efficace per ridurre lo spazio di ricerca. E 'difficile individuare esattamente che cosa sta succedendo nel vostro problema. Posso vedere le seguenti spiegazioni per il comportamento non stabile:

• MBQI sta avendo un momento difficile creare un modello che soddisfi i CAS. Anche se i SBA potare lo spazio di ricerca, se il problema è soddisfacibile, Z3 cercherà di costruire un'interpretazione (modello) che soddisfa loro. Quindi, in questo caso, la SBA è solo in testa. Ciò è particolarmente vero, se la formula di ingresso è molto facile da soddisfare, ma diventa difficile quando si aggiunge lo SBA. È possibile confermare questa ipotesi utilizzando l'opzione MBQI_TRACE=true. Z3 visualizzerà messaggi come: [mbqi] failed k!18. Dove k![line-number] è il quantificatore id. È possibile assegnare i tuoi ID utilizzando il tag :qid. Ecco un esempio:

  (assert (forall ((x T) (y T)) (! (=> (E (sottotipo x y) (Sottotipo y x)) (= X y)) : Qid antisimmetria)))

A proposito, è possibile disattivare il modulo MBQI utilizzando MBQI=false.

Nelle versioni future di Z3, stiamo progettando di aggiungere un'opzione per disabilitare MBQI per alcune formule quantificati. Questa funzione può essere utile per SBA.

• Un'altra spiegazione è che E-matching sta creando troppe istanze della SBA. È possibile confermare che utilizzando l'opzione QI_PROFILE=true. Z3 scaricherà informazioni quali:

[quantifier_instances] antisimmetria: 12: 1: 2.00

Il primo numero è il numero di istanze generate. Se questo è l'origine del problema, una soluzione è quella modelli restrittivi assegnare per le SBAs che generano troppi casi. Ad esempio, Z3 userà (R ai aj) come modello per SBA(R, A)_upToDiag. Questo tipo di modello può creare una serie di istanze quadratica. Un altro esperimento consiste nella disabilitazione E-matching. Esempio, l'opzione

AUTO_CONFIG=false EMATCHING=false MBQI=true

Si può anche provare a disabilitare la propagazione rilevanza nella configurazione di cui sopra, l'opzione: RELEVANCY=0.

Infine, un'altra opzione è di generare le istanze della SBA che si ritiene siano utili, e rimuovere le formule quantificati.