Introduction

The transfer matrix method is a general technique which has been used to find exact solutions for a great variety of problems. In particular, have been developed techniques, based on this method, to count structures in a grid graph G n,m , e.g., spanning trees, Hamiltonian cycles, independent sets, acyclic orientations, k-coloring, and so on [1,2,7,9]. In the case of others grid topologies, as grid-cylinders and grid-tori, there exists little work done on counting structures. In [9] the transfer matrix technique is used, with some modifications, to count structures in fixed height grid-cylinders and tori. In the case of counting satisfying assignments of Boolean formulas with this type of grid topologies, the work is null as far as we know.

In almost all cases of counting structures in grid graphs, the technique used follows a transfer matrix formulation. For example, Calkin and Wilf [2] used this method for computing the number I(G n,m ) of independent sets of a grid graph G n,m and Golin in [9] count the same number (and others structures) but in grid-cylinders and grid-tori.

The number of independent sets in a grid graph, problem denoted as I(G m,n ), is closely related to the "hard-square model" used in statistical physics and, of particular interest is the so-called "hard-square entropy constant" defined as lim m,n→∞ I(G m,n ) 1/m•n [1]. Applications also include for instance tiling and efficient coding schemes in data storage [12].

It is well known that the number of satisfying assignments (models) of a monotone formula F in two conjunctive normal form 2-CNF, which is a propositional formula formed by a conjunction of disjunctions of two nonnegative literals, is related with the number of independent sets of the constrained undirected graph of the formula [11,9]. The number of models of a Boolean formula F is denoted as #SAT(F ) and the computation of #SAT(F ) for formulas in 2-CNF, denoted as #2-SAT, is a classic #Pcomplete problem.

There is a significant amount of works on the design of algorithms for solving #SAT, #2-SAT and #3-SAT [6,16,10,3,4,8,5,15]. Most of them are based on branch-and-bound techniques, for example, applying the recursive decomposition of the input formula based on the classical Davis and Putnam division rule [8,4].

Regarding to #2-SAT problem, considering formulas with n variables, the better time bounds than the trivial O(2 n ) have been achieved in the works of Dahllöf et al. [4], Fürer [8] and Wahlströn [15]. Wahlströn uses a refinement of the method of analysis, where is extended the concept of compound measures to multivariate measures in which a leading running time of O(1.2377 n ) has obtained, for weighted formulas in 2-CNF.

An important line of research is related to the determination of the constraints on the 2-CF formulas which allow us to compute #2-SAT in polynomial time. In this address, there are few general results, one of them is due to Vadhan [14] who showed that #2-SAT is solved in polynomial time for monotone 2-CNF where all variables appear twice at the most. Roth [11] generalizes the previous results for non only the monotone case, but continuing to consider two ocurrence per variable at the most. In this paper, we extend the class of formulas in 2-CNF in which, counting the number of satisfying assignments can be done in polynomial time.

On the other hand, Bubbley has shown that #2µ-SAT (conjunction of clauses without bound in its length and where each variable may appear at most twice) is a #P-Complete problem [13].

In order to extend the transfer matrix method for considering any kind of 2-CNF's we have to deal with grid graphs with signed edges. In the case of counting models of Boolean formulas with this type of grid topologies, the work is null as far as we know. In this article, we adapt the transfer matrix method considering three classes of grid topologies: grid graphs, grid-cylinders and grid-tori obtained from 2-CNF's not restricted to the monotone case, and we show how to compute the number of models for these classes of formulas. The complexity of our method when counting models in structures of fixed height is polynomial.

Preliminaries

For k and l integers such that k < l, we denote the set {k, k + 1, ..., l} by [k, l]. The Euclidean distance between points u and v in Euclidean 2-space is denoted by 1d).

