/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


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

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


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

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

   g(x, x, x) -> g(c, d, e)
   g(x, y, x) -> g(c, d, e)
   s(f(x, y)) -> f(y, f(s(s(x)), a))
   h(h(x, a), y) -> h(h(a, y), h(a, x))
   f(x, f(y, f(x, y))) -> f(a, f(x, f(y, b)))
   f(h(a, y), g(x, b, a)) -> h(f(x, s(y)), s(b))
   h(f(x, s(y)), b) -> f(a, g(y, a, f(s(x), a)))
   f(x, g(x, a, f(s(x), y))) -> f(h(x, b), g(a, b, y))
   s(y) -> b

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:

   G(x, x, x) -> G(c, d, e)
   G(x, y, x) -> G(c, d, e)
   S(f(x, y)) -> F(y, f(s(s(x)), a))
   S(f(x, y)) -> F(s(s(x)), a)
   S(f(x, y)) -> S(s(x))
   S(f(x, y)) -> S(x)
   H(h(x, a), y) -> H(h(a, y), h(a, x))
   H(h(x, a), y) -> H(a, y)
   H(h(x, a), y) -> H(a, x)
   F(x, f(y, f(x, y))) -> F(a, f(x, f(y, b)))
   F(x, f(y, f(x, y))) -> F(x, f(y, b))
   F(x, f(y, f(x, y))) -> F(y, b)
   F(h(a, y), g(x, b, a)) -> H(f(x, s(y)), s(b))
   F(h(a, y), g(x, b, a)) -> F(x, s(y))
   F(h(a, y), g(x, b, a)) -> S(y)
   F(h(a, y), g(x, b, a)) -> S(b)
   H(f(x, s(y)), b) -> F(a, g(y, a, f(s(x), a)))
   H(f(x, s(y)), b) -> G(y, a, f(s(x), a))
   H(f(x, s(y)), b) -> F(s(x), a)
   H(f(x, s(y)), b) -> S(x)
   F(x, g(x, a, f(s(x), y))) -> F(h(x, b), g(a, b, y))
   F(x, g(x, a, f(s(x), y))) -> H(x, b)
   F(x, g(x, a, f(s(x), y))) -> G(a, b, y)

The TRS R consists of the following rules:

   g(x, x, x) -> g(c, d, e)
   g(x, y, x) -> g(c, d, e)
   s(f(x, y)) -> f(y, f(s(s(x)), a))
   h(h(x, a), y) -> h(h(a, y), h(a, x))
   f(x, f(y, f(x, y))) -> f(a, f(x, f(y, b)))
   f(h(a, y), g(x, b, a)) -> h(f(x, s(y)), s(b))
   h(f(x, s(y)), b) -> f(a, g(y, a, f(s(x), a)))
   f(x, g(x, a, f(s(x), y))) -> f(h(x, b), g(a, b, y))
   s(y) -> b

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 4 SCCs with 15 less nodes.
----------------------------------------

(4)
Complex Obligation (AND)

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

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

   F(x, f(y, f(x, y))) -> F(a, f(x, f(y, b)))

The TRS R consists of the following rules:

   g(x, x, x) -> g(c, d, e)
   g(x, y, x) -> g(c, d, e)
   s(f(x, y)) -> f(y, f(s(s(x)), a))
   h(h(x, a), y) -> h(h(a, y), h(a, x))
   f(x, f(y, f(x, y))) -> f(a, f(x, f(y, b)))
   f(h(a, y), g(x, b, a)) -> h(f(x, s(y)), s(b))
   h(f(x, s(y)), b) -> f(a, g(y, a, f(s(x), a)))
   f(x, g(x, a, f(s(x), y))) -> f(h(x, b), g(a, b, y))
   s(y) -> b

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:

   F(x, f(y, f(x, y))) -> F(a, f(x, f(y, b)))

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

