/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, 74 ms]
(2) QDP
(3) DependencyGraphProof [EQUIVALENT, 0 ms]
(4) AND
    (5) QDP
        (6) UsableRulesProof [EQUIVALENT, 2 ms]
        (7) QDP
        (8) MRRProof [EQUIVALENT, 68 ms]
        (9) QDP
        (10) PisEmptyProof [EQUIVALENT, 0 ms]
        (11) YES
    (12) QDP
        (13) UsableRulesProof [EQUIVALENT, 1 ms]
        (14) QDP
        (15) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (16) YES


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

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

   c(0, x) -> x
   c(x, c(y, z)) -> c(+(x, y), z)
   +(0, 0) -> 0
   +(0, 1) -> 1
   +(0, 2) -> 2
   +(0, 3) -> 3
   +(0, 4) -> 4
   +(0, 5) -> 5
   +(0, 6) -> 6
   +(0, 7) -> 7
   +(0, 8) -> 8
   +(0, 9) -> 9
   +(1, 0) -> 1
   +(1, 1) -> 2
   +(1, 2) -> 3
   +(1, 3) -> 4
   +(1, 4) -> 5
   +(1, 5) -> 6
   +(1, 6) -> 7
   +(1, 7) -> 8
   +(1, 8) -> 9
   +(1, 9) -> c(1, 0)
   +(2, 0) -> 2
   +(2, 1) -> 3
   +(2, 2) -> 4
   +(2, 3) -> 5
   +(2, 4) -> 6
   +(2, 5) -> 7
   +(2, 6) -> 8
   +(2, 7) -> 9
   +(2, 8) -> c(1, 0)
   +(2, 9) -> c(1, 1)
   +(3, 0) -> 3
   +(3, 1) -> 4
   +(3, 2) -> 5
   +(3, 3) -> 6
   +(3, 4) -> 7
   +(3, 5) -> 8
   +(3, 6) -> 9
   +(3, 7) -> c(1, 0)
   +(3, 8) -> c(1, 1)
   +(3, 9) -> c(1, 2)
   +(4, 0) -> 4
   +(4, 1) -> 5
   +(4, 2) -> 6
   +(4, 3) -> 7
   +(4, 4) -> 8
   +(4, 5) -> 9
   +(4, 6) -> c(1, 0)
   +(4, 7) -> c(1, 1)
   +(4, 8) -> c(1, 2)
   +(4, 9) -> c(1, 3)
   +(5, 0) -> 5
   +(5, 1) -> 6
   +(5, 2) -> 7
   +(5, 3) -> 8
   +(5, 4) -> 9
   +(5, 5) -> c(1, 0)
   +(5, 6) -> c(1, 1)
   +(5, 7) -> c(1, 2)
   +(5, 8) -> c(1, 3)
   +(5, 9) -> c(1, 4)
   +(6, 0) -> 6
   +(6, 1) -> 7
   +(6, 2) -> 8
   +(6, 3) -> 9
   +(6, 4) -> c(1, 0)
   +(6, 5) -> c(1, 1)
   +(6, 6) -> c(1, 2)
   +(6, 7) -> c(1, 3)
   +(6, 8) -> c(1, 4)
   +(6, 9) -> c(1, 5)
   +(7, 0) -> 7
   +(7, 1) -> 8
   +(7, 2) -> 9
   +(7, 3) -> c(1, 0)
   +(7, 4) -> c(1, 1)
   +(7, 5) -> c(1, 2)
   +(7, 6) -> c(1, 3)
   +(7, 7) -> c(1, 4)
   +(7, 8) -> c(1, 5)
   +(7, 9) -> c(1, 6)
   +(8, 0) -> 8
   +(8, 1) -> 9
   +(8, 2) -> c(1, 0)
   +(8, 3) -> c(1, 1)
   +(8, 4) -> c(1, 2)
   +(8, 5) -> c(1, 3)
   +(8, 6) -> c(1, 4)
   +(8, 7) -> c(1, 5)
   +(8, 8) -> c(1, 6)
   +(8, 9) -> c(1, 7)
   +(9, 0) -> 9
   +(9, 1) -> c(1, 0)
   +(9, 2) -> c(1, 1)
   +(9, 3) -> c(1, 2)
   +(9, 4) -> c(1, 3)
   +(9, 5) -> c(1, 4)
   +(9, 6) -> c(1, 5)
   +(9, 7) -> c(1, 6)
   +(9, 8) -> c(1, 7)
   +(9, 9) -> c(1, 8)
   +(x, c(y, z)) -> c(y, +(x, z))
   +(c(x, y), z) -> c(x, +(y, z))
   *(0, 0) -> 0
   *(0, 1) -> 0
   *(0, 2) -> 0
   *(0, 3) -> 0
   *(0, 4) -> 0
   *(0, 5) -> 0
   *(0, 6) -> 0
   *(0, 7) -> 0
   *(0, 8) -> 0
   *(0, 9) -> 0
   *(1, 0) -> 0
   *(1, 1) -> 1
   *(1, 2) -> 2
   *(1, 3) -> 3
   *(1, 4) -> 4
   *(1, 5) -> 5
   *(1, 6) -> 6
   *(1, 7) -> 7
   *(1, 8) -> 8
   *(1, 9) -> 9
   *(2, 0) -> 0
   *(2, 1) -> 2
   *(2, 2) -> 4
   *(2, 3) -> 6
   *(2, 4) -> 8
   *(2, 5) -> c(1, 0)
   *(2, 6) -> c(1, 2)
   *(2, 7) -> c(1, 4)
   *(2, 8) -> c(1, 6)
   *(2, 9) -> c(1, 8)
   *(3, 0) -> 0
   *(3, 1) -> 3
   *(3, 2) -> 6
   *(3, 3) -> 9
   *(3, 4) -> c(1, 2)
   *(3, 5) -> c(1, 5)
   *(3, 6) -> c(1, 8)
   *(3, 7) -> c(2, 1)
   *(3, 8) -> c(2, 4)
   *(3, 9) -> c(2, 7)
   *(4, 0) -> 0
   *(4, 1) -> 4
   *(4, 2) -> 8
   *(4, 3) -> c(1, 2)
   *(4, 4) -> c(1, 6)
   *(4, 5) -> c(2, 0)
   *(4, 6) -> c(2, 4)
   *(4, 7) -> c(2, 8)
   *(4, 8) -> c(3, 2)
   *(4, 9) -> c(3, 6)
   *(5, 0) -> 0
   *(5, 1) -> 5
   *(5, 2) -> c(1, 0)
   *(5, 3) -> c(1, 5)
   *(5, 4) -> c(2, 0)
   *(5, 5) -> c(2, 5)
   *(5, 6) -> c(3, 0)
   *(5, 7) -> c(3, 5)
   *(5, 8) -> c(4, 0)
   *(5, 9) -> c(4, 5)
   *(6, 0) -> 0
   *(6, 1) -> 6
   *(6, 2) -> c(1, 2)
   *(6, 3) -> c(1, 8)
   *(6, 4) -> c(2, 4)
   *(6, 5) -> c(3, 0)
   *(6, 6) -> c(3, 6)
   *(6, 7) -> c(4, 2)
   *(6, 8) -> c(4, 8)
   *(6, 9) -> c(5, 4)
   *(7, 0) -> 0
   *(7, 1) -> 7
   *(7, 2) -> c(1, 4)
   *(7, 3) -> c(2, 1)
   *(7, 4) -> c(2, 8)
   *(7, 5) -> c(3, 5)
   *(7, 6) -> c(4, 2)
   *(7, 7) -> c(4, 9)
   *(7, 8) -> c(5, 6)
   *(7, 9) -> c(6, 3)
   *(8, 0) -> 0
   *(8, 1) -> 8
   *(8, 2) -> c(1, 8)
   *(8, 3) -> c(2, 4)
   *(8, 4) -> c(3, 2)
   *(8, 5) -> c(4, 0)
   *(8, 6) -> c(4, 8)
   *(8, 7) -> c(5, 6)
   *(8, 8) -> c(6, 4)
   *(8, 9) -> c(7, 2)
   *(9, 0) -> 0
   *(9, 1) -> 9
   *(9, 2) -> c(1, 8)
   *(9, 3) -> c(2, 7)
   *(9, 4) -> c(3, 6)
   *(9, 5) -> c(4, 5)
   *(9, 6) -> c(5, 4)
   *(9, 7) -> c(6, 3)
   *(9, 8) -> c(7, 2)
   *(9, 9) -> c(8, 1)
   *(x, c(y, z)) -> c(*(x, y), *(x, z))
   *(c(x, y), z) -> c(*(x, z), *(y, z))

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:

   C(x, c(y, z)) -> C(+(x, y), z)
   C(x, c(y, z)) -> +^1(x, y)
   +^1(1, 9) -> C(1, 0)
   +^1(2, 8) -> C(1, 0)
   +^1(2, 9) -> C(1, 1)
   +^1(3, 7) -> C(1, 0)
   +^1(3, 8) -> C(1, 1)
   +^1(3, 9) -> C(1, 2)
   +^1(4, 6) -> C(1, 0)
   +^1(4, 7) -> C(1, 1)
   +^1(4, 8) -> C(1, 2)
   +^1(4, 9) -> C(1, 3)
   +^1(5, 5) -> C(1, 0)
   +^1(5, 6) -> C(1, 1)
   +^1(5, 7) -> C(1, 2)
   +^1(5, 8) -> C(1, 3)
   +^1(5, 9) -> C(1, 4)
   +^1(6, 4) -> C(1, 0)
   +^1(6, 5) -> C(1, 1)
   +^1(6, 6) -> C(1, 2)
   +^1(6, 7) -> C(1, 3)
   +^1(6, 8) -> C(1, 4)
   +^1(6, 9) -> C(1, 5)
   +^1(7, 3) -> C(1, 0)
   +^1(7, 4) -> C(1, 1)
   +^1(7, 5) -> C(1, 2)
   +^1(7, 6) -> C(1, 3)
   +^1(7, 7) -> C(1, 4)
   +^1(7, 8) -> C(1, 5)
   +^1(7, 9) -> C(1, 6)
   +^1(8, 2) -> C(1, 0)
   +^1(8, 3) -> C(1, 1)
   +^1(8, 4) -> C(1, 2)
   +^1(8, 5) -> C(1, 3)
   +^1(8, 6) -> C(1, 4)
   +^1(8, 7) -> C(1, 5)
   +^1(8, 8) -> C(1, 6)
   +^1(8, 9) -> C(1, 7)
   +^1(9, 1) -> C(1, 0)
   +^1(9, 2) -> C(1, 1)
   +^1(9, 3) -> C(1, 2)
   +^1(9, 4) -> C(1, 3)
   +^1(9, 5) -> C(1, 4)
   +^1(9, 6) -> C(1, 5)
   +^1(9, 7) -> C(1, 6)
   +^1(9, 8) -> C(1, 7)
   +^1(9, 9) -> C(1, 8)
   +^1(x, c(y, z)) -> C(y, +(x, z))
   +^1(x, c(y, z)) -> +^1(x, z)
   +^1(c(x, y), z) -> C(x, +(y, z))
   +^1(c(x, y), z) -> +^1(y, z)
   *^1(2, 5) -> C(1, 0)
   *^1(2, 6) -> C(1, 2)
   *^1(2, 7) -> C(1, 4)
   *^1(2, 8) -> C(1, 6)
   *^1(2, 9) -> C(1, 8)
   *^1(3, 4) -> C(1, 2)
   *^1(3, 5) -> C(1, 5)
   *^1(3, 6) -> C(1, 8)
   *^1(3, 7) -> C(2, 1)
   *^1(3, 8) -> C(2, 4)
   *^1(3, 9) -> C(2, 7)
   *^1(4, 3) -> C(1, 2)
   *^1(4, 4) -> C(1, 6)
   *^1(4, 5) -> C(2, 0)
   *^1(4, 6) -> C(2, 4)
   *^1(4, 7) -> C(2, 8)
   *^1(4, 8) -> C(3, 2)
   *^1(4, 9) -> C(3, 6)
   *^1(5, 2) -> C(1, 0)
   *^1(5, 3) -> C(1, 5)
   *^1(5, 4) -> C(2, 0)
   *^1(5, 5) -> C(2, 5)
   *^1(5, 6) -> C(3, 0)
   *^1(5, 7) -> C(3, 5)
   *^1(5, 8) -> C(4, 0)
   *^1(5, 9) -> C(4, 5)
   *^1(6, 2) -> C(1, 2)
   *^1(6, 3) -> C(1, 8)
   *^1(6, 4) -> C(2, 4)
   *^1(6, 5) -> C(3, 0)
   *^1(6, 6) -> C(3, 6)
   *^1(6, 7) -> C(4, 2)
   *^1(6, 8) -> C(4, 8)
   *^1(6, 9) -> C(5, 4)
   *^1(7, 2) -> C(1, 4)
   *^1(7, 3) -> C(2, 1)
   *^1(7, 4) -> C(2, 8)
   *^1(7, 5) -> C(3, 5)
   *^1(7, 6) -> C(4, 2)
   *^1(7, 7) -> C(4, 9)
   *^1(7, 8) -> C(5, 6)
   *^1(7, 9) -> C(6, 3)
   *^1(8, 2) -> C(1, 8)
   *^1(8, 3) -> C(2, 4)
   *^1(8, 4) -> C(3, 2)
   *^1(8, 5) -> C(4, 0)
   *^1(8, 6) -> C(4, 8)
   *^1(8, 7) -> C(5, 6)
   *^1(8, 8) -> C(6, 4)
   *^1(8, 9) -> C(7, 2)
   *^1(9, 2) -> C(1, 8)
   *^1(9, 3) -> C(2, 7)
   *^1(9, 4) -> C(3, 6)
   *^1(9, 5) -> C(4, 5)
   *^1(9, 6) -> C(5, 4)
   *^1(9, 7) -> C(6, 3)
   *^1(9, 8) -> C(7, 2)
   *^1(9, 9) -> C(8, 1)
   *^1(x, c(y, z)) -> C(*(x, y), *(x, z))
   *^1(x, c(y, z)) -> *^1(x, y)
   *^1(x, c(y, z)) -> *^1(x, z)
   *^1(c(x, y), z) -> C(*(x, z), *(y, z))
   *^1(c(x, y), z) -> *^1(x, z)
   *^1(c(x, y), z) -> *^1(y, z)

