/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


YES
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


Outermost Termination of the given OTRS could be proven:

(0) OTRS
(1) Raffelsieper-Zantema-Transformation [SOUND, 0 ms]
(2) QTRS
(3) QTRSRRRProof [EQUIVALENT, 100 ms]
(4) QTRS
(5) QTRSRRRProof [EQUIVALENT, 65 ms]
(6) QTRS
(7) QTRSRRRProof [EQUIVALENT, 35 ms]
(8) QTRS
(9) QTRSRRRProof [EQUIVALENT, 30 ms]
(10) QTRS
(11) QTRSRRRProof [EQUIVALENT, 13 ms]
(12) QTRS
(13) QTRSRRRProof [EQUIVALENT, 0 ms]
(14) QTRS
(15) QTRSRRRProof [EQUIVALENT, 27 ms]
(16) QTRS
(17) DependencyPairsProof [EQUIVALENT, 5 ms]
(18) QDP
(19) DependencyGraphProof [EQUIVALENT, 0 ms]
(20) AND
    (21) QDP
        (22) UsableRulesProof [EQUIVALENT, 0 ms]
        (23) QDP
        (24) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (25) YES
    (26) QDP
        (27) UsableRulesProof [EQUIVALENT, 0 ms]
        (28) QDP
        (29) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (30) YES
    (31) QDP
        (32) UsableRulesProof [EQUIVALENT, 0 ms]
        (33) QDP
        (34) TransformationProof [EQUIVALENT, 0 ms]
        (35) QDP
        (36) DependencyGraphProof [EQUIVALENT, 0 ms]
        (37) QDP
        (38) QDPOrderProof [EQUIVALENT, 28 ms]
        (39) QDP
        (40) DependencyGraphProof [EQUIVALENT, 0 ms]
        (41) QDP
        (42) QDPOrderProof [EQUIVALENT, 20 ms]
        (43) QDP
        (44) QDPOrderProof [EQUIVALENT, 12 ms]
        (45) QDP
        (46) QDPOrderProof [EQUIVALENT, 2018 ms]
        (47) QDP
        (48) PisEmptyProof [EQUIVALENT, 0 ms]
        (49) YES


----------------------------------------

(0)
Obligation:
Term rewrite system R:
The TRS R consists of the following rules:

   a__zeros -> cons(0, zeros)
   a__and(tt, X) -> mark(X)
   a__length(nil) -> 0
   a__length(cons(N, L)) -> s(a__length(mark(L)))
   mark(zeros) -> a__zeros
   mark(and(X1, X2)) -> a__and(mark(X1), X2)
   mark(length(X)) -> a__length(mark(X))
   mark(cons(X1, X2)) -> cons(mark(X1), X2)
   mark(0) -> 0
   mark(tt) -> tt
   mark(nil) -> nil
   mark(s(X)) -> s(mark(X))
   a__zeros -> zeros
   a__and(X1, X2) -> and(X1, X2)
   a__length(X) -> length(X)



Outermost Strategy.

----------------------------------------

(1) Raffelsieper-Zantema-Transformation (SOUND)
We applied the Raffelsieper-Zantema transformation  to transform the outermost TRS to a standard TRS.
----------------------------------------

(2)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__and(tt, X)) -> up(mark(X))
   down(a__length(nil)) -> up(0)
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(and(X1, X2))) -> up(a__and(mark(X1), X2))
   down(mark(length(X))) -> up(a__length(mark(X)))
   down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2))
   down(mark(0)) -> up(0)
   down(mark(tt)) -> up(tt)
   down(mark(nil)) -> up(nil)
   down(mark(s(X))) -> up(s(mark(X)))
   down(a__zeros) -> up(zeros)
   down(a__and(X1, X2)) -> up(and(X1, X2))
   down(a__length(X)) -> up(length(X))
   top(up(x)) -> top(down(x))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   a__and_flat(up(x_1), block(x_2)) -> up(a__and(x_1, x_2))
   a__and_flat(block(x_1), up(x_2)) -> up(a__and(x_1, x_2))
   mark_flat(up(x_1)) -> up(mark(x_1))
   a__length_flat(up(x_1)) -> up(a__length(x_1))
   s_flat(up(x_1)) -> up(s(x_1))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   length_flat(up(x_1)) -> up(length(x_1))

Q is empty.

----------------------------------------