(8) TransformationProof (EQUIVALENT)
By instantiating [LPAR04] the rule F(x, f(y, f(x, y))) -> F(a, f(x, f(y, b))) we obtained the following new rules [LPAR04]:

   (F(a, f(b, f(a, b))) -> F(a, f(a, f(b, b))),F(a, f(b, f(a, b))) -> F(a, f(a, f(b, b))))


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

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

   F(a, f(b, f(a, b))) -> F(a, f(a, f(b, b)))

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

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

(11)
TRUE

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

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

   S(f(x, y)) -> S(x)
   S(f(x, y)) -> S(s(x))

The TRS R consists of the following rules:

   g(x, x, x) -> g(c, d, e)
   g(x, y, x) -> g(c, d, e)
   s(f(x, y)) -> f(y, f(s(s(x)), a))
   h(h(x, a), y) -> h(h(a, y), h(a, x))
   f(x, f(y, f(x, y))) -> f(a, f(x, f(y, b)))
   f(h(a, y), g(x, b, a)) -> h(f(x, s(y)), s(b))
   h(f(x, s(y)), b) -> f(a, g(y, a, f(s(x), a)))
   f(x, g(x, a, f(s(x), y))) -> f(h(x, b), g(a, b, y))
   s(y) -> b

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

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

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

   S(f(x, y)) -> S(x)
   S(f(x, y)) -> S(s(x))

The TRS R consists of the following rules:

   s(f(x, y)) -> f(y, f(s(s(x)), a))
   s(y) -> b

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

(15) TransformationProof (EQUIVALENT)
By narrowing [LPAR04] the rule S(f(x, y)) -> S(s(x)) at position [0] we obtained the following new rules [LPAR04]:

   (S(f(f(x0, x1), y1)) -> S(f(x1, f(s(s(x0)), a))),S(f(f(x0, x1), y1)) -> S(f(x1, f(s(s(x0)), a))))
   (S(f(x0, y1)) -> S(b),S(f(x0, y1)) -> S(b))


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

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

   S(f(x, y)) -> S(x)
   S(f(f(x0, x1), y1)) -> S(f(x1, f(s(s(x0)), a)))
   S(f(x0, y1)) -> S(b)

The TRS R consists of the following rules:

   s(f(x, y)) -> f(y, f(s(s(x)), a))
   s(y) -> b

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

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

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

   S(f(x, y)) -> S(x)
   S(f(f(x0, x1), y1)) -> S(f(x1, f(s(s(x0)), a)))

The TRS R consists of the following rules:

   s(f(x, y)) -> f(y, f(s(s(x)), a))
   s(y) -> b

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

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


The following pairs can be oriented strictly and are deleted.

   S(f(x, y)) -> S(x)
   S(f(f(x0, x1), y1)) -> S(f(x1, f(s(s(x0)), a)))
The remaining pairs can at least be oriented weakly.
Used ordering:  Matrix interpretation [MATRO] to (N^2, +, *, >=, >) :

   <<<
 POL(S(x_1)) =  	[[0]] 	 +  	[[2, 0]] 	* 	x_1
>>>

   <<<
 POL(f(x_1, x_2)) =  	[[1], [1]] 	 +  	[[1, 1], [0, 0]] 	* 	x_1 	 +  	[[0, 0], [1, 1]] 	* 	x_2
>>>

   <<<
 POL(s(x_1)) =  	[[0], [0]] 	 +  	[[0, 1], [3, 0]] 	* 	x_1
>>>

   <<<
 POL(a) =  	[[0], [0]]
>>>

   <<<
 POL(b) =  	[[0], [0]]
>>>


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

   s(f(x, y)) -> f(y, f(s(s(x)), a))
   s(y) -> b


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

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

   s(f(x, y)) -> f(y, f(s(s(x)), a))
   s(y) -> b

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

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

(22)
YES

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

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

   H(h(x, a), y) -> H(h(a, y), h(a, x))