The TRS R consists of the following rules:

   c(0, x) -> x
   c(x, c(y, z)) -> c(+(x, y), z)
   +(0, 0) -> 0
   +(0, 1) -> 1
   +(0, 2) -> 2
   +(0, 3) -> 3
   +(0, 4) -> 4
   +(0, 5) -> 5
   +(0, 6) -> 6
   +(0, 7) -> 7
   +(0, 8) -> 8
   +(0, 9) -> 9
   +(1, 0) -> 1
   +(1, 1) -> 2
   +(1, 2) -> 3
   +(1, 3) -> 4
   +(1, 4) -> 5
   +(1, 5) -> 6
   +(1, 6) -> 7
   +(1, 7) -> 8
   +(1, 8) -> 9
   +(1, 9) -> c(1, 0)
   +(2, 0) -> 2
   +(2, 1) -> 3
   +(2, 2) -> 4
   +(2, 3) -> 5
   +(2, 4) -> 6
   +(2, 5) -> 7
   +(2, 6) -> 8
   +(2, 7) -> 9
   +(2, 8) -> c(1, 0)
   +(2, 9) -> c(1, 1)
   +(3, 0) -> 3
   +(3, 1) -> 4
   +(3, 2) -> 5
   +(3, 3) -> 6
   +(3, 4) -> 7
   +(3, 5) -> 8
   +(3, 6) -> 9
   +(3, 7) -> c(1, 0)
   +(3, 8) -> c(1, 1)
   +(3, 9) -> c(1, 2)
   +(4, 0) -> 4
   +(4, 1) -> 5
   +(4, 2) -> 6
   +(4, 3) -> 7
   +(4, 4) -> 8
   +(4, 5) -> 9
   +(4, 6) -> c(1, 0)
   +(4, 7) -> c(1, 1)
   +(4, 8) -> c(1, 2)
   +(4, 9) -> c(1, 3)
   +(5, 0) -> 5
   +(5, 1) -> 6
   +(5, 2) -> 7
   +(5, 3) -> 8
   +(5, 4) -> 9
   +(5, 5) -> c(1, 0)
   +(5, 6) -> c(1, 1)
   +(5, 7) -> c(1, 2)
   +(5, 8) -> c(1, 3)
   +(5, 9) -> c(1, 4)
   +(6, 0) -> 6
   +(6, 1) -> 7
   +(6, 2) -> 8
   +(6, 3) -> 9
   +(6, 4) -> c(1, 0)
   +(6, 5) -> c(1, 1)
   +(6, 6) -> c(1, 2)
   +(6, 7) -> c(1, 3)
   +(6, 8) -> c(1, 4)
   +(6, 9) -> c(1, 5)
   +(7, 0) -> 7
   +(7, 1) -> 8
   +(7, 2) -> 9
   +(7, 3) -> c(1, 0)
   +(7, 4) -> c(1, 1)
   +(7, 5) -> c(1, 2)
   +(7, 6) -> c(1, 3)
   +(7, 7) -> c(1, 4)
   +(7, 8) -> c(1, 5)
   +(7, 9) -> c(1, 6)
   +(8, 0) -> 8
   +(8, 1) -> 9
   +(8, 2) -> c(1, 0)
   +(8, 3) -> c(1, 1)
   +(8, 4) -> c(1, 2)
   +(8, 5) -> c(1, 3)
   +(8, 6) -> c(1, 4)
   +(8, 7) -> c(1, 5)
   +(8, 8) -> c(1, 6)
   +(8, 9) -> c(1, 7)
   +(9, 0) -> 9
   +(9, 1) -> c(1, 0)
   +(9, 2) -> c(1, 1)
   +(9, 3) -> c(1, 2)
   +(9, 4) -> c(1, 3)
   +(9, 5) -> c(1, 4)
   +(9, 6) -> c(1, 5)
   +(9, 7) -> c(1, 6)
   +(9, 8) -> c(1, 7)
   +(9, 9) -> c(1, 8)
   +(x, c(y, z)) -> c(y, +(x, z))
   +(c(x, y), z) -> c(x, +(y, z))
   *(0, 0) -> 0
   *(0, 1) -> 0
   *(0, 2) -> 0
   *(0, 3) -> 0
   *(0, 4) -> 0
   *(0, 5) -> 0
   *(0, 6) -> 0
   *(0, 7) -> 0
   *(0, 8) -> 0
   *(0, 9) -> 0
   *(1, 0) -> 0
   *(1, 1) -> 1
   *(1, 2) -> 2
   *(1, 3) -> 3
   *(1, 4) -> 4
   *(1, 5) -> 5
   *(1, 6) -> 6
   *(1, 7) -> 7
   *(1, 8) -> 8
   *(1, 9) -> 9
   *(2, 0) -> 0
   *(2, 1) -> 2
   *(2, 2) -> 4
   *(2, 3) -> 6
   *(2, 4) -> 8
   *(2, 5) -> c(1, 0)
   *(2, 6) -> c(1, 2)
   *(2, 7) -> c(1, 4)
   *(2, 8) -> c(1, 6)
   *(2, 9) -> c(1, 8)
   *(3, 0) -> 0
   *(3, 1) -> 3
   *(3, 2) -> 6
   *(3, 3) -> 9
   *(3, 4) -> c(1, 2)
   *(3, 5) -> c(1, 5)
   *(3, 6) -> c(1, 8)
   *(3, 7) -> c(2, 1)
   *(3, 8) -> c(2, 4)
   *(3, 9) -> c(2, 7)
   *(4, 0) -> 0
   *(4, 1) -> 4
   *(4, 2) -> 8
   *(4, 3) -> c(1, 2)
   *(4, 4) -> c(1, 6)
   *(4, 5) -> c(2, 0)
   *(4, 6) -> c(2, 4)
   *(4, 7) -> c(2, 8)
   *(4, 8) -> c(3, 2)
   *(4, 9) -> c(3, 6)
   *(5, 0) -> 0
   *(5, 1) -> 5
   *(5, 2) -> c(1, 0)
   *(5, 3) -> c(1, 5)
   *(5, 4) -> c(2, 0)
   *(5, 5) -> c(2, 5)
   *(5, 6) -> c(3, 0)
   *(5, 7) -> c(3, 5)
   *(5, 8) -> c(4, 0)
   *(5, 9) -> c(4, 5)
   *(6, 0) -> 0
   *(6, 1) -> 6
   *(6, 2) -> c(1, 2)
   *(6, 3) -> c(1, 8)
   *(6, 4) -> c(2, 4)
   *(6, 5) -> c(3, 0)
   *(6, 6) -> c(3, 6)
   *(6, 7) -> c(4, 2)
   *(6, 8) -> c(4, 8)
   *(6, 9) -> c(5, 4)
   *(7, 0) -> 0
   *(7, 1) -> 7
   *(7, 2) -> c(1, 4)
   *(7, 3) -> c(2, 1)
   *(7, 4) -> c(2, 8)
   *(7, 5) -> c(3, 5)
   *(7, 6) -> c(4, 2)
   *(7, 7) -> c(4, 9)
   *(7, 8) -> c(5, 6)
   *(7, 9) -> c(6, 3)
   *(8, 0) -> 0
   *(8, 1) -> 8
   *(8, 2) -> c(1, 8)
   *(8, 3) -> c(2, 4)
   *(8, 4) -> c(3, 2)
   *(8, 5) -> c(4, 0)
   *(8, 6) -> c(4, 8)
   *(8, 7) -> c(5, 6)
   *(8, 8) -> c(6, 4)
   *(8, 9) -> c(7, 2)
   *(9, 0) -> 0
   *(9, 1) -> 9
   *(9, 2) -> c(1, 8)
   *(9, 3) -> c(2, 7)
   *(9, 4) -> c(3, 6)
   *(9, 5) -> c(4, 5)
   *(9, 6) -> c(5, 4)
   *(9, 7) -> c(6, 3)
   *(9, 8) -> c(7, 2)
   *(9, 9) -> c(8, 1)
   *(x, c(y, z)) -> c(*(x, y), *(x, z))
   *(c(x, y), z) -> c(*(x, z), *(y, z))

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