(3) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(a__and(x_1, x_2)) = 2*x_1 + 2*x_2
   POL(a__and_flat(x_1, x_2)) = 1 + 2*x_1 + 2*x_2
   POL(a__length(x_1)) = 2*x_1
   POL(a__length_flat(x_1)) = 1 + 2*x_1
   POL(a__zeros) = 0
   POL(and(x_1, x_2)) = 2*x_1 + x_2
   POL(and_flat(x_1, x_2)) = 2*x_1 + x_2
   POL(block(x_1)) = x_1
   POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2
   POL(cons_flat(x_1, x_2)) = 2*x_1 + 2*x_2
   POL(down(x_1)) = x_1
   POL(fresh_constant) = 0
   POL(length(x_1)) = 2*x_1
   POL(length_flat(x_1)) = 2*x_1
   POL(mark(x_1)) = 2*x_1
   POL(mark_flat(x_1)) = 2*x_1
   POL(nil) = 1
   POL(s(x_1)) = x_1
   POL(s_flat(x_1)) = x_1
   POL(top(x_1)) = x_1
   POL(tt) = 1
   POL(up(x_1)) = x_1
   POL(zeros) = 0
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   down(a__and(tt, X)) -> up(mark(X))
   down(a__length(nil)) -> up(0)
   down(mark(tt)) -> up(tt)
   down(mark(nil)) -> up(nil)
   a__and_flat(up(x_1), block(x_2)) -> up(a__and(x_1, x_2))
   a__and_flat(block(x_1), up(x_2)) -> up(a__and(x_1, x_2))
   a__length_flat(up(x_1)) -> up(a__length(x_1))




----------------------------------------

(4)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(and(X1, X2))) -> up(a__and(mark(X1), X2))
   down(mark(length(X))) -> up(a__length(mark(X)))
   down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2))
   down(mark(0)) -> up(0)
   down(mark(s(X))) -> up(s(mark(X)))
   down(a__zeros) -> up(zeros)
   down(a__and(X1, X2)) -> up(and(X1, X2))
   down(a__length(X)) -> up(length(X))
   top(up(x)) -> top(down(x))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   mark_flat(up(x_1)) -> up(mark(x_1))
   s_flat(up(x_1)) -> up(s(x_1))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   length_flat(up(x_1)) -> up(length(x_1))

Q is empty.

----------------------------------------

(5) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(a__and(x_1, x_2)) = x_1 + 2*x_2
   POL(a__length(x_1)) = 2*x_1
   POL(a__zeros) = 2
   POL(and(x_1, x_2)) = x_1 + 2*x_2
   POL(and_flat(x_1, x_2)) = x_1 + 2*x_2
   POL(block(x_1)) = 2*x_1
   POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2
   POL(cons_flat(x_1, x_2)) = 2*x_1 + 2*x_2
   POL(down(x_1)) = 2*x_1
   POL(fresh_constant) = 0
   POL(length(x_1)) = 2*x_1
   POL(length_flat(x_1)) = 2*x_1
   POL(mark(x_1)) = 2*x_1
   POL(mark_flat(x_1)) = 2*x_1
   POL(s(x_1)) = x_1
   POL(s_flat(x_1)) = x_1
   POL(top(x_1)) = 2*x_1
   POL(up(x_1)) = 2*x_1
   POL(zeros) = 1
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   down(a__zeros) -> up(zeros)




----------------------------------------

(6)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(and(X1, X2))) -> up(a__and(mark(X1), X2))
   down(mark(length(X))) -> up(a__length(mark(X)))
   down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2))
   down(mark(0)) -> up(0)
   down(mark(s(X))) -> up(s(mark(X)))
   down(a__and(X1, X2)) -> up(and(X1, X2))
   down(a__length(X)) -> up(length(X))
   top(up(x)) -> top(down(x))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   mark_flat(up(x_1)) -> up(mark(x_1))
   s_flat(up(x_1)) -> up(s(x_1))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   length_flat(up(x_1)) -> up(length(x_1))

Q is empty.

----------------------------------------

(7) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(a__and(x_1, x_2)) = 2 + 2*x_1 + 2*x_2
   POL(a__length(x_1)) = 1 + x_1
   POL(a__zeros) = 0
   POL(and(x_1, x_2)) = 1 + 2*x_1 + x_2
   POL(and_flat(x_1, x_2)) = 2 + 2*x_1 + x_2
   POL(block(x_1)) = 2*x_1
   POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2
   POL(cons_flat(x_1, x_2)) = 2*x_1 + 2*x_2
   POL(down(x_1)) = 2*x_1
   POL(fresh_constant) = 0
   POL(length(x_1)) = 1 + x_1
   POL(length_flat(x_1)) = 2 + x_1
   POL(mark(x_1)) = 2*x_1
   POL(mark_flat(x_1)) = 2*x_1
   POL(s(x_1)) = x_1
   POL(s_flat(x_1)) = x_1
   POL(top(x_1)) = 2*x_1
   POL(up(x_1)) = 2*x_1
   POL(zeros) = 0
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   down(mark(length(X))) -> up(a__length(mark(X)))
   down(a__and(X1, X2)) -> up(and(X1, X2))