d(u, v). A grid graph of size m × n is a graph G n,m with vertex set V (n, m) = [0, n] × [0, m] and edge set E(n, m) = {(u, v) ∈ V 2 (n, m) : d(u, v) = 1}. Let E 1 (n, m) = ({0} × [0, m]) × ({n} × [0, m]) and E 2 (n, m) = ([0, n] × {0}) × ([0, n] × {m}) be two sets of edges. A grid-cylinder of size m × n is a graph C(n, m) with vertex set V (n, m) and edge set EC(n, m) = E(n, m) ∪ E (n, m), where E (n, m) ∈ {E 1 (n, m), E 2 (n, m)} (see figures 1b and 1c). A grid-tori of size m × n is a graph T (n, m) with the same vertex set V (n, m) but its edge set is ET (n, m) = E(n, m) ∪ E 1 (n, m) ∪ E 2 (n, m) (see figure

A set I ⊆ V is called an independent set if no two of its elements are joined by an edge. We describe the method used by Calkin as follows.

Let I(G n,m ) be the number of independent sets of G n,m , and let C m be the set of all (m + 1)-vectors v of 0 s and 1 s without two consecutive 1 s (the number of these vectors is F ib m+2 , the (m + 2)-th Fibonacci number). Let T m be an F ib m+2 × F ib m+2 symmetric matrix of 0 s and 1 s whose rows and columns are indexed by the vectors of C m . The entry of T m in position (u, v) is 1 if the vectors u, v are orthogonal, and is 0 otherwise, T m is called the transfer matrix for G n,m . Then, I(G n,m ) is the sum of all entries of the n-th power matrix T n m , i.e., I(G n,m ) = 1 t T n m 1, where 1 is the (F ib m+2 )vector whose entries are all 1 s. For example, if m = 2 and n = 3 we have that C 2 = {(0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 0, 1)},

T 2 =       1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 1 0 0       and T 3 2 =      17      , therefore I(G(2, 3)) = 1T 3 2 1 = 227.

A Boolean formula F is called monotone when each literal appearing in F occurs with just one of its signs. Given a monotone Boolean formula F in 2-conjunctive normal form (2-CN F ), we can associate an undirected graph G F = (V, E), called its constrained graph, where V is the set of variables of F and two vertices of V are connected by an edge in E if they belong to the same clause of F . Conversely, given an undirected graph G = (V, E), we can associate a monotone 2-CN F formula F G with variables V , and where

F G = (u,v)∈E (u ∨ v).

We say that a 2-CN F F is a cycle, path, tree, grid, grid-cylinder or a grid-tori formula if its constrained graph is a cycle, path, tree, grid, grid-cylinder or a grid-tori, respectively.

Extending the Transfer Matrix Method

In order to extend the transfer matrix method for considering any kind of 2-CNF's we have to deal with grid graphs with signed edges. In this case, the associated graph of a formula F is a graph G F = (V, E) with labels on the edges, where V is the set of variables appearing in F , and a clause (l ∨ l ) of F determines an ordered pair (s 1 , s 2 ) of signs assigned as the labels of the edge connecting the variables appearing in l and l . The signs s 1 and s 2 are related to the signs of the literals l and l respectively. For example, the clause (¬x ∨ y) determines the labelled edge: "x − + y" which is equivalent to the edge "y + − x".

Some authors had considered the signs of the literals in the clauses of a 2-CN F F by using orientation of the edge corresponding to the clause [12,13], and then the problem of counting models of F is seen as counting the number of orientations in its respective constrained graph, which has no sink.

A graph with labelled edges on a set A is a triplet G = (V, E, ψ), where (V, E) is a graph, and ψ is a function with domain E and range A. The valuation ψ(e) is called the label of the edge e ∈ E.

We denote S = {+, −}, S = {±, ∓} and Ŝ = S ∪ S. Let G n,m = (V, E, ψ) be a grid graph with labelled edges on S 2 . Let x and y be nodes in V . If e = {x, y} is an edge and ψ(e) = (s, s ), then s (s ) is called the adjacent sign to x (y), see figure 2. Let e = ((i, j), (i , j )) be an edge of a grid graph G n,m , if i = i and j = j , e is called a column-edge (see figure 2b), and if i = i and j = j , e is called a row-edge (see figure 2a). If x is a node of G n,m , then either x has one incident column-edge, or x has two incident column-edges. If x has one incident column-edge e 0 whose label is (s 0 , s 0 ), then we define sgn c (x) = s 0 , where s 0 is the adjacent sign to x (see figure 3a).

s s' x y j=j' i i' a) x y j j' i=i' b) s s' x s' a) x b) o s o s' o s o s 1 s' 1

If x has two incident column-edges e 0 and e 1 with labels (s 0 , s 0 ) and (s 1 , s 1 ) respectively ( see figure 3b ), we define sgn cc : V → Ŝ as follows

sgn cc (x) =        + if (s 0 , s 1 ) = (+, +), − if (s 0 , s 1 ) = (−, −), ± if (s 0 , s 1 ) = (+, −), ∓ if (s 0 , s 1 ) = (−, +).

In general, we can consider the function sgn : V → Ŝ as sgn(x) = sgn c (x) if x has one incident column-edge or sgn(x) = sgn cc (x) if x has two incident column-edges.

+ + + - -+ - - x0 y0 y1 + + y2 x2 x1 + + + + z0 z1 z2 + + -- + + + + + + G 2,0,1 G 2,1,2 x x x 0 1 2 y y y y y y z z z 0 0 0 1 1 1 2 2 2 + - - - + + -- - - + + + + -+ + + + + + + + + + + + + a) b) Fig. 4: a) Grid G 2,2 , b) Subgrids G 2,0,1 , G 2,1,2