(4)
Complex Obligation (AND)

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

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

   C(x, c(y, z)) -> +^1(x, y)
   +^1(x, c(y, z)) -> C(y, +(x, z))
   C(x, c(y, z)) -> C(+(x, y), z)
   +^1(x, c(y, z)) -> +^1(x, z)
   +^1(c(x, y), z) -> C(x, +(y, z))
   +^1(c(x, y), z) -> +^1(y, z)

The TRS R consists of the following rules:

   c(0, x) -> x
   c(x, c(y, z)) -> c(+(x, y), z)
   +(0, 0) -> 0
   +(0, 1) -> 1
   +(0, 2) -> 2
   +(0, 3) -> 3
   +(0, 4) -> 4
   +(0, 5) -> 5
   +(0, 6) -> 6
   +(0, 7) -> 7
   +(0, 8) -> 8
   +(0, 9) -> 9
   +(1, 0) -> 1
   +(1, 1) -> 2
   +(1, 2) -> 3
   +(1, 3) -> 4
   +(1, 4) -> 5
   +(1, 5) -> 6
   +(1, 6) -> 7
   +(1, 7) -> 8
   +(1, 8) -> 9
   +(1, 9) -> c(1, 0)
   +(2, 0) -> 2
   +(2, 1) -> 3
   +(2, 2) -> 4
   +(2, 3) -> 5
   +(2, 4) -> 6
   +(2, 5) -> 7
   +(2, 6) -> 8
   +(2, 7) -> 9
   +(2, 8) -> c(1, 0)
   +(2, 9) -> c(1, 1)
   +(3, 0) -> 3
   +(3, 1) -> 4
   +(3, 2) -> 5
   +(3, 3) -> 6
   +(3, 4) -> 7
   +(3, 5) -> 8
   +(3, 6) -> 9
   +(3, 7) -> c(1, 0)
   +(3, 8) -> c(1, 1)
   +(3, 9) -> c(1, 2)
   +(4, 0) -> 4
   +(4, 1) -> 5
   +(4, 2) -> 6
   +(4, 3) -> 7
   +(4, 4) -> 8
   +(4, 5) -> 9
   +(4, 6) -> c(1, 0)
   +(4, 7) -> c(1, 1)
   +(4, 8) -> c(1, 2)
   +(4, 9) -> c(1, 3)
   +(5, 0) -> 5
   +(5, 1) -> 6
   +(5, 2) -> 7
   +(5, 3) -> 8
   +(5, 4) -> 9
   +(5, 5) -> c(1, 0)
   +(5, 6) -> c(1, 1)
   +(5, 7) -> c(1, 2)
   +(5, 8) -> c(1, 3)
   +(5, 9) -> c(1, 4)
   +(6, 0) -> 6
   +(6, 1) -> 7
   +(6, 2) -> 8
   +(6, 3) -> 9
   +(6, 4) -> c(1, 0)
   +(6, 5) -> c(1, 1)
   +(6, 6) -> c(1, 2)
   +(6, 7) -> c(1, 3)
   +(6, 8) -> c(1, 4)
   +(6, 9) -> c(1, 5)
   +(7, 0) -> 7
   +(7, 1) -> 8
   +(7, 2) -> 9
   +(7, 3) -> c(1, 0)
   +(7, 4) -> c(1, 1)
   +(7, 5) -> c(1, 2)
   +(7, 6) -> c(1, 3)
   +(7, 7) -> c(1, 4)
   +(7, 8) -> c(1, 5)
   +(7, 9) -> c(1, 6)
   +(8, 0) -> 8
   +(8, 1) -> 9
   +(8, 2) -> c(1, 0)
   +(8, 3) -> c(1, 1)
   +(8, 4) -> c(1, 2)
   +(8, 5) -> c(1, 3)
   +(8, 6) -> c(1, 4)
   +(8, 7) -> c(1, 5)
   +(8, 8) -> c(1, 6)
   +(8, 9) -> c(1, 7)
   +(9, 0) -> 9
   +(9, 1) -> c(1, 0)
   +(9, 2) -> c(1, 1)
   +(9, 3) -> c(1, 2)
   +(9, 4) -> c(1, 3)
   +(9, 5) -> c(1, 4)
   +(9, 6) -> c(1, 5)
   +(9, 7) -> c(1, 6)
   +(9, 8) -> c(1, 7)
   +(9, 9) -> c(1, 8)
   +(x, c(y, z)) -> c(y, +(x, z))
   +(c(x, y), z) -> c(x, +(y, z))
   *(0, 0) -> 0
   *(0, 1) -> 0
   *(0, 2) -> 0
   *(0, 3) -> 0
   *(0, 4) -> 0
   *(0, 5) -> 0
   *(0, 6) -> 0
   *(0, 7) -> 0
   *(0, 8) -> 0
   *(0, 9) -> 0
   *(1, 0) -> 0
   *(1, 1) -> 1
   *(1, 2) -> 2
   *(1, 3) -> 3
   *(1, 4) -> 4
   *(1, 5) -> 5
   *(1, 6) -> 6
   *(1, 7) -> 7
   *(1, 8) -> 8
   *(1, 9) -> 9
   *(2, 0) -> 0
   *(2, 1) -> 2
   *(2, 2) -> 4
   *(2, 3) -> 6
   *(2, 4) -> 8
   *(2, 5) -> c(1, 0)
   *(2, 6) -> c(1, 2)
   *(2, 7) -> c(1, 4)
   *(2, 8) -> c(1, 6)
   *(2, 9) -> c(1, 8)
   *(3, 0) -> 0
   *(3, 1) -> 3
   *(3, 2) -> 6
   *(3, 3) -> 9
   *(3, 4) -> c(1, 2)
   *(3, 5) -> c(1, 5)
   *(3, 6) -> c(1, 8)
   *(3, 7) -> c(2, 1)
   *(3, 8) -> c(2, 4)
   *(3, 9) -> c(2, 7)
   *(4, 0) -> 0
   *(4, 1) -> 4
   *(4, 2) -> 8
   *(4, 3) -> c(1, 2)
   *(4, 4) -> c(1, 6)
   *(4, 5) -> c(2, 0)
   *(4, 6) -> c(2, 4)
   *(4, 7) -> c(2, 8)
   *(4, 8) -> c(3, 2)
   *(4, 9) -> c(3, 6)
   *(5, 0) -> 0
   *(5, 1) -> 5
   *(5, 2) -> c(1, 0)
   *(5, 3) -> c(1, 5)
   *(5, 4) -> c(2, 0)
   *(5, 5) -> c(2, 5)
   *(5, 6) -> c(3, 0)
   *(5, 7) -> c(3, 5)
   *(5, 8) -> c(4, 0)
   *(5, 9) -> c(4, 5)
   *(6, 0) -> 0
   *(6, 1) -> 6
   *(6, 2) -> c(1, 2)
   *(6, 3) -> c(1, 8)
   *(6, 4) -> c(2, 4)
   *(6, 5) -> c(3, 0)
   *(6, 6) -> c(3, 6)
   *(6, 7) -> c(4, 2)
   *(6, 8) -> c(4, 8)
   *(6, 9) -> c(5, 4)
   *(7, 0) -> 0
   *(7, 1) -> 7
   *(7, 2) -> c(1, 4)
   *(7, 3) -> c(2, 1)
   *(7, 4) -> c(2, 8)
   *(7, 5) -> c(3, 5)
   *(7, 6) -> c(4, 2)
   *(7, 7) -> c(4, 9)
   *(7, 8) -> c(5, 6)
   *(7, 9) -> c(6, 3)
   *(8, 0) -> 0
   *(8, 1) -> 8
   *(8, 2) -> c(1, 8)
   *(8, 3) -> c(2, 4)
   *(8, 4) -> c(3, 2)
   *(8, 5) -> c(4, 0)
   *(8, 6) -> c(4, 8)
   *(8, 7) -> c(5, 6)
   *(8, 8) -> c(6, 4)
   *(8, 9) -> c(7, 2)
   *(9, 0) -> 0
   *(9, 1) -> 9
   *(9, 2) -> c(1, 8)
   *(9, 3) -> c(2, 7)
   *(9, 4) -> c(3, 6)
   *(9, 5) -> c(4, 5)
   *(9, 6) -> c(5, 4)
   *(9, 7) -> c(6, 3)
   *(9, 8) -> c(7, 2)
   *(9, 9) -> c(8, 1)
   *(x, c(y, z)) -> c(*(x, y), *(x, z))
   *(c(x, y), z) -> c(*(x, z), *(y, z))

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:

   C(x, c(y, z)) -> +^1(x, y)
   +^1(x, c(y, z)) -> C(y, +(x, z))
   C(x, c(y, z)) -> C(+(x, y), z)
   +^1(x, c(y, z)) -> +^1(x, z)
   +^1(c(x, y), z) -> C(x, +(y, z))
   +^1(c(x, y), z) -> +^1(y, z)