----------------------------------------

(8)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(and(X1, X2))) -> up(a__and(mark(X1), X2))
   down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2))
   down(mark(0)) -> up(0)
   down(mark(s(X))) -> up(s(mark(X)))
   down(a__length(X)) -> up(length(X))
   top(up(x)) -> top(down(x))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   mark_flat(up(x_1)) -> up(mark(x_1))
   s_flat(up(x_1)) -> up(s(x_1))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   length_flat(up(x_1)) -> up(length(x_1))

Q is empty.

----------------------------------------

(9) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(a__and(x_1, x_2)) = x_1 + x_2
   POL(a__length(x_1)) = 2*x_1
   POL(a__zeros) = 0
   POL(and(x_1, x_2)) = 1 + x_1 + x_2
   POL(and_flat(x_1, x_2)) = 2 + x_1 + x_2
   POL(block(x_1)) = 2*x_1
   POL(cons(x_1, x_2)) = 2*x_1 + x_2
   POL(cons_flat(x_1, x_2)) = 2*x_1 + x_2
   POL(down(x_1)) = 2*x_1
   POL(fresh_constant) = 0
   POL(length(x_1)) = x_1
   POL(length_flat(x_1)) = x_1
   POL(mark(x_1)) = x_1
   POL(mark_flat(x_1)) = x_1
   POL(s(x_1)) = x_1
   POL(s_flat(x_1)) = x_1
   POL(top(x_1)) = x_1
   POL(up(x_1)) = 2*x_1
   POL(zeros) = 0
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   down(mark(and(X1, X2))) -> up(a__and(mark(X1), X2))




----------------------------------------

(10)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2))
   down(mark(0)) -> up(0)
   down(mark(s(X))) -> up(s(mark(X)))
   down(a__length(X)) -> up(length(X))
   top(up(x)) -> top(down(x))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   mark_flat(up(x_1)) -> up(mark(x_1))
   s_flat(up(x_1)) -> up(s(x_1))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   length_flat(up(x_1)) -> up(length(x_1))

Q is empty.

----------------------------------------

(11) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(a__and(x_1, x_2)) = x_1 + x_2
   POL(a__length(x_1)) = 1 + x_1
   POL(a__zeros) = 0
   POL(and(x_1, x_2)) = 2*x_1 + 2*x_2
   POL(and_flat(x_1, x_2)) = 2*x_1 + 2*x_2
   POL(block(x_1)) = 2*x_1
   POL(cons(x_1, x_2)) = 2*x_1 + x_2
   POL(cons_flat(x_1, x_2)) = 2*x_1 + x_2
   POL(down(x_1)) = 2*x_1
   POL(fresh_constant) = 0
   POL(length(x_1)) = x_1
   POL(length_flat(x_1)) = x_1
   POL(mark(x_1)) = x_1
   POL(mark_flat(x_1)) = x_1
   POL(s(x_1)) = x_1
   POL(s_flat(x_1)) = x_1
   POL(top(x_1)) = 2*x_1
   POL(up(x_1)) = 2*x_1
   POL(zeros) = 0
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   down(a__length(X)) -> up(length(X))




----------------------------------------

(12)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2))
   down(mark(0)) -> up(0)
   down(mark(s(X))) -> up(s(mark(X)))
   top(up(x)) -> top(down(x))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   mark_flat(up(x_1)) -> up(mark(x_1))
   s_flat(up(x_1)) -> up(s(x_1))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   length_flat(up(x_1)) -> up(length(x_1))

Q is empty.

----------------------------------------

(13) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(a__and(x_1, x_2)) = 1 + 2*x_1 + 2*x_2
   POL(a__length(x_1)) = x_1
   POL(a__zeros) = 1
   POL(and(x_1, x_2)) = 2*x_1 + 2*x_2
   POL(and_flat(x_1, x_2)) = 2*x_1 + 2*x_2
   POL(block(x_1)) = 2*x_1
   POL(cons(x_1, x_2)) = 1 + x_1 + x_2
   POL(cons_flat(x_1, x_2)) = 2 + x_1 + x_2
   POL(down(x_1)) = 2*x_1
   POL(fresh_constant) = 0
   POL(length(x_1)) = x_1
   POL(length_flat(x_1)) = x_1
   POL(mark(x_1)) = 1 + x_1
   POL(mark_flat(x_1)) = 2 + x_1
   POL(s(x_1)) = x_1
   POL(s_flat(x_1)) = x_1
   POL(top(x_1)) = 2*x_1
   POL(up(x_1)) = 2*x_1
   POL(zeros) = 0
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   down(mark(0)) -> up(0)




