Transcript Presentation

(Yet another) decision
procedure for Equality
Logic
Ofer Strichman and Orly Meir
Technion
Technion
1
Equality Logic

E:
0
0
0
1
0
1
(x1 = x2 Æ (x2 = x3 Ç x1  x3))

Domain: x1,x2,x3 2 N

The satisfiability problem: is there an assignment to
x1,x2,x3 that satisfies E ?

Q: When is Equality Logic useful ?...
Technion
2
Equality Logic
0
0
0
1
0
1

E:
(x1 = x2 Æ (x2 = x3 Ç x1  x3))

A: Mainly when combined with Uninterpreted
Functions f(x,y), g(z),…

Uninterpreted Functions can be reduced to Equality
Logic via e.g. Ackermann’s reduction.

Mainly used in proving equivalences, but not only.
Technion
3
Basic notions
E: x = y Æ y = z Æ z  x
(non-polar) Equality Graph:
y
x
z
Gives an abstract view of E
Technion
4
From Equality to Propositional Logic
Bryant & Velev CAV’00 – the Sparse method
E : x1 = x2 Æ x2 = x3 Æ x1  x3
B:
e1,2
Æ
e2,3 Æ :e1,3
e1,3
x1
x2
x3

Encode all edges with Boolean variables
 This
is an abstraction
 Transitivity of equality is lost!
 Must add transitivity constraints!
Technion
5
From Equality to Propositional Logic
Bryant & Velev CAV’00 – the Sparse method
E : x1 = x2 Æ x2 = x3 Æ x1  x3
B:
e1,2
Æ
e2,3 Æ :e1,3
e1,3
x1
x2
x3

Transitivity Constraints: For each cycle of size n,
forbid a true assignment to n-1 edges
T S = (e1,2 Æ e2,3 ! e1,3) Æ
(e1,2 Æ e1,3 ! e2,3) Æ
(e1,3 Æ e2,3 ! e1,2)
Check: B Æ T S
Technion
6
From Equality to Propositional Logic
Bryant & Velev CAV’00 – the Sparse method

Thm-1: It is sufficient to constrain simple cycles only
T
e2
T
T
e3
e4 F
e1
e6
T
e5
T
Technion
7
From Equality to Propositional Logic
Bryant & Velev CAV’00 – the Sparse method

Thm-2: It is sufficient to constrain chord-free simple
cycles
T
e2
T
e5
F e1
T
F
T
e3
e4
Technion
8
From Equality to Propositional Logic
Bryant & Velev CAV’00 – the Sparse method

Still, there can be an exponential number of chordfree simple cycles…
….

Solution: make the graph ‘chordal’ by adding edges.
Technion
9
From Equality to Propositional Logic
Bryant & Velev CAV’00 – the Sparse method

In a chordal graph, it is sufficient to constrain only
triangles.
T
T
Contradiction!
T
T
T
F
T

Polynomial # of edges and constraints.

# constraints = 3 £ #triangles
Technion
10
An improvement
Reduced Transitivity Constraints (RTC)

So far we did not consider the polarity of the edges.
E: x = y Æ y = z Æ z  x

Assuming E is in Negation Normal Form
y
(polar) Equality Graph:
x

Technion
z
11
Monotonicity of NNF

Thm-3: NNF formulas are monotonically satisfied
(in CNF this is simply the pure literal rule)

Let  be in NNF and satisfiable. Thm-3 implies:
 Let
²
’ from  by switching the value of a ‘mis-assigned’
pure literal in 
 Derive
 Now
’ ² 
Technion
12
An improvement
Reduced Transitivity Constraints (RTC)

Claim: in the following graph T
sufficient
R
= e3 Æ e2 ! e1 is
z
Allowing e.g.
x = z, x = y, z  y
F
T
e1

e3
=
x

e2
y
T
This is only true because of monotonicity of NNF
Technion
13
Basic notions
y
x
z

Equality Path: a path made of equalities.
we write x =*z

Disequality Path: a path made of equalities and
exactly one disequality. We write x *y

Contradictory Cycle: two nodes x and y, s.t. x=*y
and x * y form a contradictory cycle
Technion
14
Basic notions

Thm-4: Every contradictory cycle is either simple or
contains a simple contradictory cycle
Technion
15
Definitions

Dfn: A contradictory Cycle C is constrained under T
if T does not allow this assignment
T
T
C=
T
T
F
Technion
16
Main theorem

If
T R constrains all simple contradictory cycles,
and
S
S
For every assignment  ,  ² T

S!
S
 ²TR
From the Sparse
method
then
E is satisfiable iff B Æ T R is satisfiable
The Equality
Formula
Technion
17
Proof of the main theorem

() E is satisfiable  BÆT S is satisfiable  BÆT
R is satisfiable

() Proof strategy:
R be a satisfying assignment to B Æ T R
 We will construct S that satisfies B Æ T S
 From this we will conclude that E is satisfiable
 Let
Skip proof
Technion
18
Applying RTC

How can we use the theorem without enumerating
contradictory cycles ?

Answer:
 Consider
the chordal graph.
 Constrain triangles if they are part of a (simple)
contradictory cycle
 How?
Technion
19

Focus on Bi-connected dashed components built on
top of a solid edge
 Includes
all contradictory cycles involving this edge
Technion
20

Make the component chordal
 Chordal-ity guarantees: every
cycle contains a simplicial
vertex, i.e. a vertex that its neighbors are connected.
Technion
21
The RTC algorithm

