YES
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


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

(0) QTRS
(1) DependencyPairsProof [EQUIVALENT, 14 ms]
(2) QDP
(3) DependencyGraphProof [EQUIVALENT, 0 ms]
(4) AND
    (5) QDP
        (6) UsableRulesProof [EQUIVALENT, 0 ms]
        (7) QDP
        (8) QDPOrderProof [EQUIVALENT, 94 ms]
        (9) QDP
        (10) DependencyGraphProof [EQUIVALENT, 0 ms]
        (11) QDP
        (12) QDPOrderProof [EQUIVALENT, 264 ms]
        (13) QDP
        (14) DependencyGraphProof [EQUIVALENT, 0 ms]
        (15) QDP
        (16) QDPOrderProof [EQUIVALENT, 289 ms]
        (17) QDP
        (18) DependencyGraphProof [EQUIVALENT, 0 ms]
        (19) QDP
        (20) QDPOrderProof [EQUIVALENT, 13 ms]
        (21) QDP
        (22) DependencyGraphProof [EQUIVALENT, 0 ms]
        (23) QDP
        (24) QDPOrderProof [EQUIVALENT, 4 ms]
        (25) QDP
        (26) PisEmptyProof [EQUIVALENT, 0 ms]
        (27) YES
    (28) QDP
        (29) UsableRulesProof [EQUIVALENT, 2 ms]
        (30) QDP
        (31) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (32) YES


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

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

   3(1(x1)) -> 4(1(x1))
   5(9(x1)) -> 2(6(5(x1)))
   3(5(x1)) -> 8(9(7(x1)))
   9(x1) -> 3(2(3(x1)))
   8(4(x1)) -> 6(x1)
   2(6(x1)) -> 4(3(x1))
   3(8(x1)) -> 3(2(7(x1)))
   9(x1) -> 5(0(2(x1)))
   8(8(4(x1))) -> 1(9(x1))
   7(1(x1)) -> 6(9(x1))
   3(9(x1)) -> 9(3(x1))
   7(5(x1)) -> 1(0(x1))

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:

   5^1(9(x1)) -> 2^1(6(5(x1)))
   5^1(9(x1)) -> 5^1(x1)
   3^1(5(x1)) -> 8^1(9(7(x1)))
   3^1(5(x1)) -> 9^1(7(x1))
   3^1(5(x1)) -> 7^1(x1)
   9^1(x1) -> 3^1(2(3(x1)))
   9^1(x1) -> 2^1(3(x1))
   9^1(x1) -> 3^1(x1)
   2^1(6(x1)) -> 3^1(x1)
   3^1(8(x1)) -> 3^1(2(7(x1)))
   3^1(8(x1)) -> 2^1(7(x1))
   3^1(8(x1)) -> 7^1(x1)
   9^1(x1) -> 5^1(0(2(x1)))
   9^1(x1) -> 2^1(x1)
   8^1(8(4(x1))) -> 9^1(x1)
   7^1(1(x1)) -> 9^1(x1)
   3^1(9(x1)) -> 9^1(3(x1))
   3^1(9(x1)) -> 3^1(x1)

The TRS R consists of the following rules:

   3(1(x1)) -> 4(1(x1))
   5(9(x1)) -> 2(6(5(x1)))
   3(5(x1)) -> 8(9(7(x1)))
   9(x1) -> 3(2(3(x1)))
   8(4(x1)) -> 6(x1)
   2(6(x1)) -> 4(3(x1))
   3(8(x1)) -> 3(2(7(x1)))
   9(x1) -> 5(0(2(x1)))
   8(8(4(x1))) -> 1(9(x1))
   7(1(x1)) -> 6(9(x1))
   3(9(x1)) -> 9(3(x1))
   7(5(x1)) -> 1(0(x1))

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 2 less nodes.
----------------------------------------