----------------------------------------

(14)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2))
   down(mark(s(X))) -> up(s(mark(X)))
   top(up(x)) -> top(down(x))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   mark_flat(up(x_1)) -> up(mark(x_1))
   s_flat(up(x_1)) -> up(s(x_1))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   length_flat(up(x_1)) -> up(length(x_1))

Q is empty.

----------------------------------------

(15) QTRSRRRProof (EQUIVALENT)
Used ordering:
Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(a__and(x_1, x_2)) = x_1 + 2*x_2
   POL(a__length(x_1)) = x_1
   POL(a__zeros) = 1
   POL(and(x_1, x_2)) = 2*x_1 + x_2
   POL(and_flat(x_1, x_2)) = 2*x_1 + x_2
   POL(block(x_1)) = 2*x_1
   POL(cons(x_1, x_2)) = 1 + x_1 + 2*x_2
   POL(cons_flat(x_1, x_2)) = 2 + x_1 + 2*x_2
   POL(down(x_1)) = 2*x_1
   POL(fresh_constant) = 0
   POL(length(x_1)) = 2*x_1
   POL(length_flat(x_1)) = 2*x_1
   POL(mark(x_1)) = 1 + 2*x_1
   POL(mark_flat(x_1)) = 2 + 2*x_1
   POL(s(x_1)) = x_1
   POL(s_flat(x_1)) = x_1
   POL(top(x_1)) = 2*x_1
   POL(up(x_1)) = 2*x_1
   POL(zeros) = 0
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

   down(mark(cons(X1, X2))) -> up(cons(mark(X1), X2))




----------------------------------------

(16)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(s(X))) -> up(s(mark(X)))
   top(up(x)) -> top(down(x))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   mark_flat(up(x_1)) -> up(mark(x_1))
   s_flat(up(x_1)) -> up(s(x_1))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   length_flat(up(x_1)) -> up(length(x_1))

Q is empty.

----------------------------------------

(17) DependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
----------------------------------------

(18)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   TOP(up(x)) -> TOP(down(x))
   TOP(up(x)) -> DOWN(x)
   DOWN(cons(y0, y1)) -> CONS_FLAT(down(y0), block(y1))
   DOWN(cons(y0, y1)) -> DOWN(y0)
   DOWN(cons(y0, y1)) -> CONS_FLAT(block(y0), down(y1))
   DOWN(cons(y0, y1)) -> DOWN(y1)
   DOWN(s(y6)) -> S_FLAT(down(y6))
   DOWN(s(y6)) -> DOWN(y6)
   DOWN(and(y7, y8)) -> AND_FLAT(down(y7), block(y8))
   DOWN(and(y7, y8)) -> DOWN(y7)
   DOWN(and(y7, y8)) -> AND_FLAT(block(y7), down(y8))
   DOWN(and(y7, y8)) -> DOWN(y8)
   DOWN(length(y9)) -> LENGTH_FLAT(down(y9))
   DOWN(length(y9)) -> DOWN(y9)
   DOWN(mark(a__zeros)) -> MARK_FLAT(down(a__zeros))
   DOWN(mark(a__zeros)) -> DOWN(a__zeros)
   DOWN(mark(a__and(y13, y14))) -> MARK_FLAT(down(a__and(y13, y14)))
   DOWN(mark(a__and(y13, y14))) -> DOWN(a__and(y13, y14))
   DOWN(mark(mark(y15))) -> MARK_FLAT(down(mark(y15)))
   DOWN(mark(mark(y15))) -> DOWN(mark(y15))
   DOWN(mark(a__length(y16))) -> MARK_FLAT(down(a__length(y16)))
   DOWN(mark(a__length(y16))) -> DOWN(a__length(y16))
   DOWN(mark(fresh_constant)) -> MARK_FLAT(down(fresh_constant))
   DOWN(mark(fresh_constant)) -> DOWN(fresh_constant)

The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(s(X))) -> up(s(mark(X)))
   top(up(x)) -> top(down(x))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   mark_flat(up(x_1)) -> up(mark(x_1))
   s_flat(up(x_1)) -> up(s(x_1))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   length_flat(up(x_1)) -> up(length(x_1))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(19) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 16 less nodes.
----------------------------------------

(20)
Complex Obligation (AND)

----------------------------------------

(21)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   DOWN(mark(mark(y15))) -> DOWN(mark(y15))

