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


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


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


Termination w.r.t. Q of the given QTRS could be proven:

(0) QTRS
(1) DependencyPairsProof [EQUIVALENT, 61 ms]
(2) QDP
(3) DependencyGraphProof [EQUIVALENT, 0 ms]
(4) AND
    (5) QDP
        (6) UsableRulesProof [EQUIVALENT, 0 ms]
        (7) QDP
        (8) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (9) YES
    (10) QDP
        (11) QDPOrderProof [EQUIVALENT, 579 ms]
        (12) QDP
        (13) DependencyGraphProof [EQUIVALENT, 0 ms]
        (14) QDP
        (15) QDPOrderProof [EQUIVALENT, 599 ms]
        (16) QDP
        (17) UsableRulesProof [EQUIVALENT, 0 ms]
        (18) QDP
        (19) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
        (20) QDP
        (21) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
        (22) QDP
        (23) PisEmptyProof [EQUIVALENT, 0 ms]
        (24) YES


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

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

   intersect'ii'in(cons(X, X0), cons(X, X1)) -> intersect'ii'out
   intersect'ii'in(Xs, cons(X0, Ys)) -> u'1'1(intersect'ii'in(Xs, Ys))
   u'1'1(intersect'ii'out) -> intersect'ii'out
   intersect'ii'in(cons(X0, Xs), Ys) -> u'2'1(intersect'ii'in(Xs, Ys))
   u'2'1(intersect'ii'out) -> intersect'ii'out
   reduce'ii'in(sequent(cons(if(A, B), Fs), Gs), NF) -> u'3'1(reduce'ii'in(sequent(cons(x'2b(x'2d(B), A), Fs), Gs), NF))
   u'3'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(iff(A, B), Fs), Gs), NF) -> u'4'1(reduce'ii'in(sequent(cons(x'2a(if(A, B), if(B, A)), Fs), Gs), NF))
   u'4'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2a(F1, F2), Fs), Gs), NF) -> u'5'1(reduce'ii'in(sequent(cons(F1, cons(F2, Fs)), Gs), NF))
   u'5'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2b(F1, F2), Fs), Gs), NF) -> u'6'1(reduce'ii'in(sequent(cons(F1, Fs), Gs), NF), F2, Fs, Gs, NF)
   u'6'1(reduce'ii'out, F2, Fs, Gs, NF) -> u'6'2(reduce'ii'in(sequent(cons(F2, Fs), Gs), NF))
   u'6'2(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2d(F1), Fs), Gs), NF) -> u'7'1(reduce'ii'in(sequent(Fs, cons(F1, Gs)), NF))
   u'7'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(if(A, B), Gs)), NF) -> u'8'1(reduce'ii'in(sequent(Fs, cons(x'2b(x'2d(B), A), Gs)), NF))
   u'8'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(iff(A, B), Gs)), NF) -> u'9'1(reduce'ii'in(sequent(Fs, cons(x'2a(if(A, B), if(B, A)), Gs)), NF))
   u'9'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(p(V), Fs), Gs), sequent(Left, Right)) -> u'10'1(reduce'ii'in(sequent(Fs, Gs), sequent(cons(p(V), Left), Right)))
   u'10'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2b(G1, G2), Gs)), NF) -> u'11'1(reduce'ii'in(sequent(Fs, cons(G1, cons(G2, Gs))), NF))
   u'11'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2a(G1, G2), Gs)), NF) -> u'12'1(reduce'ii'in(sequent(Fs, cons(G1, Gs)), NF), Fs, G2, Gs, NF)
   u'12'1(reduce'ii'out, Fs, G2, Gs, NF) -> u'12'2(reduce'ii'in(sequent(Fs, cons(G2, Gs)), NF))
   u'12'2(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2d(G1), Gs)), NF) -> u'13'1(reduce'ii'in(sequent(cons(G1, Fs), Gs), NF))
   u'13'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(nil, cons(p(V), Gs)), sequent(Left, Right)) -> u'14'1(reduce'ii'in(sequent(nil, Gs), sequent(Left, cons(p(V), Right))))
   u'14'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(nil, nil), sequent(F1, F2)) -> u'15'1(intersect'ii'in(F1, F2))
   u'15'1(intersect'ii'out) -> reduce'ii'out
   tautology'i'in(F) -> u'16'1(reduce'ii'in(sequent(nil, cons(F, nil)), sequent(nil, nil)))
   u'16'1(reduce'ii'out) -> tautology'i'out