(4)
Complex Obligation (AND)

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

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

   8^1(8(4(x1))) -> 9^1(x1)
   9^1(x1) -> 3^1(2(3(x1)))
   3^1(5(x1)) -> 8^1(9(7(x1)))
   3^1(5(x1)) -> 9^1(7(x1))
   9^1(x1) -> 2^1(3(x1))
   2^1(6(x1)) -> 3^1(x1)
   3^1(5(x1)) -> 7^1(x1)
   7^1(1(x1)) -> 9^1(x1)
   9^1(x1) -> 3^1(x1)
   3^1(8(x1)) -> 3^1(2(7(x1)))
   3^1(8(x1)) -> 2^1(7(x1))
   3^1(8(x1)) -> 7^1(x1)
   3^1(9(x1)) -> 9^1(3(x1))
   9^1(x1) -> 2^1(x1)
   3^1(9(x1)) -> 3^1(x1)

The TRS R consists of the following rules:

   3(1(x1)) -> 4(1(x1))
   5(9(x1)) -> 2(6(5(x1)))
   3(5(x1)) -> 8(9(7(x1)))
   9(x1) -> 3(2(3(x1)))
   8(4(x1)) -> 6(x1)
   2(6(x1)) -> 4(3(x1))
   3(8(x1)) -> 3(2(7(x1)))
   9(x1) -> 5(0(2(x1)))
   8(8(4(x1))) -> 1(9(x1))
   7(1(x1)) -> 6(9(x1))
   3(9(x1)) -> 9(3(x1))
   7(5(x1)) -> 1(0(x1))

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:

   8^1(8(4(x1))) -> 9^1(x1)
   9^1(x1) -> 3^1(2(3(x1)))
   3^1(5(x1)) -> 8^1(9(7(x1)))
   3^1(5(x1)) -> 9^1(7(x1))
   9^1(x1) -> 2^1(3(x1))
   2^1(6(x1)) -> 3^1(x1)
   3^1(5(x1)) -> 7^1(x1)
   7^1(1(x1)) -> 9^1(x1)
   9^1(x1) -> 3^1(x1)
   3^1(8(x1)) -> 3^1(2(7(x1)))
   3^1(8(x1)) -> 2^1(7(x1))
   3^1(8(x1)) -> 7^1(x1)
   3^1(9(x1)) -> 9^1(3(x1))
   9^1(x1) -> 2^1(x1)
   3^1(9(x1)) -> 3^1(x1)

The TRS R consists of the following rules:

   3(1(x1)) -> 4(1(x1))
   3(5(x1)) -> 8(9(7(x1)))
   3(8(x1)) -> 3(2(7(x1)))
   3(9(x1)) -> 9(3(x1))
   9(x1) -> 3(2(3(x1)))
   7(1(x1)) -> 6(9(x1))
   7(5(x1)) -> 1(0(x1))
   2(6(x1)) -> 4(3(x1))
   9(x1) -> 5(0(2(x1)))
   8(4(x1)) -> 6(x1)
   8(8(4(x1))) -> 1(9(x1))

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

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


The following pairs can be oriented strictly and are deleted.

   8^1(8(4(x1))) -> 9^1(x1)
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:

POL( 2^1_1(x_1) ) = 0
POL( 8^1_1(x_1) ) = max{0, 2x_1 - 2}
POL( 9^1_1(x_1) ) = max{0, -2}
POL( 2_1(x_1) ) = max{0, -2}
POL( 3^1_1(x_1) ) = max{0, -2}
POL( 4_1(x_1) ) = max{0, -2}
POL( 3_1(x_1) ) = 2x_1
POL( 1_1(x_1) ) = 2
POL( 5_1(x_1) ) = 1
POL( 8_1(x_1) ) = 2
POL( 9_1(x_1) ) = 1
POL( 7_1(x_1) ) = 0
POL( 0_1(x_1) ) = max{0, -2}
POL( 6_1(x_1) ) = 2
POL( 7^1_1(x_1) ) = 0

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

   3(1(x1)) -> 4(1(x1))
   3(5(x1)) -> 8(9(7(x1)))
   3(9(x1)) -> 9(3(x1))
   9(x1) -> 3(2(3(x1)))
   3(8(x1)) -> 3(2(7(x1)))
   2(6(x1)) -> 4(3(x1))
   9(x1) -> 5(0(2(x1)))
   8(8(4(x1))) -> 1(9(x1))
   8(4(x1)) -> 6(x1)


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

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

   9^1(x1) -> 3^1(2(3(x1)))
   3^1(5(x1)) -> 8^1(9(7(x1)))
   3^1(5(x1)) -> 9^1(7(x1))
   9^1(x1) -> 2^1(3(x1))
   2^1(6(x1)) -> 3^1(x1)
   3^1(5(x1)) -> 7^1(x1)
   7^1(1(x1)) -> 9^1(x1)
   9^1(x1) -> 3^1(x1)
   3^1(8(x1)) -> 3^1(2(7(x1)))
   3^1(8(x1)) -> 2^1(7(x1))
   3^1(8(x1)) -> 7^1(x1)
   3^1(9(x1)) -> 9^1(3(x1))
   9^1(x1) -> 2^1(x1)
   3^1(9(x1)) -> 3^1(x1)

The TRS R consists of the following rules:

   3(1(x1)) -> 4(1(x1))
   3(5(x1)) -> 8(9(7(x1)))
   3(8(x1)) -> 3(2(7(x1)))
   3(9(x1)) -> 9(3(x1))
   9(x1) -> 3(2(3(x1)))
   7(1(x1)) -> 6(9(x1))
   7(5(x1)) -> 1(0(x1))
   2(6(x1)) -> 4(3(x1))
   9(x1) -> 5(0(2(x1)))
   8(4(x1)) -> 6(x1)
   8(8(4(x1))) -> 1(9(x1))

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 1 SCC with 1 less node.
----------------------------------------

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

   3^1(5(x1)) -> 9^1(7(x1))
   9^1(x1) -> 3^1(2(3(x1)))
   3^1(5(x1)) -> 7^1(x1)
   7^1(1(x1)) -> 9^1(x1)
   9^1(x1) -> 2^1(3(x1))
   2^1(6(x1)) -> 3^1(x1)
   3^1(8(x1)) -> 3^1(2(7(x1)))
   3^1(8(x1)) -> 2^1(7(x1))
   3^1(8(x1)) -> 7^1(x1)
   3^1(9(x1)) -> 9^1(3(x1))
   9^1(x1) -> 3^1(x1)
   3^1(9(x1)) -> 3^1(x1)
   9^1(x1) -> 2^1(x1)

The TRS R consists of the following rules:

   3(1(x1)) -> 4(1(x1))
   3(5(x1)) -> 8(9(7(x1)))
   3(8(x1)) -> 3(2(7(x1)))
   3(9(x1)) -> 9(3(x1))
   9(x1) -> 3(2(3(x1)))
   7(1(x1)) -> 6(9(x1))
   7(5(x1)) -> 1(0(x1))
   2(6(x1)) -> 4(3(x1))
   9(x1) -> 5(0(2(x1)))
   8(4(x1)) -> 6(x1)
   8(8(4(x1))) -> 1(9(x1))

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

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


The following pairs can be oriented strictly and are deleted.

   7^1(1(x1)) -> 9^1(x1)
The remaining pairs can at least be oriented weakly.
Used ordering:  Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]:

   <<<
 POL(3^1(x_1)) =  	[[0A]] 	 +  	[[0A, -I, 0A]] 	* 	x_1
>>>

   <<<
 POL(5(x_1)) =  	[[-I], [0A], [-I]] 	 +  	[[0A, 0A, 0A], [0A, 1A, -I], [-I, 0A, 1A]] 	* 	x_1
>>>

   <<<
 POL(9^1(x_1)) =  	[[0A]] 	 +  	[[0A, 0A, 0A]] 	* 	x_1