The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(s(X))) -> up(s(mark(X)))
   top(up(x)) -> top(down(x))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   mark_flat(up(x_1)) -> up(mark(x_1))
   s_flat(up(x_1)) -> up(s(x_1))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   length_flat(up(x_1)) -> up(length(x_1))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(22) UsableRulesProof (EQUIVALENT)
We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(23)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   DOWN(mark(mark(y15))) -> DOWN(mark(y15))

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(24) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*DOWN(mark(mark(y15))) -> DOWN(mark(y15))
The graph contains the following edges 1 > 1


----------------------------------------

(25)
YES

----------------------------------------

(26)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   DOWN(cons(y0, y1)) -> DOWN(y1)
   DOWN(cons(y0, y1)) -> DOWN(y0)
   DOWN(s(y6)) -> DOWN(y6)
   DOWN(and(y7, y8)) -> DOWN(y7)
   DOWN(and(y7, y8)) -> DOWN(y8)
   DOWN(length(y9)) -> DOWN(y9)

The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(s(X))) -> up(s(mark(X)))
   top(up(x)) -> top(down(x))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   mark_flat(up(x_1)) -> up(mark(x_1))
   s_flat(up(x_1)) -> up(s(x_1))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   length_flat(up(x_1)) -> up(length(x_1))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(27) UsableRulesProof (EQUIVALENT)
We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(28)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   DOWN(cons(y0, y1)) -> DOWN(y1)
   DOWN(cons(y0, y1)) -> DOWN(y0)
   DOWN(s(y6)) -> DOWN(y6)
   DOWN(and(y7, y8)) -> DOWN(y7)
   DOWN(and(y7, y8)) -> DOWN(y8)
   DOWN(length(y9)) -> DOWN(y9)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(29) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*DOWN(cons(y0, y1)) -> DOWN(y1)
The graph contains the following edges 1 > 1


*DOWN(cons(y0, y1)) -> DOWN(y0)
The graph contains the following edges 1 > 1


*DOWN(s(y6)) -> DOWN(y6)
The graph contains the following edges 1 > 1


*DOWN(and(y7, y8)) -> DOWN(y7)
The graph contains the following edges 1 > 1


*DOWN(and(y7, y8)) -> DOWN(y8)
The graph contains the following edges 1 > 1


*DOWN(length(y9)) -> DOWN(y9)
The graph contains the following edges 1 > 1


----------------------------------------

(30)
YES

----------------------------------------

(31)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   TOP(up(x)) -> TOP(down(x))

The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(s(X))) -> up(s(mark(X)))
   top(up(x)) -> top(down(x))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   mark_flat(up(x_1)) -> up(mark(x_1))
   s_flat(up(x_1)) -> up(s(x_1))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   length_flat(up(x_1)) -> up(length(x_1))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(32) UsableRulesProof (EQUIVALENT)
We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(33)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   TOP(up(x)) -> TOP(down(x))

The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(s(X))) -> up(s(mark(X)))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   mark_flat(up(x_1)) -> up(mark(x_1))
   length_flat(up(x_1)) -> up(length(x_1))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   s_flat(up(x_1)) -> up(s(x_1))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(34) TransformationProof (EQUIVALENT)
By narrowing [LPAR04] the rule TOP(up(x)) -> TOP(down(x)) at position [0] we obtained the following new rules [LPAR04]:

   (TOP(up(a__zeros)) -> TOP(up(cons(0, zeros))),TOP(up(a__zeros)) -> TOP(up(cons(0, zeros))))
   (TOP(up(a__length(cons(x0, x1)))) -> TOP(up(s(a__length(mark(x1))))),TOP(up(a__length(cons(x0, x1)))) -> TOP(up(s(a__length(mark(x1))))))
   (TOP(up(mark(zeros))) -> TOP(up(a__zeros)),TOP(up(mark(zeros))) -> TOP(up(a__zeros)))
   (TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0)))),TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0)))))
   (TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))),TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1))))
   (TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))),TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1))))
   (TOP(up(s(x0))) -> TOP(s_flat(down(x0))),TOP(up(s(x0))) -> TOP(s_flat(down(x0))))
   (TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1))),TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1))))
   (TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1))),TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1))))
   (TOP(up(length(x0))) -> TOP(length_flat(down(x0))),TOP(up(length(x0))) -> TOP(length_flat(down(x0))))
   (TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))),TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros))))
   (TOP(up(mark(a__and(x0, x1)))) -> TOP(mark_flat(down(a__and(x0, x1)))),TOP(up(mark(a__and(x0, x1)))) -> TOP(mark_flat(down(a__and(x0, x1)))))
   (TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))),TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0)))))
   (TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))),TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0)))))
   (TOP(up(mark(fresh_constant))) -> TOP(mark_flat(down(fresh_constant))),TOP(up(mark(fresh_constant))) -> TOP(mark_flat(down(fresh_constant))))