The TRS R consists of the following rules:

   g(x, x, x) -> g(c, d, e)
   g(x, y, x) -> g(c, d, e)
   s(f(x, y)) -> f(y, f(s(s(x)), a))
   h(h(x, a), y) -> h(h(a, y), h(a, x))
   f(x, f(y, f(x, y))) -> f(a, f(x, f(y, b)))
   f(h(a, y), g(x, b, a)) -> h(f(x, s(y)), s(b))
   h(f(x, s(y)), b) -> f(a, g(y, a, f(s(x), a)))
   f(x, g(x, a, f(s(x), y))) -> f(h(x, b), g(a, b, y))
   s(y) -> b

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

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

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

   H(h(x, a), y) -> H(h(a, y), h(a, x))

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

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


The following pairs can be oriented strictly and are deleted.

   H(h(x, a), y) -> H(h(a, y), h(a, x))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO,RATPOLO]:

   POL(H(x_1, x_2)) = x_1 + [1/2]x_2
   POL(a) = [1]
   POL(h(x_1, x_2)) = [1/4]x_1 + [1/2]x_2
The value of delta used in the strict ordering is 1/8.
The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
none


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

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

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

(29)
YES

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

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

   H(f(x, s(y)), b) -> F(a, g(y, a, f(s(x), a)))
   F(x, g(x, a, f(s(x), y))) -> F(h(x, b), g(a, b, y))
   F(h(a, y), g(x, b, a)) -> H(f(x, s(y)), s(b))
   F(x, g(x, a, f(s(x), y))) -> H(x, b)

The TRS R consists of the following rules:

   g(x, x, x) -> g(c, d, e)
   g(x, y, x) -> g(c, d, e)
   s(f(x, y)) -> f(y, f(s(s(x)), a))
   h(h(x, a), y) -> h(h(a, y), h(a, x))
   f(x, f(y, f(x, y))) -> f(a, f(x, f(y, b)))
   f(h(a, y), g(x, b, a)) -> h(f(x, s(y)), s(b))
   h(f(x, s(y)), b) -> f(a, g(y, a, f(s(x), a)))
   f(x, g(x, a, f(s(x), y))) -> f(h(x, b), g(a, b, y))
   s(y) -> b

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

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

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

   H(f(x, s(y)), b) -> F(a, g(y, a, f(s(x), a)))
   F(x, g(x, a, f(s(x), y))) -> F(h(x, b), g(a, b, y))
   F(h(a, y), g(x, b, a)) -> H(f(x, s(y)), s(b))
   F(x, g(x, a, f(s(x), y))) -> H(x, b)

The TRS R consists of the following rules:

   s(f(x, y)) -> f(y, f(s(s(x)), a))
   s(y) -> b
   f(x, f(y, f(x, y))) -> f(a, f(x, f(y, b)))
   h(f(x, s(y)), b) -> f(a, g(y, a, f(s(x), a)))
   f(x, g(x, a, f(s(x), y))) -> f(h(x, b), g(a, b, y))
   f(h(a, y), g(x, b, a)) -> h(f(x, s(y)), s(b))
   g(x, y, x) -> g(c, d, e)
   h(h(x, a), y) -> h(h(a, y), h(a, x))

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

(33) TransformationProof (EQUIVALENT)
By instantiating [LPAR04] the rule F(x, g(x, a, f(s(x), y))) -> F(h(x, b), g(a, b, y)) we obtained the following new rules [LPAR04]:

   (F(a, g(a, a, f(s(a), x1))) -> F(h(a, b), g(a, b, x1)),F(a, g(a, a, f(s(a), x1))) -> F(h(a, b), g(a, b, x1)))


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

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

   H(f(x, s(y)), b) -> F(a, g(y, a, f(s(x), a)))
   F(h(a, y), g(x, b, a)) -> H(f(x, s(y)), s(b))
   F(x, g(x, a, f(s(x), y))) -> H(x, b)
   F(a, g(a, a, f(s(a), x1))) -> F(h(a, b), g(a, b, x1))