>>>

   <<<
 POL(7(x_1)) =  	[[0A], [0A], [-I]] 	 +  	[[0A, 0A, -I], [0A, 0A, -I], [-I, 0A, -I]] 	* 	x_1
>>>

   <<<
 POL(2(x_1)) =  	[[0A], [-I], [0A]] 	 +  	[[0A, 0A, -I], [-I, -I, -I], [0A, 0A, 0A]] 	* 	x_1
>>>

   <<<
 POL(3(x_1)) =  	[[0A], [0A], [-I]] 	 +  	[[-I, 0A, -I], [-I, 0A, -I], [-I, 0A, -I]] 	* 	x_1
>>>

   <<<
 POL(7^1(x_1)) =  	[[0A]] 	 +  	[[0A, 0A, 1A]] 	* 	x_1
>>>

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

   <<<
 POL(2^1(x_1)) =  	[[0A]] 	 +  	[[0A, 0A, 0A]] 	* 	x_1
>>>

   <<<
 POL(6(x_1)) =  	[[-I], [-I], [-I]] 	 +  	[[0A, 0A, 0A], [0A, 0A, 0A], [0A, 0A, 0A]] 	* 	x_1
>>>

   <<<
 POL(8(x_1)) =  	[[-I], [0A], [-I]] 	 +  	[[0A, 0A, 1A], [-I, -I, 0A], [-I, -I, 0A]] 	* 	x_1
>>>

   <<<
 POL(9(x_1)) =  	[[0A], [0A], [-I]] 	 +  	[[0A, 0A, 0A], [0A, 0A, -I], [-I, -I, 0A]] 	* 	x_1
>>>

   <<<
 POL(0(x_1)) =  	[[0A], [-I], [-I]] 	 +  	[[0A, -I, -I], [-I, -I, -I], [-I, 0A, -I]] 	* 	x_1
>>>

   <<<
 POL(4(x_1)) =  	[[0A], [-I], [0A]] 	 +  	[[0A, 0A, -I], [-I, -I, -I], [0A, 0A, 0A]] 	* 	x_1
>>>


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

   7(1(x1)) -> 6(9(x1))
   7(5(x1)) -> 1(0(x1))
   3(1(x1)) -> 4(1(x1))
   3(5(x1)) -> 8(9(7(x1)))
   3(9(x1)) -> 9(3(x1))
   9(x1) -> 3(2(3(x1)))
   3(8(x1)) -> 3(2(7(x1)))
   2(6(x1)) -> 4(3(x1))
   9(x1) -> 5(0(2(x1)))
   8(8(4(x1))) -> 1(9(x1))
   8(4(x1)) -> 6(x1)


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

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

   3^1(5(x1)) -> 9^1(7(x1))
   9^1(x1) -> 3^1(2(3(x1)))
   3^1(5(x1)) -> 7^1(x1)
   9^1(x1) -> 2^1(3(x1))
   2^1(6(x1)) -> 3^1(x1)
   3^1(8(x1)) -> 3^1(2(7(x1)))
   3^1(8(x1)) -> 2^1(7(x1))
   3^1(8(x1)) -> 7^1(x1)
   3^1(9(x1)) -> 9^1(3(x1))
   9^1(x1) -> 3^1(x1)
   3^1(9(x1)) -> 3^1(x1)
   9^1(x1) -> 2^1(x1)

The TRS R consists of the following rules:

   3(1(x1)) -> 4(1(x1))
   3(5(x1)) -> 8(9(7(x1)))
   3(8(x1)) -> 3(2(7(x1)))
   3(9(x1)) -> 9(3(x1))
   9(x1) -> 3(2(3(x1)))
   7(1(x1)) -> 6(9(x1))
   7(5(x1)) -> 1(0(x1))
   2(6(x1)) -> 4(3(x1))
   9(x1) -> 5(0(2(x1)))
   8(4(x1)) -> 6(x1)
   8(8(4(x1))) -> 1(9(x1))

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

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

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

   9^1(x1) -> 3^1(2(3(x1)))
   3^1(5(x1)) -> 9^1(7(x1))
   9^1(x1) -> 2^1(3(x1))
   2^1(6(x1)) -> 3^1(x1)
   3^1(8(x1)) -> 3^1(2(7(x1)))
   3^1(8(x1)) -> 2^1(7(x1))
   3^1(9(x1)) -> 9^1(3(x1))
   9^1(x1) -> 3^1(x1)
   3^1(9(x1)) -> 3^1(x1)
   9^1(x1) -> 2^1(x1)