Given G n,m = (V, E, ψ) a grid graph with labelled edges on S 2 , we consider for k = 0, ..., n−1 the sub-grid graph with labelled edges

G m,k,k+1 = (V k , E k , ψ k ), where V k = V ∩([k, k+1]×[0, m]), E k = {(u, v) ∈ V 2 k : d(u, v) = 1} and ψ k = ψ | E k the restriction of ψ to E k .

Notice that G m,k,k+1 specifies a grid of two columns and m+1 rows. If x is a node in G m,k,k+1 , then x has only one incident row-edge e. For k = 0, . . . , n − 1 we define sgn k : V k → S as sgn k (x) = s, where s is the adjacent sign of x on the incident row-edge e.

For example, let G 2,2 be the grid graph illustrated in figure 4a. Then sgn(x) = +, for x ∈ {x 0 , x 2 , y 2 , z 0 , z 1 , z 2 }, sgn(y 0 ) = − and sgn(y 1 ) = sgn(x 1 ) = ∓. In G 2,0,1 , we have sgn 0 (x) = + for all x ∈ V 0 . In G 2,1,2 , sgn 1 (x) = + for x ∈ {y 2 , z 1 , z 2 } and sgn 1 (x) = − for x ∈ {y 0 , y 1 , z 0 } (see figure 4b).

Given a vector v = (v 0 , v 1 , . . . , v m ) ∈ {0, 1} m+1 and a string s = s 0 . . . s m of signs in Ŝ, for m ≥ 0, we define the family of operators

ϕ s : {0, 1} m+1 → {0, 1} p , (m + 1 ≤ p ≤ 2m + 2) as ϕ s (v) = (s 0 v 0 , . . . , s m v m )

, where

s j v j =        v j if s j = +, vj if s j = −, (v j , vj ) if s j = ±, ( vj , v j ) if s j = ∓.

(1) for j = 0, . . . , m. For v ∈ {0, 1}, v denotes 1 − v and v denotes (v 0 , ..., vm ). For instance, ϕ +,−,±,∓,− (1, 0, 1, 1, 0) = (+1, −0, ±1, ∓1, −0) = (1, 1, (1, 0), (0, 1), 1).

In general, we can omit the internal parenthesis given the associative property of the cartesian product. In particular, the vector (1, 1, (1, 0), (0, 1), 1) can be seen as (1, 1, 1, 0, 0, 1, 1).

Let F m be the set of all (m+1)-vectors v of 0 s and 1 s, and let C m ⊂ F m be the set of all (m + 1)-vectors v of 0 s and 1 s, such that v does not have two consecutive 1 s. The cardinality of C m (denoted by

|C m |) is F ib m+2 (the (m + 2)-th Fibonacci number), while |F m | = 2 m+1 . Given s = s 0 s 1 • • • s m a string of signs in Ŝ, we define F s m = {e ∈ F m : ϕ s (e) ∈ C m+ }, where = |{s ∈ {s 0 , ..., s m } : s ∈ S}|.

Remark 1. Notice that C m ⊆ F m and that the equality holds when s i = + for all i = 0, ..., m. Furthermore, if there exists i ∈ {0, ..., m} such that

s i ∈ Ŝ, then |F s m | < |C m |.