The TRS R consists of the following rules:

   s(f(x, y)) -> f(y, f(s(s(x)), a))
   s(y) -> b
   f(x, f(y, f(x, y))) -> f(a, f(x, f(y, b)))
   h(f(x, s(y)), b) -> f(a, g(y, a, f(s(x), a)))
   f(x, g(x, a, f(s(x), y))) -> f(h(x, b), g(a, b, y))
   f(h(a, y), g(x, b, a)) -> h(f(x, s(y)), s(b))
   g(x, y, x) -> g(c, d, e)
   h(h(x, a), y) -> h(h(a, y), h(a, x))

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

(35) TransformationProof (EQUIVALENT)
By instantiating [LPAR04] the rule F(h(a, y), g(x, b, a)) -> H(f(x, s(y)), s(b)) we obtained the following new rules [LPAR04]:

   (F(h(a, b), g(x1, b, a)) -> H(f(x1, s(b)), s(b)),F(h(a, b), g(x1, b, a)) -> H(f(x1, s(b)), s(b)))


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

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

   H(f(x, s(y)), b) -> F(a, g(y, a, f(s(x), a)))
   F(x, g(x, a, f(s(x), y))) -> H(x, b)
   F(a, g(a, a, f(s(a), x1))) -> F(h(a, b), g(a, b, x1))
   F(h(a, b), g(x1, b, a)) -> H(f(x1, s(b)), s(b))

The TRS R consists of the following rules:

   s(f(x, y)) -> f(y, f(s(s(x)), a))
   s(y) -> b
   f(x, f(y, f(x, y))) -> f(a, f(x, f(y, b)))
   h(f(x, s(y)), b) -> f(a, g(y, a, f(s(x), a)))
   f(x, g(x, a, f(s(x), y))) -> f(h(x, b), g(a, b, y))
   f(h(a, y), g(x, b, a)) -> h(f(x, s(y)), s(b))
   g(x, y, x) -> g(c, d, e)
   h(h(x, a), y) -> h(h(a, y), h(a, x))

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

(37) TransformationProof (EQUIVALENT)
By instantiating [LPAR04] the rule F(x, g(x, a, f(s(x), y))) -> H(x, b) we obtained the following new rules [LPAR04]:

   (F(a, g(a, a, f(s(a), x1))) -> H(a, b),F(a, g(a, a, f(s(a), x1))) -> H(a, b))


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

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

   H(f(x, s(y)), b) -> F(a, g(y, a, f(s(x), a)))
   F(a, g(a, a, f(s(a), x1))) -> F(h(a, b), g(a, b, x1))
   F(h(a, b), g(x1, b, a)) -> H(f(x1, s(b)), s(b))
   F(a, g(a, a, f(s(a), x1))) -> H(a, b)

The TRS R consists of the following rules:

   s(f(x, y)) -> f(y, f(s(s(x)), a))
   s(y) -> b
   f(x, f(y, f(x, y))) -> f(a, f(x, f(y, b)))
   h(f(x, s(y)), b) -> f(a, g(y, a, f(s(x), a)))
   f(x, g(x, a, f(s(x), y))) -> f(h(x, b), g(a, b, y))
   f(h(a, y), g(x, b, a)) -> h(f(x, s(y)), s(b))
   g(x, y, x) -> g(c, d, e)
   h(h(x, a), y) -> h(h(a, y), h(a, x))

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

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

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

   F(a, g(a, a, f(s(a), x1))) -> F(h(a, b), g(a, b, x1))
   F(h(a, b), g(x1, b, a)) -> H(f(x1, s(b)), s(b))
   H(f(x, s(y)), b) -> F(a, g(y, a, f(s(x), a)))

The TRS R consists of the following rules:

   s(f(x, y)) -> f(y, f(s(s(x)), a))
   s(y) -> b
   f(x, f(y, f(x, y))) -> f(a, f(x, f(y, b)))
   h(f(x, s(y)), b) -> f(a, g(y, a, f(s(x), a)))
   f(x, g(x, a, f(s(x), y))) -> f(h(x, b), g(a, b, y))
   f(h(a, y), g(x, b, a)) -> h(f(x, s(y)), s(b))
   g(x, y, x) -> g(c, d, e)
   h(h(x, a), y) -> h(h(a, y), h(a, x))

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