The TRS R consists of the following rules:

   3(1(x1)) -> 4(1(x1))
   3(5(x1)) -> 8(9(7(x1)))
   3(8(x1)) -> 3(2(7(x1)))
   3(9(x1)) -> 9(3(x1))
   9(x1) -> 3(2(3(x1)))
   7(1(x1)) -> 6(9(x1))
   7(5(x1)) -> 1(0(x1))
   2(6(x1)) -> 4(3(x1))
   9(x1) -> 5(0(2(x1)))
   8(4(x1)) -> 6(x1)
   8(8(4(x1))) -> 1(9(x1))

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

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


The following pairs can be oriented strictly and are deleted.

   2^1(6(x1)) -> 3^1(x1)
The remaining pairs can at least be oriented weakly.
Used ordering:  Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]:

   <<<
 POL(9^1(x_1)) =  	[[0A]] 	 +  	[[0A, 0A, 1A]] 	* 	x_1
>>>

   <<<
 POL(3^1(x_1)) =  	[[-I]] 	 +  	[[0A, 0A, 0A]] 	* 	x_1
>>>

   <<<
 POL(2(x_1)) =  	[[0A], [-I], [-I]] 	 +  	[[-I, 0A, 1A], [-I, 0A, 0A], [-I, -I, 0A]] 	* 	x_1
>>>

   <<<
 POL(3(x_1)) =  	[[0A], [-I], [-I]] 	 +  	[[0A, 0A, 1A], [-I, 0A, 0A], [-I, -I, 0A]] 	* 	x_1
>>>

   <<<
 POL(5(x_1)) =  	[[0A], [-I], [0A]] 	 +  	[[0A, 0A, -I], [-I, -I, -I], [1A, 0A, 1A]] 	* 	x_1
>>>

   <<<
 POL(7(x_1)) =  	[[-I], [-I], [-I]] 	 +  	[[0A, 0A, 1A], [0A, 0A, -I], [0A, -I, -I]] 	* 	x_1
>>>

   <<<
 POL(2^1(x_1)) =  	[[0A]] 	 +  	[[-I, 0A, 1A]] 	* 	x_1
>>>

   <<<
 POL(6(x_1)) =  	[[0A], [0A], [-I]] 	 +  	[[0A, 0A, 0A], [-I, 0A, 0A], [0A, 0A, 0A]] 	* 	x_1
>>>

   <<<
 POL(8(x_1)) =  	[[1A], [-I], [-I]] 	 +  	[[1A, 0A, 0A], [-I, 0A, -I], [0A, -I, -I]] 	* 	x_1
>>>

   <<<
 POL(9(x_1)) =  	[[0A], [-I], [1A]] 	 +  	[[0A, 0A, 1A], [0A, 0A, 0A], [0A, 0A, 1A]] 	* 	x_1
>>>

   <<<
 POL(1(x_1)) =  	[[1A], [0A], [0A]] 	 +  	[[0A, 0A, 1A], [-I, -I, -I], [-I, 0A, 0A]] 	* 	x_1
>>>

   <<<
 POL(4(x_1)) =  	[[-I], [0A], [-I]] 	 +  	[[0A, 0A, 0A], [-I, 0A, 0A], [-I, 0A, 0A]] 	* 	x_1