Let G n,m be a grid graph of size m × n with labelled edges on the set S 2 , we assume that x k 0 , . . . , x k m and x k+1 0 , . . . , x k+1 m are the nodes of the k − th and (k + 1) − th columns respectively of G n,m , 0 ≤ k < n (or columns 0 and 1 of G m,k,k+1 respectively).

For

j = k, k + 1, let s j = s j 0 s j 1 • • • s j m and τ j = τ j 0 τ j 1 • • • τ j m be two string of signs, such that s j i = sgn(x j i ) and τ j i = sgn k (x j i ) for i = 0, • • • , m.

Following the idea proposed in [2], we define a matrix T k = T m,k , the transfer matrix from column k to the column k + 1 of G n,m as follows.

T k is an | F s k+1 m | × | F s k

m | matrix of 0 s and 1 s whose rows and columns are indexed by vectors

(v, u) of F s k+1 m × F s k m .

The entry of T k in position (v, u) is 1 if the vectors ϕ τ k (u) and ϕ τ k+1 (v) are orthogonal, and is 0 otherwise. Notice that if s j i and τ j i are positive signs for i = 0, • • • , m, j = k, k + 1, then T k is the transfer matrix used in the classic transfer method [2].

For example, if G 2,2 is the grid graph with labelled edges as it is illustrated in figure 4. For G 2,0,1 , we have that s 0 = + ∓ +, s 1 = − ∓ + and

τ 0 = τ 1 = + + +, then F +∓+ 2 = {u 1 , • • • , u 4 } and F −∓+ 2 = {v 1 , v 2 , v 3 , v 4 },

where u 1 = (0, 0, 0), u 2 = (0, 1, 0), u 3 = (0, 0, 1), u 4 = (1, 1, 0), v 1 = (1, 0, 0), v 2 = (0, 1, 0), v 3 = (1, 0, 1) and v 4 = (1, 1, 0). The transfer matrix

T 0 = (a ij ) 4×4 , is a 4 × 4 matrix determined, for 1 ≤ i, j ≤ 4, as a ij = 1, if ϕ τ 1 (v i ) • ϕ τ 0 (u j ) = 0 and a ij = 0 otherwise. Since τ 0 = τ 1 = + + +, we have ϕ τ 1 (v i ) = v i and ϕ τ 0 (u j ) = u j . Then T 0 =     1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0    (2)

For G 2,1,2 that is also depicted in figure 4 = {ν 1 ,...,ν 5 }, where µ 1 =(1,0,0), µ 2 =(0,1,0), µ 3 =(1,0,1), µ 4 =(1,1,0), ν 1 =(0,0,0), ν 2 =(1,0,0), ν 3 =(0,1,0), ν 4 =(0,0,1) and ν 5 =(1,0,1). Then,

ϕ −−+ (F −∓+ 2 ) = {(0, 1, 0), (1

, 0, 0), (0, 1, 1), (0, 0, 0)} and ϕ −++ (F −∓+ 2 ) = {(1, 0, 0), (0, 0, 0), (1, 1, 0), (1, 0, 1), (0, 0, 1)}. The transfer matrix

T 1 = (b ij ) 5×4 , is such that, for 1 ≤ i ≤ 5 and 1 ≤ j ≤ 4, b ij = 1, if ϕ −++ (ν i ) • ϕ −−+ (µ j ) = 0 and b ij = 0 otherwise. Then T 1 =       1 0 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1      (3)

In the case, not necessarily monotone, of a formula F having a constrained grid graph G n,m with labelled edges on S 2 and transfer matrices T 0 , . . . , T n−1 , we conclude that the sum of all entries of the product matrix T n−1 • • • T 0 is the number of satisfying assignment of F . This fact is expressed in the following theorem.

Theorem 1. Let F be a grid formula such that its constrained graph is G n,m (1 ≤ n) with labelled edges on S 2 , then #SAT (F ) is given by the sum of all entries of the product matrix T n−1 • • • T 0 , where T k is the transfer matrix of the two consecutive columns:

k and k + 1 of G n,m , k = 0, ..., n − 1.

Before detailing the proof, we consider the following example and observations.