Q is empty.

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

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

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

   INTERSECT'II'IN(Xs, cons(X0, Ys)) -> U'1'1(intersect'ii'in(Xs, Ys))
   INTERSECT'II'IN(Xs, cons(X0, Ys)) -> INTERSECT'II'IN(Xs, Ys)
   INTERSECT'II'IN(cons(X0, Xs), Ys) -> U'2'1(intersect'ii'in(Xs, Ys))
   INTERSECT'II'IN(cons(X0, Xs), Ys) -> INTERSECT'II'IN(Xs, Ys)
   REDUCE'II'IN(sequent(cons(if(A, B), Fs), Gs), NF) -> U'3'1(reduce'ii'in(sequent(cons(x'2b(x'2d(B), A), Fs), Gs), NF))
   REDUCE'II'IN(sequent(cons(if(A, B), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(x'2b(x'2d(B), A), Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(iff(A, B), Fs), Gs), NF) -> U'4'1(reduce'ii'in(sequent(cons(x'2a(if(A, B), if(B, A)), Fs), Gs), NF))
   REDUCE'II'IN(sequent(cons(iff(A, B), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(x'2a(if(A, B), if(B, A)), Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(x'2a(F1, F2), Fs), Gs), NF) -> U'5'1(reduce'ii'in(sequent(cons(F1, cons(F2, Fs)), Gs), NF))
   REDUCE'II'IN(sequent(cons(x'2a(F1, F2), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(F1, cons(F2, Fs)), Gs), NF)
   REDUCE'II'IN(sequent(cons(x'2b(F1, F2), Fs), Gs), NF) -> U'6'1(reduce'ii'in(sequent(cons(F1, Fs), Gs), NF), F2, Fs, Gs, NF)
   REDUCE'II'IN(sequent(cons(x'2b(F1, F2), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(F1, Fs), Gs), NF)
   U'6'1(reduce'ii'out, F2, Fs, Gs, NF) -> U'6'2(reduce'ii'in(sequent(cons(F2, Fs), Gs), NF))
   U'6'1(reduce'ii'out, F2, Fs, Gs, NF) -> REDUCE'II'IN(sequent(cons(F2, Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(x'2d(F1), Fs), Gs), NF) -> U'7'1(reduce'ii'in(sequent(Fs, cons(F1, Gs)), NF))
   REDUCE'II'IN(sequent(cons(x'2d(F1), Fs), Gs), NF) -> REDUCE'II'IN(sequent(Fs, cons(F1, Gs)), NF)
   REDUCE'II'IN(sequent(Fs, cons(if(A, B), Gs)), NF) -> U'8'1(reduce'ii'in(sequent(Fs, cons(x'2b(x'2d(B), A), Gs)), NF))
   REDUCE'II'IN(sequent(Fs, cons(if(A, B), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(x'2b(x'2d(B), A), Gs)), NF)
   REDUCE'II'IN(sequent(Fs, cons(iff(A, B), Gs)), NF) -> U'9'1(reduce'ii'in(sequent(Fs, cons(x'2a(if(A, B), if(B, A)), Gs)), NF))
   REDUCE'II'IN(sequent(Fs, cons(iff(A, B), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(x'2a(if(A, B), if(B, A)), Gs)), NF)
   REDUCE'II'IN(sequent(cons(p(V), Fs), Gs), sequent(Left, Right)) -> U'10'1(reduce'ii'in(sequent(Fs, Gs), sequent(cons(p(V), Left), Right)))
   REDUCE'II'IN(sequent(cons(p(V), Fs), Gs), sequent(Left, Right)) -> REDUCE'II'IN(sequent(Fs, Gs), sequent(cons(p(V), Left), Right))
   REDUCE'II'IN(sequent(Fs, cons(x'2b(G1, G2), Gs)), NF) -> U'11'1(reduce'ii'in(sequent(Fs, cons(G1, cons(G2, Gs))), NF))
   REDUCE'II'IN(sequent(Fs, cons(x'2b(G1, G2), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(G1, cons(G2, Gs))), NF)
   REDUCE'II'IN(sequent(Fs, cons(x'2a(G1, G2), Gs)), NF) -> U'12'1(reduce'ii'in(sequent(Fs, cons(G1, Gs)), NF), Fs, G2, Gs, NF)
   REDUCE'II'IN(sequent(Fs, cons(x'2a(G1, G2), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(G1, Gs)), NF)
   U'12'1(reduce'ii'out, Fs, G2, Gs, NF) -> U'12'2(reduce'ii'in(sequent(Fs, cons(G2, Gs)), NF))
   U'12'1(reduce'ii'out, Fs, G2, Gs, NF) -> REDUCE'II'IN(sequent(Fs, cons(G2, Gs)), NF)
   REDUCE'II'IN(sequent(Fs, cons(x'2d(G1), Gs)), NF) -> U'13'1(reduce'ii'in(sequent(cons(G1, Fs), Gs), NF))
   REDUCE'II'IN(sequent(Fs, cons(x'2d(G1), Gs)), NF) -> REDUCE'II'IN(sequent(cons(G1, Fs), Gs), NF)
   REDUCE'II'IN(sequent(nil, cons(p(V), Gs)), sequent(Left, Right)) -> U'14'1(reduce'ii'in(sequent(nil, Gs), sequent(Left, cons(p(V), Right))))
   REDUCE'II'IN(sequent(nil, cons(p(V), Gs)), sequent(Left, Right)) -> REDUCE'II'IN(sequent(nil, Gs), sequent(Left, cons(p(V), Right)))
   REDUCE'II'IN(sequent(nil, nil), sequent(F1, F2)) -> U'15'1(intersect'ii'in(F1, F2))
   REDUCE'II'IN(sequent(nil, nil), sequent(F1, F2)) -> INTERSECT'II'IN(F1, F2)
   TAUTOLOGY'I'IN(F) -> U'16'1(reduce'ii'in(sequent(nil, cons(F, nil)), sequent(nil, nil)))
   TAUTOLOGY'I'IN(F) -> REDUCE'II'IN(sequent(nil, cons(F, nil)), sequent(nil, nil))

The TRS R consists of the following rules:

   intersect'ii'in(cons(X, X0), cons(X, X1)) -> intersect'ii'out
   intersect'ii'in(Xs, cons(X0, Ys)) -> u'1'1(intersect'ii'in(Xs, Ys))
   u'1'1(intersect'ii'out) -> intersect'ii'out
   intersect'ii'in(cons(X0, Xs), Ys) -> u'2'1(intersect'ii'in(Xs, Ys))
   u'2'1(intersect'ii'out) -> intersect'ii'out
   reduce'ii'in(sequent(cons(if(A, B), Fs), Gs), NF) -> u'3'1(reduce'ii'in(sequent(cons(x'2b(x'2d(B), A), Fs), Gs), NF))
   u'3'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(iff(A, B), Fs), Gs), NF) -> u'4'1(reduce'ii'in(sequent(cons(x'2a(if(A, B), if(B, A)), Fs), Gs), NF))
   u'4'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2a(F1, F2), Fs), Gs), NF) -> u'5'1(reduce'ii'in(sequent(cons(F1, cons(F2, Fs)), Gs), NF))
   u'5'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2b(F1, F2), Fs), Gs), NF) -> u'6'1(reduce'ii'in(sequent(cons(F1, Fs), Gs), NF), F2, Fs, Gs, NF)
   u'6'1(reduce'ii'out, F2, Fs, Gs, NF) -> u'6'2(reduce'ii'in(sequent(cons(F2, Fs), Gs), NF))
   u'6'2(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2d(F1), Fs), Gs), NF) -> u'7'1(reduce'ii'in(sequent(Fs, cons(F1, Gs)), NF))
   u'7'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(if(A, B), Gs)), NF) -> u'8'1(reduce'ii'in(sequent(Fs, cons(x'2b(x'2d(B), A), Gs)), NF))
   u'8'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(iff(A, B), Gs)), NF) -> u'9'1(reduce'ii'in(sequent(Fs, cons(x'2a(if(A, B), if(B, A)), Gs)), NF))
   u'9'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(p(V), Fs), Gs), sequent(Left, Right)) -> u'10'1(reduce'ii'in(sequent(Fs, Gs), sequent(cons(p(V), Left), Right)))
   u'10'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2b(G1, G2), Gs)), NF) -> u'11'1(reduce'ii'in(sequent(Fs, cons(G1, cons(G2, Gs))), NF))
   u'11'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2a(G1, G2), Gs)), NF) -> u'12'1(reduce'ii'in(sequent(Fs, cons(G1, Gs)), NF), Fs, G2, Gs, NF)
   u'12'1(reduce'ii'out, Fs, G2, Gs, NF) -> u'12'2(reduce'ii'in(sequent(Fs, cons(G2, Gs)), NF))
   u'12'2(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2d(G1), Gs)), NF) -> u'13'1(reduce'ii'in(sequent(cons(G1, Fs), Gs), NF))
   u'13'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(nil, cons(p(V), Gs)), sequent(Left, Right)) -> u'14'1(reduce'ii'in(sequent(nil, Gs), sequent(Left, cons(p(V), Right))))
   u'14'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(nil, nil), sequent(F1, F2)) -> u'15'1(intersect'ii'in(F1, F2))
   u'15'1(intersect'ii'out) -> reduce'ii'out
   tautology'i'in(F) -> u'16'1(reduce'ii'in(sequent(nil, cons(F, nil)), sequent(nil, nil)))
   u'16'1(reduce'ii'out) -> tautology'i'out

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

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

(4)
Complex Obligation (AND)

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

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

   INTERSECT'II'IN(cons(X0, Xs), Ys) -> INTERSECT'II'IN(Xs, Ys)
   INTERSECT'II'IN(Xs, cons(X0, Ys)) -> INTERSECT'II'IN(Xs, Ys)

The TRS R consists of the following rules:

   intersect'ii'in(cons(X, X0), cons(X, X1)) -> intersect'ii'out
   intersect'ii'in(Xs, cons(X0, Ys)) -> u'1'1(intersect'ii'in(Xs, Ys))
   u'1'1(intersect'ii'out) -> intersect'ii'out
   intersect'ii'in(cons(X0, Xs), Ys) -> u'2'1(intersect'ii'in(Xs, Ys))
   u'2'1(intersect'ii'out) -> intersect'ii'out
   reduce'ii'in(sequent(cons(if(A, B), Fs), Gs), NF) -> u'3'1(reduce'ii'in(sequent(cons(x'2b(x'2d(B), A), Fs), Gs), NF))
   u'3'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(iff(A, B), Fs), Gs), NF) -> u'4'1(reduce'ii'in(sequent(cons(x'2a(if(A, B), if(B, A)), Fs), Gs), NF))
   u'4'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2a(F1, F2), Fs), Gs), NF) -> u'5'1(reduce'ii'in(sequent(cons(F1, cons(F2, Fs)), Gs), NF))
   u'5'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2b(F1, F2), Fs), Gs), NF) -> u'6'1(reduce'ii'in(sequent(cons(F1, Fs), Gs), NF), F2, Fs, Gs, NF)
   u'6'1(reduce'ii'out, F2, Fs, Gs, NF) -> u'6'2(reduce'ii'in(sequent(cons(F2, Fs), Gs), NF))
   u'6'2(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2d(F1), Fs), Gs), NF) -> u'7'1(reduce'ii'in(sequent(Fs, cons(F1, Gs)), NF))
   u'7'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(if(A, B), Gs)), NF) -> u'8'1(reduce'ii'in(sequent(Fs, cons(x'2b(x'2d(B), A), Gs)), NF))
   u'8'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(iff(A, B), Gs)), NF) -> u'9'1(reduce'ii'in(sequent(Fs, cons(x'2a(if(A, B), if(B, A)), Gs)), NF))
   u'9'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(p(V), Fs), Gs), sequent(Left, Right)) -> u'10'1(reduce'ii'in(sequent(Fs, Gs), sequent(cons(p(V), Left), Right)))
   u'10'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2b(G1, G2), Gs)), NF) -> u'11'1(reduce'ii'in(sequent(Fs, cons(G1, cons(G2, Gs))), NF))
   u'11'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2a(G1, G2), Gs)), NF) -> u'12'1(reduce'ii'in(sequent(Fs, cons(G1, Gs)), NF), Fs, G2, Gs, NF)
   u'12'1(reduce'ii'out, Fs, G2, Gs, NF) -> u'12'2(reduce'ii'in(sequent(Fs, cons(G2, Gs)), NF))
   u'12'2(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2d(G1), Gs)), NF) -> u'13'1(reduce'ii'in(sequent(cons(G1, Fs), Gs), NF))
   u'13'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(nil, cons(p(V), Gs)), sequent(Left, Right)) -> u'14'1(reduce'ii'in(sequent(nil, Gs), sequent(Left, cons(p(V), Right))))
   u'14'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(nil, nil), sequent(F1, F2)) -> u'15'1(intersect'ii'in(F1, F2))
   u'15'1(intersect'ii'out) -> reduce'ii'out
   tautology'i'in(F) -> u'16'1(reduce'ii'in(sequent(nil, cons(F, nil)), sequent(nil, nil)))
   u'16'1(reduce'ii'out) -> tautology'i'out

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

(6) 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.
----------------------------------------

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

   INTERSECT'II'IN(cons(X0, Xs), Ys) -> INTERSECT'II'IN(Xs, Ys)
   INTERSECT'II'IN(Xs, cons(X0, Ys)) -> INTERSECT'II'IN(Xs, Ys)

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

(8) 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:
*INTERSECT'II'IN(cons(X0, Xs), Ys) -> INTERSECT'II'IN(Xs, Ys)
The graph contains the following edges 1 > 1, 2 >= 2


*INTERSECT'II'IN(Xs, cons(X0, Ys)) -> INTERSECT'II'IN(Xs, Ys)
The graph contains the following edges 1 >= 1, 2 > 2


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

(9)
YES

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

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

   REDUCE'II'IN(sequent(cons(x'2b(F1, F2), Fs), Gs), NF) -> U'6'1(reduce'ii'in(sequent(cons(F1, Fs), Gs), NF), F2, Fs, Gs, NF)
   U'6'1(reduce'ii'out, F2, Fs, Gs, NF) -> REDUCE'II'IN(sequent(cons(F2, Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(if(A, B), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(x'2b(x'2d(B), A), Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(x'2b(F1, F2), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(F1, Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(iff(A, B), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(x'2a(if(A, B), if(B, A)), Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(x'2a(F1, F2), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(F1, cons(F2, Fs)), Gs), NF)
   REDUCE'II'IN(sequent(cons(x'2d(F1), Fs), Gs), NF) -> REDUCE'II'IN(sequent(Fs, cons(F1, Gs)), NF)
   REDUCE'II'IN(sequent(Fs, cons(if(A, B), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(x'2b(x'2d(B), A), Gs)), NF)
   REDUCE'II'IN(sequent(cons(p(V), Fs), Gs), sequent(Left, Right)) -> REDUCE'II'IN(sequent(Fs, Gs), sequent(cons(p(V), Left), Right))
   REDUCE'II'IN(sequent(Fs, cons(iff(A, B), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(x'2a(if(A, B), if(B, A)), Gs)), NF)
   REDUCE'II'IN(sequent(Fs, cons(x'2a(G1, G2), Gs)), NF) -> U'12'1(reduce'ii'in(sequent(Fs, cons(G1, Gs)), NF), Fs, G2, Gs, NF)
   U'12'1(reduce'ii'out, Fs, G2, Gs, NF) -> REDUCE'II'IN(sequent(Fs, cons(G2, Gs)), NF)
   REDUCE'II'IN(sequent(Fs, cons(x'2b(G1, G2), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(G1, cons(G2, Gs))), NF)
   REDUCE'II'IN(sequent(Fs, cons(x'2a(G1, G2), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(G1, Gs)), NF)
   REDUCE'II'IN(sequent(Fs, cons(x'2d(G1), Gs)), NF) -> REDUCE'II'IN(sequent(cons(G1, Fs), Gs), NF)
   REDUCE'II'IN(sequent(nil, cons(p(V), Gs)), sequent(Left, Right)) -> REDUCE'II'IN(sequent(nil, Gs), sequent(Left, cons(p(V), Right)))

The TRS R consists of the following rules:

   intersect'ii'in(cons(X, X0), cons(X, X1)) -> intersect'ii'out
   intersect'ii'in(Xs, cons(X0, Ys)) -> u'1'1(intersect'ii'in(Xs, Ys))
   u'1'1(intersect'ii'out) -> intersect'ii'out
   intersect'ii'in(cons(X0, Xs), Ys) -> u'2'1(intersect'ii'in(Xs, Ys))
   u'2'1(intersect'ii'out) -> intersect'ii'out
   reduce'ii'in(sequent(cons(if(A, B), Fs), Gs), NF) -> u'3'1(reduce'ii'in(sequent(cons(x'2b(x'2d(B), A), Fs), Gs), NF))
   u'3'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(iff(A, B), Fs), Gs), NF) -> u'4'1(reduce'ii'in(sequent(cons(x'2a(if(A, B), if(B, A)), Fs), Gs), NF))
   u'4'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2a(F1, F2), Fs), Gs), NF) -> u'5'1(reduce'ii'in(sequent(cons(F1, cons(F2, Fs)), Gs), NF))
   u'5'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2b(F1, F2), Fs), Gs), NF) -> u'6'1(reduce'ii'in(sequent(cons(F1, Fs), Gs), NF), F2, Fs, Gs, NF)
   u'6'1(reduce'ii'out, F2, Fs, Gs, NF) -> u'6'2(reduce'ii'in(sequent(cons(F2, Fs), Gs), NF))
   u'6'2(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2d(F1), Fs), Gs), NF) -> u'7'1(reduce'ii'in(sequent(Fs, cons(F1, Gs)), NF))
   u'7'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(if(A, B), Gs)), NF) -> u'8'1(reduce'ii'in(sequent(Fs, cons(x'2b(x'2d(B), A), Gs)), NF))
   u'8'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(iff(A, B), Gs)), NF) -> u'9'1(reduce'ii'in(sequent(Fs, cons(x'2a(if(A, B), if(B, A)), Gs)), NF))
   u'9'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(p(V), Fs), Gs), sequent(Left, Right)) -> u'10'1(reduce'ii'in(sequent(Fs, Gs), sequent(cons(p(V), Left), Right)))
   u'10'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2b(G1, G2), Gs)), NF) -> u'11'1(reduce'ii'in(sequent(Fs, cons(G1, cons(G2, Gs))), NF))
   u'11'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2a(G1, G2), Gs)), NF) -> u'12'1(reduce'ii'in(sequent(Fs, cons(G1, Gs)), NF), Fs, G2, Gs, NF)
   u'12'1(reduce'ii'out, Fs, G2, Gs, NF) -> u'12'2(reduce'ii'in(sequent(Fs, cons(G2, Gs)), NF))
   u'12'2(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2d(G1), Gs)), NF) -> u'13'1(reduce'ii'in(sequent(cons(G1, Fs), Gs), NF))
   u'13'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(nil, cons(p(V), Gs)), sequent(Left, Right)) -> u'14'1(reduce'ii'in(sequent(nil, Gs), sequent(Left, cons(p(V), Right))))
   u'14'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(nil, nil), sequent(F1, F2)) -> u'15'1(intersect'ii'in(F1, F2))
   u'15'1(intersect'ii'out) -> reduce'ii'out
   tautology'i'in(F) -> u'16'1(reduce'ii'in(sequent(nil, cons(F, nil)), sequent(nil, nil)))
   u'16'1(reduce'ii'out) -> tautology'i'out

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

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


The following pairs can be oriented strictly and are deleted.

   REDUCE'II'IN(sequent(cons(iff(A, B), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(x'2a(if(A, B), if(B, A)), Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(x'2a(F1, F2), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(F1, cons(F2, Fs)), Gs), NF)
   REDUCE'II'IN(sequent(Fs, cons(iff(A, B), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(x'2a(if(A, B), if(B, A)), Gs)), NF)
   REDUCE'II'IN(sequent(Fs, cons(x'2a(G1, G2), Gs)), NF) -> U'12'1(reduce'ii'in(sequent(Fs, cons(G1, Gs)), NF), Fs, G2, Gs, NF)
   REDUCE'II'IN(sequent(Fs, cons(x'2a(G1, G2), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(G1, Gs)), NF)
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:

POL( U'12'1_5(x_1, ..., x_5) ) = 2x_2 + 2x_3 + 2x_4 + 2x_5
POL( U'6'1_5(x_1, ..., x_5) ) = 2x_2 + 2x_3 + 2x_4 + 2x_5
POL( reduce'ii'in_2(x_1, x_2) ) = max{0, 2x_2 - 2}
POL( sequent_2(x_1, x_2) ) = x_1 + x_2
POL( cons_2(x_1, x_2) ) = x_1 + x_2
POL( if_2(x_1, x_2) ) = x_1 + x_2
POL( u'3'1_1(x_1) ) = 2
POL( x'2b_2(x_1, x_2) ) = x_1 + x_2
POL( x'2d_1(x_1) ) = x_1
POL( iff_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2
POL( u'4'1_1(x_1) ) = max{0, -2}
POL( x'2a_2(x_1, x_2) ) = x_1 + x_2 + 1
POL( u'5'1_1(x_1) ) = max{0, 2x_1 - 2}
POL( u'6'1_5(x_1, ..., x_5) ) = max{0, x_3 - 2}
POL( u'7'1_1(x_1) ) = max{0, 2x_1 - 2}
POL( u'8'1_1(x_1) ) = max{0, -2}
POL( u'9'1_1(x_1) ) = 1
POL( p_1(x_1) ) = 0
POL( u'10'1_1(x_1) ) = 2
POL( u'11'1_1(x_1) ) = 2
POL( u'12'1_5(x_1, ..., x_5) ) = x_3 + 2
POL( u'13'1_1(x_1) ) = max{0, -2}
POL( nil ) = 0
POL( u'14'1_1(x_1) ) = max{0, -2}
POL( reduce'ii'out ) = 0
POL( u'15'1_1(x_1) ) = max{0, -2}
POL( intersect'ii'in_2(x_1, x_2) ) = 0
POL( u'12'2_1(x_1) ) = max{0, -2}
POL( u'6'2_1(x_1) ) = 2x_1 + 2
POL( intersect'ii'out ) = 2
POL( u'1'1_1(x_1) ) = max{0, -2}
POL( u'2'1_1(x_1) ) = max{0, -2}
POL( REDUCE'II'IN_2(x_1, x_2) ) = 2x_1 + 2x_2

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


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

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

   REDUCE'II'IN(sequent(cons(x'2b(F1, F2), Fs), Gs), NF) -> U'6'1(reduce'ii'in(sequent(cons(F1, Fs), Gs), NF), F2, Fs, Gs, NF)
   U'6'1(reduce'ii'out, F2, Fs, Gs, NF) -> REDUCE'II'IN(sequent(cons(F2, Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(if(A, B), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(x'2b(x'2d(B), A), Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(x'2b(F1, F2), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(F1, Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(x'2d(F1), Fs), Gs), NF) -> REDUCE'II'IN(sequent(Fs, cons(F1, Gs)), NF)
   REDUCE'II'IN(sequent(Fs, cons(if(A, B), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(x'2b(x'2d(B), A), Gs)), NF)
   REDUCE'II'IN(sequent(cons(p(V), Fs), Gs), sequent(Left, Right)) -> REDUCE'II'IN(sequent(Fs, Gs), sequent(cons(p(V), Left), Right))
   U'12'1(reduce'ii'out, Fs, G2, Gs, NF) -> REDUCE'II'IN(sequent(Fs, cons(G2, Gs)), NF)
   REDUCE'II'IN(sequent(Fs, cons(x'2b(G1, G2), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(G1, cons(G2, Gs))), NF)
   REDUCE'II'IN(sequent(Fs, cons(x'2d(G1), Gs)), NF) -> REDUCE'II'IN(sequent(cons(G1, Fs), Gs), NF)
   REDUCE'II'IN(sequent(nil, cons(p(V), Gs)), sequent(Left, Right)) -> REDUCE'II'IN(sequent(nil, Gs), sequent(Left, cons(p(V), Right)))

The TRS R consists of the following rules:

   intersect'ii'in(cons(X, X0), cons(X, X1)) -> intersect'ii'out
   intersect'ii'in(Xs, cons(X0, Ys)) -> u'1'1(intersect'ii'in(Xs, Ys))
   u'1'1(intersect'ii'out) -> intersect'ii'out
   intersect'ii'in(cons(X0, Xs), Ys) -> u'2'1(intersect'ii'in(Xs, Ys))
   u'2'1(intersect'ii'out) -> intersect'ii'out
   reduce'ii'in(sequent(cons(if(A, B), Fs), Gs), NF) -> u'3'1(reduce'ii'in(sequent(cons(x'2b(x'2d(B), A), Fs), Gs), NF))
   u'3'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(iff(A, B), Fs), Gs), NF) -> u'4'1(reduce'ii'in(sequent(cons(x'2a(if(A, B), if(B, A)), Fs), Gs), NF))
   u'4'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2a(F1, F2), Fs), Gs), NF) -> u'5'1(reduce'ii'in(sequent(cons(F1, cons(F2, Fs)), Gs), NF))
   u'5'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2b(F1, F2), Fs), Gs), NF) -> u'6'1(reduce'ii'in(sequent(cons(F1, Fs), Gs), NF), F2, Fs, Gs, NF)
   u'6'1(reduce'ii'out, F2, Fs, Gs, NF) -> u'6'2(reduce'ii'in(sequent(cons(F2, Fs), Gs), NF))
   u'6'2(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2d(F1), Fs), Gs), NF) -> u'7'1(reduce'ii'in(sequent(Fs, cons(F1, Gs)), NF))
   u'7'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(if(A, B), Gs)), NF) -> u'8'1(reduce'ii'in(sequent(Fs, cons(x'2b(x'2d(B), A), Gs)), NF))
   u'8'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(iff(A, B), Gs)), NF) -> u'9'1(reduce'ii'in(sequent(Fs, cons(x'2a(if(A, B), if(B, A)), Gs)), NF))
   u'9'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(p(V), Fs), Gs), sequent(Left, Right)) -> u'10'1(reduce'ii'in(sequent(Fs, Gs), sequent(cons(p(V), Left), Right)))
   u'10'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2b(G1, G2), Gs)), NF) -> u'11'1(reduce'ii'in(sequent(Fs, cons(G1, cons(G2, Gs))), NF))
   u'11'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2a(G1, G2), Gs)), NF) -> u'12'1(reduce'ii'in(sequent(Fs, cons(G1, Gs)), NF), Fs, G2, Gs, NF)
   u'12'1(reduce'ii'out, Fs, G2, Gs, NF) -> u'12'2(reduce'ii'in(sequent(Fs, cons(G2, Gs)), NF))
   u'12'2(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2d(G1), Gs)), NF) -> u'13'1(reduce'ii'in(sequent(cons(G1, Fs), Gs), NF))
   u'13'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(nil, cons(p(V), Gs)), sequent(Left, Right)) -> u'14'1(reduce'ii'in(sequent(nil, Gs), sequent(Left, cons(p(V), Right))))
   u'14'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(nil, nil), sequent(F1, F2)) -> u'15'1(intersect'ii'in(F1, F2))
   u'15'1(intersect'ii'out) -> reduce'ii'out
   tautology'i'in(F) -> u'16'1(reduce'ii'in(sequent(nil, cons(F, nil)), sequent(nil, nil)))
   u'16'1(reduce'ii'out) -> tautology'i'out

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

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

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

   U'6'1(reduce'ii'out, F2, Fs, Gs, NF) -> REDUCE'II'IN(sequent(cons(F2, Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(if(A, B), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(x'2b(x'2d(B), A), Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(x'2b(F1, F2), Fs), Gs), NF) -> U'6'1(reduce'ii'in(sequent(cons(F1, Fs), Gs), NF), F2, Fs, Gs, NF)
   REDUCE'II'IN(sequent(cons(x'2b(F1, F2), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(F1, Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(x'2d(F1), Fs), Gs), NF) -> REDUCE'II'IN(sequent(Fs, cons(F1, Gs)), NF)
   REDUCE'II'IN(sequent(Fs, cons(if(A, B), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(x'2b(x'2d(B), A), Gs)), NF)
   REDUCE'II'IN(sequent(cons(p(V), Fs), Gs), sequent(Left, Right)) -> REDUCE'II'IN(sequent(Fs, Gs), sequent(cons(p(V), Left), Right))
   REDUCE'II'IN(sequent(Fs, cons(x'2b(G1, G2), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(G1, cons(G2, Gs))), NF)
   REDUCE'II'IN(sequent(Fs, cons(x'2d(G1), Gs)), NF) -> REDUCE'II'IN(sequent(cons(G1, Fs), Gs), NF)
   REDUCE'II'IN(sequent(nil, cons(p(V), Gs)), sequent(Left, Right)) -> REDUCE'II'IN(sequent(nil, Gs), sequent(Left, cons(p(V), Right)))

The TRS R consists of the following rules:

   intersect'ii'in(cons(X, X0), cons(X, X1)) -> intersect'ii'out
   intersect'ii'in(Xs, cons(X0, Ys)) -> u'1'1(intersect'ii'in(Xs, Ys))
   u'1'1(intersect'ii'out) -> intersect'ii'out
   intersect'ii'in(cons(X0, Xs), Ys) -> u'2'1(intersect'ii'in(Xs, Ys))
   u'2'1(intersect'ii'out) -> intersect'ii'out
   reduce'ii'in(sequent(cons(if(A, B), Fs), Gs), NF) -> u'3'1(reduce'ii'in(sequent(cons(x'2b(x'2d(B), A), Fs), Gs), NF))
   u'3'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(iff(A, B), Fs), Gs), NF) -> u'4'1(reduce'ii'in(sequent(cons(x'2a(if(A, B), if(B, A)), Fs), Gs), NF))
   u'4'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2a(F1, F2), Fs), Gs), NF) -> u'5'1(reduce'ii'in(sequent(cons(F1, cons(F2, Fs)), Gs), NF))
   u'5'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2b(F1, F2), Fs), Gs), NF) -> u'6'1(reduce'ii'in(sequent(cons(F1, Fs), Gs), NF), F2, Fs, Gs, NF)
   u'6'1(reduce'ii'out, F2, Fs, Gs, NF) -> u'6'2(reduce'ii'in(sequent(cons(F2, Fs), Gs), NF))
   u'6'2(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2d(F1), Fs), Gs), NF) -> u'7'1(reduce'ii'in(sequent(Fs, cons(F1, Gs)), NF))
   u'7'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(if(A, B), Gs)), NF) -> u'8'1(reduce'ii'in(sequent(Fs, cons(x'2b(x'2d(B), A), Gs)), NF))
   u'8'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(iff(A, B), Gs)), NF) -> u'9'1(reduce'ii'in(sequent(Fs, cons(x'2a(if(A, B), if(B, A)), Gs)), NF))
   u'9'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(p(V), Fs), Gs), sequent(Left, Right)) -> u'10'1(reduce'ii'in(sequent(Fs, Gs), sequent(cons(p(V), Left), Right)))
   u'10'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2b(G1, G2), Gs)), NF) -> u'11'1(reduce'ii'in(sequent(Fs, cons(G1, cons(G2, Gs))), NF))
   u'11'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2a(G1, G2), Gs)), NF) -> u'12'1(reduce'ii'in(sequent(Fs, cons(G1, Gs)), NF), Fs, G2, Gs, NF)
   u'12'1(reduce'ii'out, Fs, G2, Gs, NF) -> u'12'2(reduce'ii'in(sequent(Fs, cons(G2, Gs)), NF))
   u'12'2(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2d(G1), Gs)), NF) -> u'13'1(reduce'ii'in(sequent(cons(G1, Fs), Gs), NF))
   u'13'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(nil, cons(p(V), Gs)), sequent(Left, Right)) -> u'14'1(reduce'ii'in(sequent(nil, Gs), sequent(Left, cons(p(V), Right))))
   u'14'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(nil, nil), sequent(F1, F2)) -> u'15'1(intersect'ii'in(F1, F2))
   u'15'1(intersect'ii'out) -> reduce'ii'out
   tautology'i'in(F) -> u'16'1(reduce'ii'in(sequent(nil, cons(F, nil)), sequent(nil, nil)))
   u'16'1(reduce'ii'out) -> tautology'i'out

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

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


The following pairs can be oriented strictly and are deleted.

   U'6'1(reduce'ii'out, F2, Fs, Gs, NF) -> REDUCE'II'IN(sequent(cons(F2, Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(x'2b(F1, F2), Fs), Gs), NF) -> U'6'1(reduce'ii'in(sequent(cons(F1, Fs), Gs), NF), F2, Fs, Gs, NF)
   REDUCE'II'IN(sequent(cons(x'2b(F1, F2), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(F1, Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(p(V), Fs), Gs), sequent(Left, Right)) -> REDUCE'II'IN(sequent(Fs, Gs), sequent(cons(p(V), Left), Right))
   REDUCE'II'IN(sequent(nil, cons(p(V), Gs)), sequent(Left, Right)) -> REDUCE'II'IN(sequent(nil, Gs), sequent(Left, cons(p(V), Right)))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:

POL( U'6'1_5(x_1, ..., x_5) ) = 2x_2 + 2x_3 + 2x_4 + 1
POL( reduce'ii'in_2(x_1, x_2) ) = max{0, -2}
POL( sequent_2(x_1, x_2) ) = max{0, 2x_1 + 2x_2 - 2}
POL( cons_2(x_1, x_2) ) = x_1 + x_2 + 2
POL( if_2(x_1, x_2) ) = x_1 + 2x_2 + 2
POL( u'3'1_1(x_1) ) = max{0, -2}
POL( x'2b_2(x_1, x_2) ) = 2x_1 + x_2 + 2
POL( x'2d_1(x_1) ) = x_1
POL( iff_2(x_1, x_2) ) = 0
POL( u'4'1_1(x_1) ) = max{0, -2}
POL( x'2a_2(x_1, x_2) ) = max{0, -2}
POL( u'5'1_1(x_1) ) = 2
POL( u'6'1_5(x_1, ..., x_5) ) = max{0, 2x_2 + x_4 + 2x_5 - 2}
POL( u'7'1_1(x_1) ) = max{0, -2}
POL( u'8'1_1(x_1) ) = max{0, -2}
POL( u'9'1_1(x_1) ) = max{0, -2}
POL( p_1(x_1) ) = 2
POL( u'10'1_1(x_1) ) = max{0, -2}
POL( u'11'1_1(x_1) ) = 2
POL( u'12'1_5(x_1, ..., x_5) ) = x_3 + 1
POL( u'13'1_1(x_1) ) = max{0, -2}
POL( reduce'ii'out ) = 0
POL( u'14'1_1(x_1) ) = 1
POL( nil ) = 1
POL( u'15'1_1(x_1) ) = max{0, -2}
POL( intersect'ii'in_2(x_1, x_2) ) = 0
POL( u'12'2_1(x_1) ) = 2
POL( u'6'2_1(x_1) ) = 2
POL( intersect'ii'out ) = 2
POL( u'1'1_1(x_1) ) = max{0, -2}
POL( u'2'1_1(x_1) ) = max{0, -2}
POL( REDUCE'II'IN_2(x_1, x_2) ) = max{0, x_1 - 2}

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


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

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

   REDUCE'II'IN(sequent(cons(if(A, B), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(x'2b(x'2d(B), A), Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(x'2d(F1), Fs), Gs), NF) -> REDUCE'II'IN(sequent(Fs, cons(F1, Gs)), NF)
   REDUCE'II'IN(sequent(Fs, cons(if(A, B), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(x'2b(x'2d(B), A), Gs)), NF)
   REDUCE'II'IN(sequent(Fs, cons(x'2b(G1, G2), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(G1, cons(G2, Gs))), NF)
   REDUCE'II'IN(sequent(Fs, cons(x'2d(G1), Gs)), NF) -> REDUCE'II'IN(sequent(cons(G1, Fs), Gs), NF)

The TRS R consists of the following rules:

   intersect'ii'in(cons(X, X0), cons(X, X1)) -> intersect'ii'out
   intersect'ii'in(Xs, cons(X0, Ys)) -> u'1'1(intersect'ii'in(Xs, Ys))
   u'1'1(intersect'ii'out) -> intersect'ii'out
   intersect'ii'in(cons(X0, Xs), Ys) -> u'2'1(intersect'ii'in(Xs, Ys))
   u'2'1(intersect'ii'out) -> intersect'ii'out
   reduce'ii'in(sequent(cons(if(A, B), Fs), Gs), NF) -> u'3'1(reduce'ii'in(sequent(cons(x'2b(x'2d(B), A), Fs), Gs), NF))
   u'3'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(iff(A, B), Fs), Gs), NF) -> u'4'1(reduce'ii'in(sequent(cons(x'2a(if(A, B), if(B, A)), Fs), Gs), NF))
   u'4'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2a(F1, F2), Fs), Gs), NF) -> u'5'1(reduce'ii'in(sequent(cons(F1, cons(F2, Fs)), Gs), NF))
   u'5'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2b(F1, F2), Fs), Gs), NF) -> u'6'1(reduce'ii'in(sequent(cons(F1, Fs), Gs), NF), F2, Fs, Gs, NF)
   u'6'1(reduce'ii'out, F2, Fs, Gs, NF) -> u'6'2(reduce'ii'in(sequent(cons(F2, Fs), Gs), NF))
   u'6'2(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(x'2d(F1), Fs), Gs), NF) -> u'7'1(reduce'ii'in(sequent(Fs, cons(F1, Gs)), NF))
   u'7'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(if(A, B), Gs)), NF) -> u'8'1(reduce'ii'in(sequent(Fs, cons(x'2b(x'2d(B), A), Gs)), NF))
   u'8'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(iff(A, B), Gs)), NF) -> u'9'1(reduce'ii'in(sequent(Fs, cons(x'2a(if(A, B), if(B, A)), Gs)), NF))
   u'9'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(cons(p(V), Fs), Gs), sequent(Left, Right)) -> u'10'1(reduce'ii'in(sequent(Fs, Gs), sequent(cons(p(V), Left), Right)))
   u'10'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2b(G1, G2), Gs)), NF) -> u'11'1(reduce'ii'in(sequent(Fs, cons(G1, cons(G2, Gs))), NF))
   u'11'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2a(G1, G2), Gs)), NF) -> u'12'1(reduce'ii'in(sequent(Fs, cons(G1, Gs)), NF), Fs, G2, Gs, NF)
   u'12'1(reduce'ii'out, Fs, G2, Gs, NF) -> u'12'2(reduce'ii'in(sequent(Fs, cons(G2, Gs)), NF))
   u'12'2(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(Fs, cons(x'2d(G1), Gs)), NF) -> u'13'1(reduce'ii'in(sequent(cons(G1, Fs), Gs), NF))
   u'13'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(nil, cons(p(V), Gs)), sequent(Left, Right)) -> u'14'1(reduce'ii'in(sequent(nil, Gs), sequent(Left, cons(p(V), Right))))
   u'14'1(reduce'ii'out) -> reduce'ii'out
   reduce'ii'in(sequent(nil, nil), sequent(F1, F2)) -> u'15'1(intersect'ii'in(F1, F2))
   u'15'1(intersect'ii'out) -> reduce'ii'out
   tautology'i'in(F) -> u'16'1(reduce'ii'in(sequent(nil, cons(F, nil)), sequent(nil, nil)))
   u'16'1(reduce'ii'out) -> tautology'i'out

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

(17) 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.
----------------------------------------

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

   REDUCE'II'IN(sequent(cons(if(A, B), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(x'2b(x'2d(B), A), Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(x'2d(F1), Fs), Gs), NF) -> REDUCE'II'IN(sequent(Fs, cons(F1, Gs)), NF)
   REDUCE'II'IN(sequent(Fs, cons(if(A, B), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(x'2b(x'2d(B), A), Gs)), NF)
   REDUCE'II'IN(sequent(Fs, cons(x'2b(G1, G2), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(G1, cons(G2, Gs))), NF)
   REDUCE'II'IN(sequent(Fs, cons(x'2d(G1), Gs)), NF) -> REDUCE'II'IN(sequent(cons(G1, Fs), Gs), NF)

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

(19) UsableRulesReductionPairsProof (EQUIVALENT)
By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.

The following dependency pairs can be deleted:

   REDUCE'II'IN(sequent(cons(if(A, B), Fs), Gs), NF) -> REDUCE'II'IN(sequent(cons(x'2b(x'2d(B), A), Fs), Gs), NF)
   REDUCE'II'IN(sequent(cons(x'2d(F1), Fs), Gs), NF) -> REDUCE'II'IN(sequent(Fs, cons(F1, Gs)), NF)
   REDUCE'II'IN(sequent(Fs, cons(if(A, B), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(x'2b(x'2d(B), A), Gs)), NF)
   REDUCE'II'IN(sequent(Fs, cons(x'2d(G1), Gs)), NF) -> REDUCE'II'IN(sequent(cons(G1, Fs), Gs), NF)
No rules are removed from R.

Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(REDUCE'II'IN(x_1, x_2)) = x_1 + x_2
   POL(cons(x_1, x_2)) = 2 + 2*x_1 + x_2
   POL(if(x_1, x_2)) = 2 + 2*x_1 + 2*x_2
   POL(sequent(x_1, x_2)) = x_1 + x_2
   POL(x'2b(x_1, x_2)) = 1 + x_1 + 2*x_2
   POL(x'2d(x_1)) = 1 + 2*x_1


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

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

   REDUCE'II'IN(sequent(Fs, cons(x'2b(G1, G2), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(G1, cons(G2, Gs))), NF)

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

(21) UsableRulesReductionPairsProof (EQUIVALENT)
By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.

The following dependency pairs can be deleted:

   REDUCE'II'IN(sequent(Fs, cons(x'2b(G1, G2), Gs)), NF) -> REDUCE'II'IN(sequent(Fs, cons(G1, cons(G2, Gs))), NF)
No rules are removed from R.

Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(REDUCE'II'IN(x_1, x_2)) = x_1 + x_2
   POL(cons(x_1, x_2)) = 2*x_1 + x_2
   POL(sequent(x_1, x_2)) = x_1 + 2*x_2
   POL(x'2b(x_1, x_2)) = 2*x_1 + x_2


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

(22)
Obligation:
Q DP problem:
P is empty.
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

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

(24)
YES