----------------------------------------

(35)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   TOP(up(a__zeros)) -> TOP(up(cons(0, zeros)))
   TOP(up(a__length(cons(x0, x1)))) -> TOP(up(s(a__length(mark(x1)))))
   TOP(up(mark(zeros))) -> TOP(up(a__zeros))
   TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0))))
   TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1)))
   TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1)))
   TOP(up(s(x0))) -> TOP(s_flat(down(x0)))
   TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1)))
   TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1)))
   TOP(up(length(x0))) -> TOP(length_flat(down(x0)))
   TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros)))
   TOP(up(mark(a__and(x0, x1)))) -> TOP(mark_flat(down(a__and(x0, x1))))
   TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0))))
   TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0))))
   TOP(up(mark(fresh_constant))) -> TOP(mark_flat(down(fresh_constant)))

The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(s(X))) -> up(s(mark(X)))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   mark_flat(up(x_1)) -> up(mark(x_1))
   length_flat(up(x_1)) -> up(length(x_1))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   s_flat(up(x_1)) -> up(s(x_1))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(36) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes.
----------------------------------------

(37)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1)))
   TOP(up(a__zeros)) -> TOP(up(cons(0, zeros)))
   TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1)))
   TOP(up(mark(zeros))) -> TOP(up(a__zeros))
   TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0))))
   TOP(up(s(x0))) -> TOP(s_flat(down(x0)))
   TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1)))
   TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1)))
   TOP(up(length(x0))) -> TOP(length_flat(down(x0)))
   TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros)))
   TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0))))
   TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0))))

The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(s(X))) -> up(s(mark(X)))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   mark_flat(up(x_1)) -> up(mark(x_1))
   length_flat(up(x_1)) -> up(length(x_1))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   s_flat(up(x_1)) -> up(s(x_1))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(38) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   TOP(up(a__zeros)) -> TOP(up(cons(0, zeros)))
   TOP(up(mark(s(x0)))) -> TOP(up(s(mark(x0))))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(TOP(x_1)) = x_1
   POL(a__and(x_1, x_2)) = x_1 + x_2
   POL(a__length(x_1)) = 0
   POL(a__zeros) = 1
   POL(and(x_1, x_2)) = 0
   POL(and_flat(x_1, x_2)) = 0
   POL(block(x_1)) = 0
   POL(cons(x_1, x_2)) = 0
   POL(cons_flat(x_1, x_2)) = 0
   POL(down(x_1)) = 0
   POL(fresh_constant) = 0
   POL(length(x_1)) = 0
   POL(length_flat(x_1)) = 0
   POL(mark(x_1)) = 1
   POL(mark_flat(x_1)) = 1
   POL(s(x_1)) = 0
   POL(s_flat(x_1)) = 0
   POL(up(x_1)) = x_1
   POL(zeros) = 0

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   s_flat(up(x_1)) -> up(s(x_1))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   length_flat(up(x_1)) -> up(length(x_1))
   mark_flat(up(x_1)) -> up(mark(x_1))


----------------------------------------

(39)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1)))
   TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1)))
   TOP(up(mark(zeros))) -> TOP(up(a__zeros))
   TOP(up(s(x0))) -> TOP(s_flat(down(x0)))
   TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1)))
   TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1)))
   TOP(up(length(x0))) -> TOP(length_flat(down(x0)))
   TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros)))
   TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0))))
   TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0))))

The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(s(X))) -> up(s(mark(X)))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   mark_flat(up(x_1)) -> up(mark(x_1))
   length_flat(up(x_1)) -> up(length(x_1))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   s_flat(up(x_1)) -> up(s(x_1))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(40) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
----------------------------------------

(41)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1)))
   TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1)))
   TOP(up(s(x0))) -> TOP(s_flat(down(x0)))
   TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1)))
   TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1)))
   TOP(up(length(x0))) -> TOP(length_flat(down(x0)))
   TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros)))
   TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0))))
   TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0))))