Example 1. Let F = (x 0 ∨ y 0 ) ∧ (¬y 0 ∨ ¬z 0 ) ∧ (z 0 ∨ z 1 ) ∧ (z 1 ∨ z 2 ) ∧ (z 2 ∨ y 2 ) ∧ (y 2 ∨x 2 )∧(x 2 ∨x 1 )∧(¬x 1 ∨x 0 )∧(x 1 ∨y 1 )∧(¬y 1 ∨z 1 )∧(¬y 1 ∨¬y 0 )∧(y 1 ∨y 2 ).The constrained graph of F is the grid graph G 2,2 with labelled edges depicted in Figure 3. Then, from last example, T 0 and T 1 are the transfer matrices given in ( 2) and ( 3) respectively. Now, we have that the product matrix T 1 T 0 is the following

T 1 T 0 =       3 2 2 0 4 2 3 0 1 0 1 0 2 1 2 0 3 1 3 0       therefore, #SAT(F ) = 30.

If F n,m denotes a grid formula having as constrained graph a grid G n,m , for n > 0, we can write

F n,m = ( n i=0 C i ) ∧ ( n−1 =0 R )(4)

where

C i = m−1 k=0 (η i 2k x i k ∨ η i 2k+1 x i k+1 )(5)η i q ∈ S for q = 0, ..., 2m − 1, R = m j=0 (τ 2 j x j ∨ τ 2 +1 j x +1 j )(6)

τ r j ∈ S for j = 0, ..., m, r ∈ {2 , 2 + 1}. Here, the formulas C i and R are called column-f ormula and row-f ormula respectively.

Notice that for n, m > 0

F n,m = F n,m−1 ∧ C n ∧ R n−1 , F m,0 = C 0 , F 0,n = R 0 . (7)

For i = 0, ..., n − 1, we define

F m,i,i+1 = C i ∧ C i+1 ∧ R i(8)

Note that

F n,m = n−1 i=0 F m,i,i+1(9)

If φ : {x i 0 , . . . , x i m } → {0, 1} is an assignment of values for the variables of C i (partial assignments of the variables of F n,m ), this is denoted by the (m + 1)-vector (φ(x i 0 ), ..., φ(x i m )). That is, an assignment for the variables of C i can be seen as a vector in {0, 1} m+1 . Observe that, the assignments of the variables of F n,m can be considered as a matrix of n columns formed by the assignments for the variables of C 0 , ..., C n .

For i = 0, ..., n, let ξ i 0 = η i 0 , ξ i m = η i 2m−1 and ξ i q = sgn(x i q ) for q = 1, ..., m − 1. Also, notice that for v ∈ {0, 1}

ξ i q v = η i 2q−1 v = η i 2q v if η i 2q−1 = η i 2q , (η i 2q−1 v, η i 2q v) otherwise. (10)

To prove the theorem 1, first, we characterize the partial assignments of the variables of F n,m such that satisfies each column-formula C i (lemma 1). Second, we characterize the pairs of assignments that satisfies the formula (8), i.e. satisfies two consecutive column-formulas C i , C i+1 and the respective row-formula R i (lemma 2). Finally, we prove that all matrix of partial assignments derived from the lemmas 1 and 2, satisfies the formula F n,m .

Next, for simplicity we omit the superindex i of v i j , x i j , η i j , τ i j and ξ i j .

Lemma 1. The vector u ∈ {0, 1} m+1 satisfies the formula (5

) iff u ∈ F ξ 0 •••ξ m m .

satisfies the row-formula R j (equation ( 6)) for j = 0, ..., m.

Remark 2. From previous lemma we have

1 t T i 1 = #SAT (F m,i,i+1

), where T i is the transfer matrix of the column i to the column i + 1 of G n,m (the constrained graph of F n,m ).

Finally, we prove the theorem 1.

Proof (Theorem 1). From equation ( 9), it is clear that the vector (u 0 , ...,

u n ) ∈ {0, 1} (n+1)(m+1) satisfies the formula F n,m iff (u i , u i+1 ) sat- isfies F m,i,i+1 for i = 0, ..., n − 1. By lemma 2, (ū i , ūi+1 ) ∈ F ξ i m × F ξ i+1 m and ϕ τ 2i (u)•ϕ τ 2i+1 (v) = 0 for i = 0, ..., n−1. Let a i l i+1 l i be the entry of the trans- fer matrix T i in the position (ū i+1 , ūi ) ∈ F ξ i+1 m × F ξ i m .