>>>

   <<<
 POL(0(x_1)) =  	[[0A], [-I], [-I]] 	 +  	[[-I, -I, 0A], [-I, 0A, -I], [-I, -I, -I]] 	* 	x_1
>>>


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

   3(1(x1)) -> 4(1(x1))
   3(5(x1)) -> 8(9(7(x1)))
   3(9(x1)) -> 9(3(x1))
   9(x1) -> 3(2(3(x1)))
   3(8(x1)) -> 3(2(7(x1)))
   2(6(x1)) -> 4(3(x1))
   7(1(x1)) -> 6(9(x1))
   7(5(x1)) -> 1(0(x1))
   9(x1) -> 5(0(2(x1)))
   8(8(4(x1))) -> 1(9(x1))
   8(4(x1)) -> 6(x1)


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

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

   9^1(x1) -> 3^1(2(3(x1)))
   3^1(5(x1)) -> 9^1(7(x1))
   9^1(x1) -> 2^1(3(x1))
   3^1(8(x1)) -> 3^1(2(7(x1)))
   3^1(8(x1)) -> 2^1(7(x1))
   3^1(9(x1)) -> 9^1(3(x1))
   9^1(x1) -> 3^1(x1)
   3^1(9(x1)) -> 3^1(x1)
   9^1(x1) -> 2^1(x1)

The TRS R consists of the following rules:

   3(1(x1)) -> 4(1(x1))
   3(5(x1)) -> 8(9(7(x1)))
   3(8(x1)) -> 3(2(7(x1)))
   3(9(x1)) -> 9(3(x1))
   9(x1) -> 3(2(3(x1)))
   7(1(x1)) -> 6(9(x1))
   7(5(x1)) -> 1(0(x1))
   2(6(x1)) -> 4(3(x1))
   9(x1) -> 5(0(2(x1)))
   8(4(x1)) -> 6(x1)
   8(8(4(x1))) -> 1(9(x1))

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

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

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

   3^1(5(x1)) -> 9^1(7(x1))
   9^1(x1) -> 3^1(2(3(x1)))
   3^1(8(x1)) -> 3^1(2(7(x1)))
   3^1(9(x1)) -> 9^1(3(x1))
   9^1(x1) -> 3^1(x1)
   3^1(9(x1)) -> 3^1(x1)

The TRS R consists of the following rules:

   3(1(x1)) -> 4(1(x1))
   3(5(x1)) -> 8(9(7(x1)))
   3(8(x1)) -> 3(2(7(x1)))
   3(9(x1)) -> 9(3(x1))
   9(x1) -> 3(2(3(x1)))
   7(1(x1)) -> 6(9(x1))
   7(5(x1)) -> 1(0(x1))
   2(6(x1)) -> 4(3(x1))
   9(x1) -> 5(0(2(x1)))
   8(4(x1)) -> 6(x1)
   8(8(4(x1))) -> 1(9(x1))

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

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


The following pairs can be oriented strictly and are deleted.

   3^1(5(x1)) -> 9^1(7(x1))
   3^1(9(x1)) -> 9^1(3(x1))
   3^1(9(x1)) -> 3^1(x1)
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(0(x_1)) = 0
   POL(1(x_1)) = 0
   POL(2(x_1)) = 0
   POL(3(x_1)) = x_1
   POL(3^1(x_1)) = x_1
   POL(4(x_1)) = 0
   POL(5(x_1)) = 1
   POL(6(x_1)) = 0
   POL(7(x_1)) = 0
   POL(8(x_1)) = 0
   POL(9(x_1)) = 1 + x_1
   POL(9^1(x_1)) = x_1

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

   7(1(x1)) -> 6(9(x1))
   7(5(x1)) -> 1(0(x1))
   3(1(x1)) -> 4(1(x1))
   3(5(x1)) -> 8(9(7(x1)))
   3(9(x1)) -> 9(3(x1))
   9(x1) -> 3(2(3(x1)))
   3(8(x1)) -> 3(2(7(x1)))
   2(6(x1)) -> 4(3(x1))
   9(x1) -> 5(0(2(x1)))
   8(8(4(x1))) -> 1(9(x1))
   8(4(x1)) -> 6(x1)


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

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

   9^1(x1) -> 3^1(2(3(x1)))
   3^1(8(x1)) -> 3^1(2(7(x1)))
   9^1(x1) -> 3^1(x1)