The TRS R consists of the following rules:

   +(0, 0) -> 0
   +(0, 1) -> 1
   +(0, 2) -> 2
   +(0, 3) -> 3
   +(0, 4) -> 4
   +(0, 5) -> 5
   +(0, 6) -> 6
   +(0, 7) -> 7
   +(0, 8) -> 8
   +(0, 9) -> 9
   +(1, 0) -> 1
   +(1, 1) -> 2
   +(1, 2) -> 3
   +(1, 3) -> 4
   +(1, 4) -> 5
   +(1, 5) -> 6
   +(1, 6) -> 7
   +(1, 7) -> 8
   +(1, 8) -> 9
   +(1, 9) -> c(1, 0)
   +(2, 0) -> 2
   +(2, 1) -> 3
   +(2, 2) -> 4
   +(2, 3) -> 5
   +(2, 4) -> 6
   +(2, 5) -> 7
   +(2, 6) -> 8
   +(2, 7) -> 9
   +(2, 8) -> c(1, 0)
   +(2, 9) -> c(1, 1)
   +(3, 0) -> 3
   +(3, 1) -> 4
   +(3, 2) -> 5
   +(3, 3) -> 6
   +(3, 4) -> 7
   +(3, 5) -> 8
   +(3, 6) -> 9
   +(3, 7) -> c(1, 0)
   +(3, 8) -> c(1, 1)
   +(3, 9) -> c(1, 2)
   +(4, 0) -> 4
   +(4, 1) -> 5
   +(4, 2) -> 6
   +(4, 3) -> 7
   +(4, 4) -> 8
   +(4, 5) -> 9
   +(4, 6) -> c(1, 0)
   +(4, 7) -> c(1, 1)
   +(4, 8) -> c(1, 2)
   +(4, 9) -> c(1, 3)
   +(5, 0) -> 5
   +(5, 1) -> 6
   +(5, 2) -> 7
   +(5, 3) -> 8
   +(5, 4) -> 9
   +(5, 5) -> c(1, 0)
   +(5, 6) -> c(1, 1)
   +(5, 7) -> c(1, 2)
   +(5, 8) -> c(1, 3)
   +(5, 9) -> c(1, 4)
   +(6, 0) -> 6
   +(6, 1) -> 7
   +(6, 2) -> 8
   +(6, 3) -> 9
   +(6, 4) -> c(1, 0)
   +(6, 5) -> c(1, 1)
   +(6, 6) -> c(1, 2)
   +(6, 7) -> c(1, 3)
   +(6, 8) -> c(1, 4)
   +(6, 9) -> c(1, 5)
   +(7, 0) -> 7
   +(7, 1) -> 8
   +(7, 2) -> 9
   +(7, 3) -> c(1, 0)
   +(7, 4) -> c(1, 1)
   +(7, 5) -> c(1, 2)
   +(7, 6) -> c(1, 3)
   +(7, 7) -> c(1, 4)
   +(7, 8) -> c(1, 5)
   +(7, 9) -> c(1, 6)
   +(8, 0) -> 8
   +(8, 1) -> 9
   +(8, 2) -> c(1, 0)
   +(8, 3) -> c(1, 1)
   +(8, 4) -> c(1, 2)
   +(8, 5) -> c(1, 3)
   +(8, 6) -> c(1, 4)
   +(8, 7) -> c(1, 5)
   +(8, 8) -> c(1, 6)
   +(8, 9) -> c(1, 7)
   +(9, 0) -> 9
   +(9, 1) -> c(1, 0)
   +(9, 2) -> c(1, 1)
   +(9, 3) -> c(1, 2)
   +(9, 4) -> c(1, 3)
   +(9, 5) -> c(1, 4)
   +(9, 6) -> c(1, 5)
   +(9, 7) -> c(1, 6)
   +(9, 8) -> c(1, 7)
   +(9, 9) -> c(1, 8)
   +(x, c(y, z)) -> c(y, +(x, z))
   +(c(x, y), z) -> c(x, +(y, z))
   c(0, x) -> x
   c(x, c(y, z)) -> c(+(x, y), z)

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