Then, by definition of T i and previous analysis, (u 0 , ..., u n ) ∈ {0, 1} (n+1)(m+1) satisfies the formula

F n,m iff (ū 0 , ..., ūn ) ∈ F ξ 0 m × • • • × F ξ n m and a n−1 l n l n−1 • • • a 0 l 1 l 0 = 1. Therefore #SAT (F n,m ) is the cardinality of the set {(ū 0 , • • • , ūn ) ∈ F ξ 0 m × • • • × F ξ n m : a n−1 l n l n−1 • • • a 0 l 1 l 0 = 1}. Taking into account all the terms a n−1 l n l n−1 • • • a 0 l 1 l 0 = 0, we obtain #SAT (F n,m ) = (l 0 ,...,l n )∈I 0 ו••×I n a n−1 l n l n−1 • • • a 1 l 2 l 1 • a 0 l 1 l 0 = 1 t T n−1 • • • T 0 1,

where

I k = {0, ..., r k }, r k =| F ξ k m | for k = 0, ..., n.

Remark 3. Note that T = (T n−1 T n−2 . . . T 0 ) = (α i,j ) rn×r 0 is a r n × r 0matrix, where α i,j is the number of models of F n,m with ūi ∈ F ξ 0 m and ūj ∈ F ξ n m fixed.

Counting Models on Grid-Cylinders and Grid-Tori

In this section, we consider grid-cylinder or a grid-tori formulas. We are interested in counting models for formulas with these classes of grid topologies. For this objective, we introduce the Hadamard product " ", which is defined for k × l matrices as follows. Let A = (a i,j ) k×l and B = (b i,j ) k×l be k × l matrices. The k × l matrix A B = (a i,j b i,j ) is the Hadamard product. Notice that a grid-cylinder C(n, m) can be seen as a grid G n,m = (V (n, m), E(n, m)) with edges from the column 0 to the column n (row 0 to the row m) of G n,m . Then the transfer matrix T n of the column 0 to the column n (row 0 to the row m) has sense.

Theorem 2. Let F be a grid-cylinder formula of size m × n with graph C(n, m) = (V (n, m), EC(n, m)), EC = E ∪ E 1 . Then #SAT (F ) = 1 t T n (T n−1 T n−2 . . . T 0 )1,

where T k is the transfer matrix of the two consecutive columns: k and k + 1 of G n,m , k = 0, ..., n − 1 and T n is the transfer matrix of the columns 0 and n of G n,m .

Clearly the previous theorem, also is true for EC = E∪E 2 (interchanging n by m and m by n). In the following example is illustrated. 5). We have that the matrix T 1 T 0 is given in example 1. The transfer matrix T 2 of columns 0 and 2 is computed as follows.