(41) TransformationProof (EQUIVALENT)
By narrowing [LPAR04] the rule F(h(a, b), g(x1, b, a)) -> H(f(x1, s(b)), s(b)) at position [1] we obtained the following new rules [LPAR04]:

   (F(h(a, b), g(y0, b, a)) -> H(f(y0, s(b)), b),F(h(a, b), g(y0, b, a)) -> H(f(y0, s(b)), b))


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

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

   F(a, g(a, a, f(s(a), x1))) -> F(h(a, b), g(a, b, x1))
   H(f(x, s(y)), b) -> F(a, g(y, a, f(s(x), a)))
   F(h(a, b), g(y0, b, a)) -> H(f(y0, s(b)), b)

The TRS R consists of the following rules:

   s(f(x, y)) -> f(y, f(s(s(x)), a))
   s(y) -> b
   f(x, f(y, f(x, y))) -> f(a, f(x, f(y, b)))
   h(f(x, s(y)), b) -> f(a, g(y, a, f(s(x), a)))
   f(x, g(x, a, f(s(x), y))) -> f(h(x, b), g(a, b, y))
   f(h(a, y), g(x, b, a)) -> h(f(x, s(y)), s(b))
   g(x, y, x) -> g(c, d, e)
   h(h(x, a), y) -> h(h(a, y), h(a, x))

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

(43) TransformationProof (EQUIVALENT)
By forward instantiating [JAR06] the rule F(a, g(a, a, f(s(a), x1))) -> F(h(a, b), g(a, b, x1)) we obtained the following new rules [LPAR04]:

   (F(a, g(a, a, f(s(a), a))) -> F(h(a, b), g(a, b, a)),F(a, g(a, a, f(s(a), a))) -> F(h(a, b), g(a, b, a)))


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

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

   H(f(x, s(y)), b) -> F(a, g(y, a, f(s(x), a)))
   F(h(a, b), g(y0, b, a)) -> H(f(y0, s(b)), b)
   F(a, g(a, a, f(s(a), a))) -> F(h(a, b), g(a, b, a))

The TRS R consists of the following rules:

   s(f(x, y)) -> f(y, f(s(s(x)), a))
   s(y) -> b
   f(x, f(y, f(x, y))) -> f(a, f(x, f(y, b)))
   h(f(x, s(y)), b) -> f(a, g(y, a, f(s(x), a)))
   f(x, g(x, a, f(s(x), y))) -> f(h(x, b), g(a, b, y))
   f(h(a, y), g(x, b, a)) -> h(f(x, s(y)), s(b))
   g(x, y, x) -> g(c, d, e)
   h(h(x, a), y) -> h(h(a, y), h(a, x))

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

(45) TransformationProof (EQUIVALENT)
By forward instantiating [JAR06] the rule H(f(x, s(y)), b) -> F(a, g(y, a, f(s(x), a))) we obtained the following new rules [LPAR04]:

   (H(f(a, s(a)), b) -> F(a, g(a, a, f(s(a), a))),H(f(a, s(a)), b) -> F(a, g(a, a, f(s(a), a))))


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

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

   F(h(a, b), g(y0, b, a)) -> H(f(y0, s(b)), b)
   F(a, g(a, a, f(s(a), a))) -> F(h(a, b), g(a, b, a))
   H(f(a, s(a)), b) -> F(a, g(a, a, f(s(a), a)))

The TRS R consists of the following rules:

   s(f(x, y)) -> f(y, f(s(s(x)), a))
   s(y) -> b
   f(x, f(y, f(x, y))) -> f(a, f(x, f(y, b)))
   h(f(x, s(y)), b) -> f(a, g(y, a, f(s(x), a)))
   f(x, g(x, a, f(s(x), y))) -> f(h(x, b), g(a, b, y))
   f(h(a, y), g(x, b, a)) -> h(f(x, s(y)), s(b))
   g(x, y, x) -> g(c, d, e)
   h(h(x, a), y) -> h(h(a, y), h(a, x))

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

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

(48)
TRUE