(8) MRRProof (EQUIVALENT)
By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.

Strictly oriented dependency pairs:

   C(x, c(y, z)) -> +^1(x, y)
   +^1(x, c(y, z)) -> C(y, +(x, z))
   C(x, c(y, z)) -> C(+(x, y), z)
   +^1(x, c(y, z)) -> +^1(x, z)
   +^1(c(x, y), z) -> C(x, +(y, z))
   +^1(c(x, y), z) -> +^1(y, z)

Strictly oriented rules of the TRS R:

   +(0, 0) -> 0
   +(0, 1) -> 1
   +(0, 2) -> 2
   +(0, 3) -> 3
   +(0, 4) -> 4
   +(0, 5) -> 5
   +(0, 6) -> 6
   +(0, 7) -> 7
   +(0, 8) -> 8
   +(0, 9) -> 9
   +(1, 0) -> 1
   +(1, 1) -> 2
   +(1, 2) -> 3
   +(1, 3) -> 4
   +(1, 4) -> 5
   +(1, 5) -> 6
   +(1, 6) -> 7
   +(1, 7) -> 8
   +(1, 8) -> 9
   +(1, 9) -> c(1, 0)
   +(2, 0) -> 2
   +(2, 1) -> 3
   +(2, 2) -> 4
   +(2, 3) -> 5
   +(2, 4) -> 6
   +(2, 5) -> 7
   +(2, 6) -> 8
   +(2, 7) -> 9
   +(2, 8) -> c(1, 0)
   +(2, 9) -> c(1, 1)
   +(3, 0) -> 3
   +(3, 1) -> 4
   +(3, 2) -> 5
   +(3, 3) -> 6
   +(3, 4) -> 7
   +(3, 5) -> 8
   +(3, 6) -> 9
   +(3, 7) -> c(1, 0)
   +(3, 8) -> c(1, 1)
   +(3, 9) -> c(1, 2)
   +(4, 0) -> 4
   +(4, 1) -> 5
   +(4, 2) -> 6
   +(4, 3) -> 7
   +(4, 4) -> 8
   +(4, 5) -> 9
   +(4, 6) -> c(1, 0)
   +(4, 7) -> c(1, 1)
   +(4, 8) -> c(1, 2)
   +(4, 9) -> c(1, 3)
   +(5, 0) -> 5
   +(5, 1) -> 6
   +(5, 2) -> 7
   +(5, 3) -> 8
   +(5, 4) -> 9
   +(5, 5) -> c(1, 0)
   +(5, 6) -> c(1, 1)
   +(5, 7) -> c(1, 2)
   +(5, 8) -> c(1, 3)
   +(5, 9) -> c(1, 4)
   +(6, 0) -> 6
   +(6, 1) -> 7
   +(6, 2) -> 8
   +(6, 3) -> 9
   +(6, 4) -> c(1, 0)
   +(6, 5) -> c(1, 1)
   +(6, 6) -> c(1, 2)
   +(6, 7) -> c(1, 3)
   +(6, 8) -> c(1, 4)
   +(6, 9) -> c(1, 5)
   +(7, 0) -> 7
   +(7, 1) -> 8
   +(7, 2) -> 9
   +(7, 3) -> c(1, 0)
   +(7, 4) -> c(1, 1)
   +(7, 5) -> c(1, 2)
   +(7, 6) -> c(1, 3)
   +(7, 7) -> c(1, 4)
   +(7, 8) -> c(1, 5)
   +(7, 9) -> c(1, 6)
   +(8, 0) -> 8
   +(8, 1) -> 9
   +(8, 2) -> c(1, 0)
   +(8, 3) -> c(1, 1)
   +(8, 4) -> c(1, 2)
   +(8, 5) -> c(1, 3)
   +(8, 6) -> c(1, 4)
   +(8, 7) -> c(1, 5)
   +(8, 8) -> c(1, 6)
   +(8, 9) -> c(1, 7)
   +(9, 0) -> 9
   +(9, 1) -> c(1, 0)
   +(9, 2) -> c(1, 1)
   +(9, 3) -> c(1, 2)
   +(9, 4) -> c(1, 3)
   +(9, 5) -> c(1, 4)
   +(9, 6) -> c(1, 5)
   +(9, 7) -> c(1, 6)
   +(9, 8) -> c(1, 7)
   +(9, 9) -> c(1, 8)
   +(x, c(y, z)) -> c(y, +(x, z))
   +(c(x, y), z) -> c(x, +(y, z))
   c(0, x) -> x
   c(x, c(y, z)) -> c(+(x, y), z)