Example 2. Let F = (x 0 ∨ y 0 ) ∧ (¬y 0 ∨ ¬z 0 ) ∧ (z 0 ∨ z 1 ) ∧ (z 1 ∨ z 2 ) ∧ (z 2 ∨ y 2 ) ∧ (y 2 ∨ x 2 ) ∧ (x 2 ∨ x 1 ) ∧ (¬x 1 ∨ x 0 ) ∧ (x 1 ∨ y 1 ) ∧ (¬y 1 ∨ z 1 ) ∧ (¬y 1 ∨ ¬y 0 ) ∧ (y 1 ∨ y 2 ), (x 0 , z 0 ), (¬x 1 , z 1 ), (¬x 2 , ¬z 2 )) (see figure

The strings of signs for edges from the column 0 to column 2 are given by:

s 0 0 s 0 1 s 0 2 = + ∓ +, s 2 0 s 2 1 s 2 2 = + + +, τ 0 0 τ 0 1 τ 0 2 = + − − and τ 2 0 τ 2 1 τ 2 2 = + + −, then F +∓+ 2 = {u 1 , • • • , u 4 } and F +++ 2 = {v 1 , v 2 , v 3 , v 4 , v 5 }

, where u 1 = (0, 0, 0), u 2 = (0, 1, 0), u 3 = (0, 0, 1), u 4 = (1, 1, 0), v 1 = (0, 0, 0), v 2 = (1, 0, 0), v 3 = (0, 1, 0), v 4 = (0, 0, 1) and v 5 = (1, 0, 1). The transfer matrix T 2 = (a ij ) 5×4 , is a 5 × 4 matrix given by

a ij = 1 if ϕ ++− (v i ) • ϕ +−− (u j ) = 0 and a ij = 0 otherwise (1 ≤ i ≤ 5 and 1 ≤ j ≤ 4). Then T 2 (T 1 T 0 ) =       0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 1 1 1 1 0             3 2 2 0 4 2 3 0 1 0 1 0 2 1 2 0 3 1 3 0       =       0 0 2 0 0 0 3 0 0 0 0 0 2 1 2 0 3 1 3 0       Therefore #SAT (F ) = 17.

Proof (Theorem 2). Let F be a grid-cylinder formula of size m×n. We have that F can be expressed as F = F n,m ∧R n , where F n,m is given by equation (4) and R n = m j=0 (τ 2n j x 0 j ∨τ 2n+1 j x n j ), that is, the graph of F is the graph o G n,m (the constrained graph of F n,m ) adding new labelled edges (with signs τ 2n j and τ 2n+1 j ) from the column 0 to column n of G n,m . Let T n = (β ij ) r n ×r 0 be the transfer matrix of the column 0 to column n of G n,m following the arcs given by R n . From remark 3, T = (T n−1 T n−2 . . . T 0 ) = (α ij ) rn×r 0 , where α i,j is the number of satisfying assignments of F n,m with ūi ∈ F ξ 0 m and ūj ∈ F ξ n m fixed. Also, the formula R n is satisfied by u i and u j iff β ij = 1. Therefore, there are β ij α ij satisfying assignments of F with ūi ∈ F ξ 0 m and ūj ∈ F ξn m fixed. We observe that, the product β ij α ij is the entry a i,j of the Hadamard product T n T .

Transfer Matrix for Cycles

We can adapt our extension for computing the transfer matrix between two consecutive simple cycles instead of two consecutive columns as follows.

Let F m be the set of all (m + 1)-vectors v of 0 s and 1 s (as in section 3), and let C m ⊂ F m be the set of all (m + 1)-vectors v of 0 s and 1 s, such that v does not have two consecutive 1 s and does not have 1 s in the first and last positions. Given s = s 0 s 1 . . . s m a string in Ŝ, we define

F s m = {e ∈ F m : ϕ s (e) ∈ Ck + 1) − th cycles respectively of C n,m , 0 ≤ k < n. For j = k, k + 1, let s j = s j 0 s j 1 • • • s j m and τ j = τ j 0 τ j 1 • • • τ j m

, where s j i = sgn(x j i ) and τ j i = sgn k (x j i ). We define a matrix T k = T m,k , the transfer matrix from cycle k to the cycle k + 1 as follows.

T k is an | F s k+1 m | × | F s k

m | matrix of 0 s and 1 s whose rows and columns are indexed by vectors of

F s k+1 m × F s k m .

The entry of T k in position (u, v) is 1 if the vectors ϕ τ k (u) and ϕ τ k+1 (v) are orthogonal, and is 0 otherwise (see figure 6).

Example 3. We compute the transfer matrices: T 0 from cycle x 0 y 0 z 0 to x 1 y 1 z 1 and T 1 from cycle x 1 y 1 z 1 to x 2 y 2 z 2 for F as in example 2 (see figure 5). We have s 0 0 s 0 1 s 0

2 = + ± ∓, s 1 0 s 1 1 s 1 2 = ∓ ± + and s 2 0 s 2 1 s 2 2 = ∓ + ±. On the other hand, τ 0 = τ 0 0 τ 0 1 τ 0 2 = +−+, τ 1 = τ 1 0 τ 1 1 τ 1 2 = −−+, and τ 2 = τ 2 0 τ 2 1 τ 2 2 = τ 3 = τ 3 0 τ 3 1 τ 3 2 = + + +. Then F +±∓ 2 = {u 1 , u 2 , u 3 }, F ∓±+ 2 = {v 1 , v 2 , v 3 } and F ∓±+ 2 = {w 1 , w 2 , w 3 }

, where u 1 = (0, 1, 0), u 2 = (0, 0, 1), u 3 = (0, 1, 1), v 1 = (0, 0, 0), v 2 = (1, 0, 0), v 3 = (0, 1, 0), w 1 = (1, 0, 0), w 2 = (0, 0, 1) and w 3 = (1, 0, 1). Computing ϕ τ 2k (u) • ϕ τ 2k+1 (v) for k = 0, 1 and following the definition of transfer matrix, we have that T 0 and T 1 are 3×3 matrices given by

T 0 =   1 0 1 1 0 1 1 1 1   , T 1 =   1 0 1 1 1 1 1 0 1   .

Remark 4. For F from example 2,

1T 1 T 0 1 = 1   2 1 2 3 1 3 2 1 2   1 = 17 = #SAT (F ).

The following theorem can also be used for computing #SAT (F ) for F , a grid-cylinder. Proof. The proof is similar to the proof of theorem 1, taking F m , C m , F s m and the transfer matrix for cycles as in section 4.1. We observe that, in this case the column formulas C i given by equation ( 5) are simple cycles.

Using theorem 3 and Hadamard product we can compute #SAT (F ) for F , a grid-tori. The following theorem shows us how to proceed.

Theorem 4. Let F be a grid-tori of size m × n with graph T (n, m) = (V (n, m), E (n, m)), E = E 1 ∪E 2 . Then #SAT (F ) = T n (T n−1 T n−2 . . . T 0 ),

where T k is the transfer matrix of the two consecutive cycles of T (n, m): k and k + 1 of G n,m , k = 0, ..., n − 1 and T n is the transfer matrix of the cycle 0 and n.

Example 4. Let F 1 = F ∪ {(x 0 ∨ x 2 ), (¬y 0 , y 2 ), (¬z 0 , ¬z 2 )}, where F is like in example 2 (see figure 7). We compute the transfer matrix T 2 from the cycle x 0 y 0 z 0 to the cycle x 2 y 2 z 2 as follows. We have

F +±∓ 2 = {u 1 , u 2 , u 3 } and F ∓±+ 2 = {w 1 , w 2 , w 3 },

where the vectors u i s and w j s are as the example 3, only that now τ 0 = τ 0 0 τ 0 1 τ 0 2 = + − − and τ 3 = τ 3 0 τ 3 1 τ 3 2 = + + −. The transfer matrix T 2 is obtained by the evaluation of ϕ τ 3 (w i ) • ϕ τ 0 (u j ) for 1 ≤ i ≤ 3 and 1 ≤ j ≤ 3. Then

T 2 =   0 1 1 1 1 1 1 1 1  

In example 2, T 0 , T 1 and T 1 T 0 are computed, therefore Proof (Theorem 4). Using the theorem 3, the proof is similar to the proof of theorem 2 taking F n,m as a grid cylinder formula and R n = C 0 ∧ C n ∧ E, where C 0 and C n corresponding to the first cycle and n-th cycle of C(n, m) respectively (C(n, m) is the grid cylinder associated to F n,m ). The formula E is formed by new clauses corresponding to edges from the vertices of the first cycle to the vertices of n-th cycle of C(n, m).

T 2 (T 1 T 0 ) =   0 1 1 1 1 1 1 1 1    2

Conclusion

We have presented an extension of the transfer matrix method that allows to consider signed edges on grid graphs, grid-cylinders and grid-tori. We argued about the advantage of this extension in the problem of counting assignments of Boolean formulas in 2-CN F .

We have designed a procedure for computing #2SAT(F ) where F is a grid, grid-cylinder or grid-tori Boolean formula, based on the sum of all entries of the product matrix of the transfer matrix of each two consecutive columns for the case of a grid. In a grid cylinder we have two result for computing #2SAT(F ) one uses the sum of the entries of the Hadamard product between the transfer matrix of the first column (row) and the top column (row) with the product matrix of the transfer matrix of each two consecutive columns (row). The second result uses the sum of all entries of the product matrix of the transfer matrix of each two consecutive cycles. Finally, if F is a grid tori, we use the sum of the entries of the Hadamard product between the transfer matrix of the first cycle and the top cycle of tori with the product matrix of the transfer matrix of each two consecutive cycles of the tori.

A work in progress is the detailed determination of the complexity of the proposed extension. However, based on previous works in the transfer matrix method and our preliminary experiments, the complexity remains polynomial as long as the starting grid graphs are of fixed height, we consider the complexity with a fixed-parameter.