Constraints cache:



e2 Æ e3 ! e1
e4 Æ e7 ! e2
e5 Æ e8 ! e4
5
8
6
4
7
3
9
2
1
11
Technion
12
22
Constrains all contradictory cycles

Constraints cache:



e2 Æ e3 ! e1
e4 Æ e7 ! e2
e6Æ e3 ! e4
5
8
6
4
7
3
9
2
1
11
Technion
12
23
Results – random graphs
400000
350000
250000
Sparse
200000
RTC
150000
# constraints
300000
100000
50000
0
10:01
05:01
02:01
01:01
01:02
01:05
01:10
Solid : Dashed
V=200, E=800, 16 random topologies
Technion
24
Results
Uclid benchmarks (all unsat)
Technion
25
Random graphs (Satisfiable)
Technion
26

Possible refutations of CNF’s generated by Sparse
Æ
B
TS
TR
B
P3
P0
P4
TS–TR
P1
P2
Constraints of the form e1 Æ e2 ! e3
Hypothesis: (T S – T R) clauses hardly participate in the proof
Thm: B is satisfiable ! B Æ (T S – T R) is satisfiable
Technion
27
T
R
CNF
B
T S- T R
TR
Average on:
10 graphs,
~890K clauses
All Unsat
Sparse: ~ 22 sec.
RTC: ~ 12 Sec.
B
Core
T S- T R
Technion
28
Example: Circuit Transformations
Stage 1
Stage 2

A pipeline processes data in stages

Data is processed in parallel – as in an
assembly line

Formal Model:
Stage 3
Technion
29
Example: Circuit Transformations

The maximum clock frequency depends
on the longest path between two latches

Note that the output of g is used
as input to k

We want to speed up the design by
postponing k to the third stage
Technion
30
Validating Circuit Transformations
?
=
Technion
31
Validating a compilation process

Target program

u1 = x1 + y1;
u2 = x2 + y2;
z = u1  u2 ;

Compilation
Source program
z = (x1 + y1)  (x2 + y2);
Need to prove that:
(u1 = x1 + y1  u2 = x2 + y2  z = u1  u2) $ z = (x1 + y1)  (x2 + y2)
Source
Target
Technion
32
Validating a compilation process

Target program

u1 = x1 + y1;
u2 = x2 + y2;
z = u1  u2 ;

Compilation
Source program
z = (x1 + y1)  (x2 + y2);
Need to prove that:
(u1 = x1 + y1  u2 = x2 + y2  z = u1  u2) $ z = (x1 + y1)  (x2 + y2)
f1
f2
g1
f1
f2
g2
Technion
33
Validating a compilation process

Instead, prove:
under functional consistency: for every uninterpreted function f

x = y ! f(x) = f(y)
Need to prove that:
(u1 = x1 + y1  u2 = x2 + y2  z = u1  u2) $ z = (x1 + y1)  (x2 + y2)

Which translates to (via Ackermann’s
reduction):
g
f1
f2
1
f1
f2
g2
Technion
34
Definitions for the proof…

A Violating cycle under an assignment R:
F
eF
eT1
T
Either
dashed or
solid
T
eT2

This assignment violates T S but not necessarily T R
Technion
36
More definitions for the proof…

An edge e = (vi,vj) is equal under an assignment  iff
there is an equality path between vi and vj all assigned
T under . Denote:
v3
F
T
T
v1
T
Technion
T
v2
37
More definitions for the proof…

An edge e = (vi,vj) is disequal under an assignment 
iff there is a disequality path between vi and vj in
which the solid edge is the only one assigned false by
. Denote:
v3
F
T
T
v1
T
Technion
T
v2
38
Proof…

Observation 1:
The combination
is impossible if = R
(recall: R ² T R)
v3
F
T
T
v1

v2
Observation 2: if (v1,v3) is solid, then
Technion
39
ReConstructing S
Type 1:
Type 2:
It is not the case that
Otherwise it is not the case that
v3
v3
F
F
T
T
F
T
T
v1

T
v1
v2
Assign S (e23) = F

v2
Assign  (e13) = T
In all other cases S = R
Technion
40
ReConstructing S

Starting from R, repeat until convergence:


(eT) := F in all Type 1 cycles
(eF) := T in all Type 2 cycles

All Type 1 and Type 2 triangles now satisfy T S

B is still satisfied (monotonicity of NNF)

Left to prove: all contradictory cycles are still
satisfied
Technion
41
Proof…

Invariant: contradictory cycles are not violating
throughout the reconstruction.
T
v3
F
T
F
T
T
v1

v2
contradicts the precondition to make this
assignment…
Technion
42
Proof…

Invariant: contradictory cycles are not violating
throughout the reconstruction.
v3
F
T
T
T
T
F
v1

v2
contradicts the precondition to make this
assignment…
Technion
43
Constraining simple contradictory cycles
The constraint e3,6 Æ e3,5  e5,6 is not added
x0
x1
x2
cache:
…
e5,6 Æ e4,6  e4,5
x4
x5
x3
x6
Open problem: constrain simple contradictory cycles in P time
Technion
44
Constraining simple contradictory cycles
the constraint
e3,6graph
Æ e3,5has
 e35,6
is not
added, though needed
Suppose the
more
edges
Here we will stop, although …
cache:
x0
x1
…
e5,6 Æ e4,6  e4,5
x2
x4
x5
x3
x6
Open problem: constrain simple contradictory cycles in P time
Technion
45