Used ordering: Knuth-Bendix order [KBO] with precedence:1 > 2 > 7 > 9 > +_2 > c_2 > 4 > 8 > 0 > 6 > 5 > +^1_2 > 3 > C_2

and weight map:

   0=1
   1=5
   2=9
   3=6
   4=7
   5=8
   6=11
   7=12
   8=13
   9=14
   +_2=0
   c_2=5
   C_2=5
   +^1_2=0

The variable weight is 1

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

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

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

(11)
YES

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

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

   *^1(x, c(y, z)) -> *^1(x, z)
   *^1(x, c(y, z)) -> *^1(x, y)
   *^1(c(x, y), z) -> *^1(x, z)
   *^1(c(x, y), z) -> *^1(y, z)

The TRS R consists of the following rules:

   c(0, x) -> x
   c(x, c(y, z)) -> c(+(x, y), z)
   +(0, 0) -> 0
   +(0, 1) -> 1
   +(0, 2) -> 2
   +(0, 3) -> 3
   +(0, 4) -> 4
   +(0, 5) -> 5
   +(0, 6) -> 6
   +(0, 7) -> 7
   +(0, 8) -> 8
   +(0, 9) -> 9
   +(1, 0) -> 1
   +(1, 1) -> 2
   +(1, 2) -> 3
   +(1, 3) -> 4
   +(1, 4) -> 5
   +(1, 5) -> 6
   +(1, 6) -> 7
   +(1, 7) -> 8
   +(1, 8) -> 9
   +(1, 9) -> c(1, 0)
   +(2, 0) -> 2
   +(2, 1) -> 3
   +(2, 2) -> 4
   +(2, 3) -> 5
   +(2, 4) -> 6
   +(2, 5) -> 7
   +(2, 6) -> 8
   +(2, 7) -> 9
   +(2, 8) -> c(1, 0)
   +(2, 9) -> c(1, 1)
   +(3, 0) -> 3
   +(3, 1) -> 4
   +(3, 2) -> 5
   +(3, 3) -> 6
   +(3, 4) -> 7
   +(3, 5) -> 8
   +(3, 6) -> 9
   +(3, 7) -> c(1, 0)
   +(3, 8) -> c(1, 1)
   +(3, 9) -> c(1, 2)
   +(4, 0) -> 4
   +(4, 1) -> 5
   +(4, 2) -> 6
   +(4, 3) -> 7
   +(4, 4) -> 8
   +(4, 5) -> 9
   +(4, 6) -> c(1, 0)
   +(4, 7) -> c(1, 1)
   +(4, 8) -> c(1, 2)
   +(4, 9) -> c(1, 3)
   +(5, 0) -> 5
   +(5, 1) -> 6
   +(5, 2) -> 7
   +(5, 3) -> 8
   +(5, 4) -> 9
   +(5, 5) -> c(1, 0)
   +(5, 6) -> c(1, 1)
   +(5, 7) -> c(1, 2)
   +(5, 8) -> c(1, 3)
   +(5, 9) -> c(1, 4)
   +(6, 0) -> 6
   +(6, 1) -> 7
   +(6, 2) -> 8
   +(6, 3) -> 9
   +(6, 4) -> c(1, 0)
   +(6, 5) -> c(1, 1)
   +(6, 6) -> c(1, 2)
   +(6, 7) -> c(1, 3)
   +(6, 8) -> c(1, 4)
   +(6, 9) -> c(1, 5)
   +(7, 0) -> 7
   +(7, 1) -> 8
   +(7, 2) -> 9
   +(7, 3) -> c(1, 0)
   +(7, 4) -> c(1, 1)
   +(7, 5) -> c(1, 2)
   +(7, 6) -> c(1, 3)
   +(7, 7) -> c(1, 4)
   +(7, 8) -> c(1, 5)
   +(7, 9) -> c(1, 6)
   +(8, 0) -> 8
   +(8, 1) -> 9
   +(8, 2) -> c(1, 0)
   +(8, 3) -> c(1, 1)
   +(8, 4) -> c(1, 2)
   +(8, 5) -> c(1, 3)
   +(8, 6) -> c(1, 4)
   +(8, 7) -> c(1, 5)
   +(8, 8) -> c(1, 6)
   +(8, 9) -> c(1, 7)
   +(9, 0) -> 9
   +(9, 1) -> c(1, 0)
   +(9, 2) -> c(1, 1)
   +(9, 3) -> c(1, 2)
   +(9, 4) -> c(1, 3)
   +(9, 5) -> c(1, 4)
   +(9, 6) -> c(1, 5)
   +(9, 7) -> c(1, 6)
   +(9, 8) -> c(1, 7)
   +(9, 9) -> c(1, 8)
   +(x, c(y, z)) -> c(y, +(x, z))
   +(c(x, y), z) -> c(x, +(y, z))
   *(0, 0) -> 0
   *(0, 1) -> 0
   *(0, 2) -> 0
   *(0, 3) -> 0
   *(0, 4) -> 0
   *(0, 5) -> 0
   *(0, 6) -> 0
   *(0, 7) -> 0
   *(0, 8) -> 0
   *(0, 9) -> 0
   *(1, 0) -> 0
   *(1, 1) -> 1
   *(1, 2) -> 2
   *(1, 3) -> 3
   *(1, 4) -> 4
   *(1, 5) -> 5
   *(1, 6) -> 6
   *(1, 7) -> 7
   *(1, 8) -> 8
   *(1, 9) -> 9
   *(2, 0) -> 0
   *(2, 1) -> 2
   *(2, 2) -> 4
   *(2, 3) -> 6
   *(2, 4) -> 8
   *(2, 5) -> c(1, 0)
   *(2, 6) -> c(1, 2)
   *(2, 7) -> c(1, 4)
   *(2, 8) -> c(1, 6)
   *(2, 9) -> c(1, 8)
   *(3, 0) -> 0
   *(3, 1) -> 3
   *(3, 2) -> 6
   *(3, 3) -> 9
   *(3, 4) -> c(1, 2)
   *(3, 5) -> c(1, 5)
   *(3, 6) -> c(1, 8)
   *(3, 7) -> c(2, 1)
   *(3, 8) -> c(2, 4)
   *(3, 9) -> c(2, 7)
   *(4, 0) -> 0
   *(4, 1) -> 4
   *(4, 2) -> 8
   *(4, 3) -> c(1, 2)
   *(4, 4) -> c(1, 6)
   *(4, 5) -> c(2, 0)
   *(4, 6) -> c(2, 4)
   *(4, 7) -> c(2, 8)
   *(4, 8) -> c(3, 2)
   *(4, 9) -> c(3, 6)
   *(5, 0) -> 0
   *(5, 1) -> 5
   *(5, 2) -> c(1, 0)
   *(5, 3) -> c(1, 5)
   *(5, 4) -> c(2, 0)
   *(5, 5) -> c(2, 5)
   *(5, 6) -> c(3, 0)
   *(5, 7) -> c(3, 5)
   *(5, 8) -> c(4, 0)
   *(5, 9) -> c(4, 5)
   *(6, 0) -> 0
   *(6, 1) -> 6
   *(6, 2) -> c(1, 2)
   *(6, 3) -> c(1, 8)
   *(6, 4) -> c(2, 4)
   *(6, 5) -> c(3, 0)
   *(6, 6) -> c(3, 6)
   *(6, 7) -> c(4, 2)
   *(6, 8) -> c(4, 8)
   *(6, 9) -> c(5, 4)
   *(7, 0) -> 0
   *(7, 1) -> 7
   *(7, 2) -> c(1, 4)
   *(7, 3) -> c(2, 1)
   *(7, 4) -> c(2, 8)
   *(7, 5) -> c(3, 5)
   *(7, 6) -> c(4, 2)
   *(7, 7) -> c(4, 9)
   *(7, 8) -> c(5, 6)
   *(7, 9) -> c(6, 3)
   *(8, 0) -> 0
   *(8, 1) -> 8
   *(8, 2) -> c(1, 8)
   *(8, 3) -> c(2, 4)
   *(8, 4) -> c(3, 2)
   *(8, 5) -> c(4, 0)
   *(8, 6) -> c(4, 8)
   *(8, 7) -> c(5, 6)
   *(8, 8) -> c(6, 4)
   *(8, 9) -> c(7, 2)
   *(9, 0) -> 0
   *(9, 1) -> 9
   *(9, 2) -> c(1, 8)
   *(9, 3) -> c(2, 7)
   *(9, 4) -> c(3, 6)
   *(9, 5) -> c(4, 5)
   *(9, 6) -> c(5, 4)
   *(9, 7) -> c(6, 3)
   *(9, 8) -> c(7, 2)
   *(9, 9) -> c(8, 1)
   *(x, c(y, z)) -> c(*(x, y), *(x, z))
   *(c(x, y), z) -> c(*(x, z), *(y, z))

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:

   *^1(x, c(y, z)) -> *^1(x, z)
   *^1(x, c(y, z)) -> *^1(x, y)
   *^1(c(x, y), z) -> *^1(x, z)
   *^1(c(x, y), z) -> *^1(y, z)

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

(15) 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:
**^1(x, c(y, z)) -> *^1(x, z)
The graph contains the following edges 1 >= 1, 2 > 2


**^1(x, c(y, z)) -> *^1(x, y)
The graph contains the following edges 1 >= 1, 2 > 2


**^1(c(x, y), z) -> *^1(x, z)
The graph contains the following edges 1 > 1, 2 >= 2


**^1(c(x, y), z) -> *^1(y, z)
The graph contains the following edges 1 > 1, 2 >= 2


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

(16)
YES