The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(s(X))) -> up(s(mark(X)))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   mark_flat(up(x_1)) -> up(mark(x_1))
   length_flat(up(x_1)) -> up(length(x_1))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   s_flat(up(x_1)) -> up(s(x_1))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(42) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   TOP(up(mark(a__length(x0)))) -> TOP(mark_flat(down(a__length(x0))))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(0) = 1
   POL(TOP(x_1)) = x_1
   POL(a__and(x_1, x_2)) = x_1 + x_2
   POL(a__length(x_1)) = 1
   POL(a__zeros) = 0
   POL(and(x_1, x_2)) = 0
   POL(and_flat(x_1, x_2)) = 0
   POL(block(x_1)) = 0
   POL(cons(x_1, x_2)) = 0
   POL(cons_flat(x_1, x_2)) = 0
   POL(down(x_1)) = 0
   POL(fresh_constant) = 0
   POL(length(x_1)) = 0
   POL(length_flat(x_1)) = 0
   POL(mark(x_1)) = x_1
   POL(mark_flat(x_1)) = x_1
   POL(s(x_1)) = 0
   POL(s_flat(x_1)) = 0
   POL(up(x_1)) = x_1
   POL(zeros) = 0

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(s(X))) -> up(s(mark(X)))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   s_flat(up(x_1)) -> up(s(x_1))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   length_flat(up(x_1)) -> up(length(x_1))
   mark_flat(up(x_1)) -> up(mark(x_1))


----------------------------------------

(43)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1)))
   TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1)))
   TOP(up(s(x0))) -> TOP(s_flat(down(x0)))
   TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1)))
   TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1)))
   TOP(up(length(x0))) -> TOP(length_flat(down(x0)))
   TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros)))
   TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0))))

The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(s(X))) -> up(s(mark(X)))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   mark_flat(up(x_1)) -> up(mark(x_1))
   length_flat(up(x_1)) -> up(length(x_1))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   s_flat(up(x_1)) -> up(s(x_1))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(44) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   TOP(up(mark(a__zeros))) -> TOP(mark_flat(down(a__zeros)))
   TOP(up(mark(mark(x0)))) -> TOP(mark_flat(down(mark(x0))))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(0) = 1
   POL(TOP(x_1)) = x_1
   POL(a__and(x_1, x_2)) = x_1 + x_2
   POL(a__length(x_1)) = 1
   POL(a__zeros) = 1
   POL(and(x_1, x_2)) = 0
   POL(and_flat(x_1, x_2)) = 1
   POL(block(x_1)) = 0
   POL(cons(x_1, x_2)) = 0
   POL(cons_flat(x_1, x_2)) = 1
   POL(down(x_1)) = x_1
   POL(fresh_constant) = 0
   POL(length(x_1)) = 0
   POL(length_flat(x_1)) = 1
   POL(mark(x_1)) = 1 + x_1
   POL(mark_flat(x_1)) = 1 + x_1
   POL(s(x_1)) = 0
   POL(s_flat(x_1)) = 1
   POL(up(x_1)) = 1 + x_1
   POL(zeros) = 1

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(s(X))) -> up(s(mark(X)))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   s_flat(up(x_1)) -> up(s(x_1))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   length_flat(up(x_1)) -> up(length(x_1))
   mark_flat(up(x_1)) -> up(mark(x_1))


----------------------------------------

(45)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1)))
   TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1)))
   TOP(up(s(x0))) -> TOP(s_flat(down(x0)))
   TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1)))
   TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1)))
   TOP(up(length(x0))) -> TOP(length_flat(down(x0)))

The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(s(X))) -> up(s(mark(X)))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   mark_flat(up(x_1)) -> up(mark(x_1))
   length_flat(up(x_1)) -> up(length(x_1))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   s_flat(up(x_1)) -> up(s(x_1))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(46) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   TOP(up(cons(x0, x1))) -> TOP(cons_flat(down(x0), block(x1)))
   TOP(up(cons(x0, x1))) -> TOP(cons_flat(block(x0), down(x1)))
   TOP(up(s(x0))) -> TOP(s_flat(down(x0)))
   TOP(up(and(x0, x1))) -> TOP(and_flat(down(x0), block(x1)))
   TOP(up(and(x0, x1))) -> TOP(and_flat(block(x0), down(x1)))
   TOP(up(length(x0))) -> TOP(length_flat(down(x0)))
The remaining pairs can at least be oriented weakly.
Used ordering:  Matrix interpretation [MATRO]:

Non-tuple symbols: 
<<<
 M( s_flat_1(x_1) ) =  	[[0], [1]] 	+ 	[[0, 0], [0, 2]] 	* 	x_1
>>>

<<<
 M( block_1(x_1) ) =  	[[0], [0]] 	+ 	[[0, 0], [2, 0]] 	* 	x_1
>>>

<<<
 M( a__length_1(x_1) ) =  	[[0], [0]] 	+ 	[[0, 2], [0, 0]] 	* 	x_1
>>>

<<<
 M( cons_flat_2(x_1, x_2) ) =  	[[0], [0]] 	+ 	[[0, 0], [0, 2]] 	* 	x_1 	+ 	[[3, 0], [0, 1]] 	* 	x_2
>>>