The TRS R consists of the following rules:

   3(1(x1)) -> 4(1(x1))
   3(5(x1)) -> 8(9(7(x1)))
   3(8(x1)) -> 3(2(7(x1)))
   3(9(x1)) -> 9(3(x1))
   9(x1) -> 3(2(3(x1)))
   7(1(x1)) -> 6(9(x1))
   7(5(x1)) -> 1(0(x1))
   2(6(x1)) -> 4(3(x1))
   9(x1) -> 5(0(2(x1)))
   8(4(x1)) -> 6(x1)
   8(8(4(x1))) -> 1(9(x1))

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

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

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

   3^1(8(x1)) -> 3^1(2(7(x1)))

The TRS R consists of the following rules:

   3(1(x1)) -> 4(1(x1))
   3(5(x1)) -> 8(9(7(x1)))
   3(8(x1)) -> 3(2(7(x1)))
   3(9(x1)) -> 9(3(x1))
   9(x1) -> 3(2(3(x1)))
   7(1(x1)) -> 6(9(x1))
   7(5(x1)) -> 1(0(x1))
   2(6(x1)) -> 4(3(x1))
   9(x1) -> 5(0(2(x1)))
   8(4(x1)) -> 6(x1)
   8(8(4(x1))) -> 1(9(x1))

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

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


The following pairs can be oriented strictly and are deleted.

   3^1(8(x1)) -> 3^1(2(7(x1)))
The remaining pairs can at least be oriented weakly.
Used ordering:  Polynomial interpretation [POLO]:

   POL(0(x_1)) = x_1
   POL(1(x_1)) = 1
   POL(2(x_1)) = 0
   POL(3(x_1)) = 1 + x_1
   POL(3^1(x_1)) = x_1
   POL(4(x_1)) = 0
   POL(5(x_1)) = 1 + x_1
   POL(6(x_1)) = 1
   POL(7(x_1)) = x_1
   POL(8(x_1)) = 1 + x_1
   POL(9(x_1)) = 1 + x_1

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

   2(6(x1)) -> 4(3(x1))


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

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

   3(1(x1)) -> 4(1(x1))
   3(5(x1)) -> 8(9(7(x1)))
   3(8(x1)) -> 3(2(7(x1)))
   3(9(x1)) -> 9(3(x1))
   9(x1) -> 3(2(3(x1)))
   7(1(x1)) -> 6(9(x1))
   7(5(x1)) -> 1(0(x1))
   2(6(x1)) -> 4(3(x1))
   9(x1) -> 5(0(2(x1)))
   8(4(x1)) -> 6(x1)
   8(8(4(x1))) -> 1(9(x1))

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

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

(27)
YES

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

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

   5^1(9(x1)) -> 5^1(x1)

The TRS R consists of the following rules:

   3(1(x1)) -> 4(1(x1))
   5(9(x1)) -> 2(6(5(x1)))
   3(5(x1)) -> 8(9(7(x1)))
   9(x1) -> 3(2(3(x1)))
   8(4(x1)) -> 6(x1)
   2(6(x1)) -> 4(3(x1))
   3(8(x1)) -> 3(2(7(x1)))
   9(x1) -> 5(0(2(x1)))
   8(8(4(x1))) -> 1(9(x1))
   7(1(x1)) -> 6(9(x1))
   3(9(x1)) -> 9(3(x1))
   7(5(x1)) -> 1(0(x1))

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

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

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

   5^1(9(x1)) -> 5^1(x1)

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

(31) 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:
*5^1(9(x1)) -> 5^1(x1)
The graph contains the following edges 1 > 1


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

(32)
YES