<<<
 M( and_2(x_1, x_2) ) =  	[[2], [0]] 	+ 	[[3, 0], [0, 0]] 	* 	x_1 	+ 	[[3, 0], [0, 0]] 	* 	x_2
>>>

<<<
 M( s_1(x_1) ) =  	[[1], [0]] 	+ 	[[2, 0], [0, 0]] 	* 	x_1
>>>

<<<
 M( mark_flat_1(x_1) ) =  	[[0], [0]] 	+ 	[[0, 0], [0, 2]] 	* 	x_1
>>>

<<<
 M( a__zeros ) =  	[[3], [0]]
>>>

<<<
 M( and_flat_2(x_1, x_2) ) =  	[[0], [0]] 	+ 	[[0, 0], [0, 3]] 	* 	x_1 	+ 	[[0, 0], [0, 3]] 	* 	x_2
>>>

<<<
 M( length_1(x_1) ) =  	[[0], [0]] 	+ 	[[1, 0], [0, 0]] 	* 	x_1
>>>

<<<
 M( a__and_2(x_1, x_2) ) =  	[[0], [0]] 	+ 	[[0, 0], [0, 0]] 	* 	x_1 	+ 	[[0, 0], [0, 0]] 	* 	x_2
>>>

<<<
 M( down_1(x_1) ) =  	[[0], [0]] 	+ 	[[0, 0], [2, 0]] 	* 	x_1
>>>

<<<
 M( zeros ) =  	[[2], [0]]
>>>

<<<
 M( 0 ) =  	[[0], [0]]
>>>

<<<
 M( fresh_constant ) =  	[[0], [0]]
>>>

<<<
 M( up_1(x_1) ) =  	[[0], [2]] 	+ 	[[0, 0], [2, 0]] 	* 	x_1
>>>

<<<
 M( cons_2(x_1, x_2) ) =  	[[0], [1]] 	+ 	[[2, 0], [0, 0]] 	* 	x_1 	+ 	[[1, 0], [0, 0]] 	* 	x_2
>>>

<<<
 M( length_flat_1(x_1) ) =  	[[0], [0]] 	+ 	[[0, 0], [0, 1]] 	* 	x_1
>>>

<<<
 M( mark_1(x_1) ) =  	[[0], [0]] 	+ 	[[2, 0], [0, 0]] 	* 	x_1
>>>

Tuple symbols: 
<<<
 M( TOP_1(x_1) ) =  	[[0]] 	+ 	[[0, 2]] 	* 	x_1
>>>



Matrix type: 

We used a basic matrix type which is not further parametrizeable.





As matrix orders are CE-compatible, we used usable rules w.r.t. argument filtering in the order.
The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(s(X))) -> up(s(mark(X)))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   s_flat(up(x_1)) -> up(s(x_1))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   length_flat(up(x_1)) -> up(length(x_1))
   mark_flat(up(x_1)) -> up(mark(x_1))


----------------------------------------

(47)
Obligation:
Q DP problem:
P is empty.
The TRS R consists of the following rules:

   down(a__zeros) -> up(cons(0, zeros))
   down(a__length(cons(N, L))) -> up(s(a__length(mark(L))))
   down(mark(zeros)) -> up(a__zeros)
   down(mark(s(X))) -> up(s(mark(X)))
   down(cons(y0, y1)) -> cons_flat(down(y0), block(y1))
   down(cons(y0, y1)) -> cons_flat(block(y0), down(y1))
   down(s(y6)) -> s_flat(down(y6))
   down(and(y7, y8)) -> and_flat(down(y7), block(y8))
   down(and(y7, y8)) -> and_flat(block(y7), down(y8))
   down(length(y9)) -> length_flat(down(y9))
   down(mark(a__zeros)) -> mark_flat(down(a__zeros))
   down(mark(a__and(y13, y14))) -> mark_flat(down(a__and(y13, y14)))
   down(mark(mark(y15))) -> mark_flat(down(mark(y15)))
   down(mark(a__length(y16))) -> mark_flat(down(a__length(y16)))
   down(mark(fresh_constant)) -> mark_flat(down(fresh_constant))
   mark_flat(up(x_1)) -> up(mark(x_1))
   length_flat(up(x_1)) -> up(length(x_1))
   and_flat(block(x_1), up(x_2)) -> up(and(x_1, x_2))
   and_flat(up(x_1), block(x_2)) -> up(and(x_1, x_2))
   s_flat(up(x_1)) -> up(s(x_1))
   cons_flat(block(x_1), up(x_2)) -> up(cons(x_1, x_2))
   cons_flat(up(x_1), block(x_2)) -> up(cons(x_1, x_2))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(48) PisEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,Q,R) chain.
----------------------------------------

(49)
YES