Term Rewriting System R:
[x, y, z, l, l1, l2]
+(x, 0) -> x
+(0, x) -> x
+(s(x), s(y)) -> s(s(+(x, y)))
+(+(x, y), z) -> +(x, +(y, z))
*(x, 0) -> 0
*(0, x) -> 0
*(s(x), s(y)) -> s(+(*(x, y), +(x, y)))
*(*(x, y), z) -> *(x, *(y, z))
app(nil, l) -> l
app(cons(x, l1), l2) -> cons(x, app(l1, l2))
sum(nil) -> 0
sum(cons(x, l)) -> +(x, sum(l))
sum(app(l1, l2)) -> +(sum(l1), sum(l2))
prod(nil) -> s(0)
prod(cons(x, l)) -> *(x, prod(l))
prod(app(l1, l2)) -> *(prod(l1), prod(l2))

Innermost Termination of R to be shown.



   R
Dependency Pair Analysis



R contains the following Dependency Pairs:

+'(s(x), s(y)) -> +'(x, y)
+'(+(x, y), z) -> +'(x, +(y, z))
+'(+(x, y), z) -> +'(y, z)
*'(s(x), s(y)) -> +'(*(x, y), +(x, y))
*'(s(x), s(y)) -> *'(x, y)
*'(s(x), s(y)) -> +'(x, y)
*'(*(x, y), z) -> *'(x, *(y, z))
*'(*(x, y), z) -> *'(y, z)
APP(cons(x, l1), l2) -> APP(l1, l2)
SUM(cons(x, l)) -> +'(x, sum(l))
SUM(cons(x, l)) -> SUM(l)
SUM(app(l1, l2)) -> +'(sum(l1), sum(l2))
SUM(app(l1, l2)) -> SUM(l1)
SUM(app(l1, l2)) -> SUM(l2)
PROD(cons(x, l)) -> *'(x, prod(l))
PROD(cons(x, l)) -> PROD(l)
PROD(app(l1, l2)) -> *'(prod(l1), prod(l2))
PROD(app(l1, l2)) -> PROD(l1)
PROD(app(l1, l2)) -> PROD(l2)

Furthermore, R contains five SCCs.


   R
DPs
       →DP Problem 1
Polynomial Ordering
       →DP Problem 2
Polo
       →DP Problem 3
Polo
       →DP Problem 4
Polo
       →DP Problem 5
Polo


Dependency Pairs:

+'(+(x, y), z) -> +'(y, z)
+'(+(x, y), z) -> +'(x, +(y, z))
+'(s(x), s(y)) -> +'(x, y)


Rules:


+(x, 0) -> x
+(0, x) -> x
+(s(x), s(y)) -> s(s(+(x, y)))
+(+(x, y), z) -> +(x, +(y, z))
*(x, 0) -> 0
*(0, x) -> 0
*(s(x), s(y)) -> s(+(*(x, y), +(x, y)))
*(*(x, y), z) -> *(x, *(y, z))
app(nil, l) -> l
app(cons(x, l1), l2) -> cons(x, app(l1, l2))
sum(nil) -> 0
sum(cons(x, l)) -> +(x, sum(l))
sum(app(l1, l2)) -> +(sum(l1), sum(l2))
prod(nil) -> s(0)
prod(cons(x, l)) -> *(x, prod(l))
prod(app(l1, l2)) -> *(prod(l1), prod(l2))


Strategy:

innermost




The following dependency pairs can be strictly oriented:

+'(+(x, y), z) -> +'(y, z)
+'(+(x, y), z) -> +'(x, +(y, z))


There are no usable rules for innermost w.r.t. to the implicit AFS that need to be oriented.

Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(0)=  0  
  POL(s(x1))=  x1  
  POL(+(x1, x2))=  1 + x1 + x2  
  POL(+'(x1, x2))=  x1  

resulting in one new DP problem.



   R
DPs
       →DP Problem 1
Polo
           →DP Problem 6
Polynomial Ordering
       →DP Problem 2
Polo
       →DP Problem 3
Polo
       →DP Problem 4
Polo
       →DP Problem 5
Polo


Dependency Pair:

+'(s(x), s(y)) -> +'(x, y)


Rules:


+(x, 0) -> x
+(0, x) -> x
+(s(x), s(y)) -> s(s(+(x, y)))
+(+(x, y), z) -> +(x, +(y, z))
*(x, 0) -> 0
*(0, x) -> 0
*(s(x), s(y)) -> s(+(*(x, y), +(x, y)))
*(*(x, y), z) -> *(x, *(y, z))
app(nil, l) -> l
app(cons(x, l1), l2) -> cons(x, app(l1, l2))
sum(nil) -> 0
sum(cons(x, l)) -> +(x, sum(l))
sum(app(l1, l2)) -> +(sum(l1), sum(l2))
prod(nil) -> s(0)
prod(cons(x, l)) -> *(x, prod(l))
prod(app(l1, l2)) -> *(prod(l1), prod(l2))


Strategy:

innermost




The following dependency pair can be strictly oriented:

+'(s(x), s(y)) -> +'(x, y)


There are no usable rules for innermost w.r.t. to the implicit AFS that need to be oriented.

Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(s(x1))=  1 + x1  
  POL(+'(x1, x2))=  x1  

resulting in one new DP problem.



   R
DPs
       →DP Problem 1
Polo
           →DP Problem 6
Polo
             ...
               →DP Problem 7
Dependency Graph
       →DP Problem 2
Polo
       →DP Problem 3
Polo
       →DP Problem 4
Polo
       →DP Problem 5
Polo


Dependency Pair:


Rules:


+(x, 0) -> x
+(0, x) -> x
+(s(x), s(y)) -> s(s(+(x, y)))
+(+(x, y), z) -> +(x, +(y, z))
*(x, 0) -> 0
*(0, x) -> 0
*(s(x), s(y)) -> s(+(*(x, y), +(x, y)))
*(*(x, y), z) -> *(x, *(y, z))
app(nil, l) -> l
app(cons(x, l1), l2) -> cons(x, app(l1, l2))
sum(nil) -> 0
sum(cons(x, l)) -> +(x, sum(l))
sum(app(l1, l2)) -> +(sum(l1), sum(l2))
prod(nil) -> s(0)
prod(cons(x, l)) -> *(x, prod(l))
prod(app(l1, l2)) -> *(prod(l1), prod(l2))


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.


   R
DPs
       →DP Problem 1
Polo
       →DP Problem 2
Polynomial Ordering
       →DP Problem 3
Polo
       →DP Problem 4
Polo
       →DP Problem 5
Polo


Dependency Pair:

APP(cons(x, l1), l2) -> APP(l1, l2)


Rules:


+(x, 0) -> x
+(0, x) -> x
+(s(x), s(y)) -> s(s(+(x, y)))
+(+(x, y), z) -> +(x, +(y, z))
*(x, 0) -> 0
*(0, x) -> 0
*(s(x), s(y)) -> s(+(*(x, y), +(x, y)))
*(*(x, y), z) -> *(x, *(y, z))
app(nil, l) -> l
app(cons(x, l1), l2) -> cons(x, app(l1, l2))
sum(nil) -> 0
sum(cons(x, l)) -> +(x, sum(l))
sum(app(l1, l2)) -> +(sum(l1), sum(l2))
prod(nil) -> s(0)
prod(cons(x, l)) -> *(x, prod(l))
prod(app(l1, l2)) -> *(prod(l1), prod(l2))


Strategy:

innermost




The following dependency pair can be strictly oriented:

APP(cons(x, l1), l2) -> APP(l1, l2)


There are no usable rules for innermost w.r.t. to the implicit AFS that need to be oriented.

Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(cons(x1, x2))=  1 + x2  
  POL(APP(x1, x2))=  x1  

resulting in one new DP problem.



   R
DPs
       →DP Problem 1
Polo
       →DP Problem 2
Polo
           →DP Problem 8
Dependency Graph
       →DP Problem 3
Polo
       →DP Problem 4
Polo
       →DP Problem 5
Polo


Dependency Pair:


Rules:


+(x, 0) -> x
+(0, x) -> x
+(s(x), s(y)) -> s(s(+(x, y)))
+(+(x, y), z) -> +(x, +(y, z))
*(x, 0) -> 0
*(0, x) -> 0
*(s(x), s(y)) -> s(+(*(x, y), +(x, y)))
*(*(x, y), z) -> *(x, *(y, z))
app(nil, l) -> l
app(cons(x, l1), l2) -> cons(x, app(l1, l2))
sum(nil) -> 0
sum(cons(x, l)) -> +(x, sum(l))
sum(app(l1, l2)) -> +(sum(l1), sum(l2))
prod(nil) -> s(0)
prod(cons(x, l)) -> *(x, prod(l))
prod(app(l1, l2)) -> *(prod(l1), prod(l2))


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.


   R
DPs
       →DP Problem 1
Polo
       →DP Problem 2
Polo
       →DP Problem 3
Polynomial Ordering
       →DP Problem 4
Polo
       →DP Problem 5
Polo


Dependency Pairs:

*'(*(x, y), z) -> *'(y, z)
*'(*(x, y), z) -> *'(x, *(y, z))
*'(s(x), s(y)) -> *'(x, y)


Rules:


+(x, 0) -> x
+(0, x) -> x
+(s(x), s(y)) -> s(s(+(x, y)))
+(+(x, y), z) -> +(x, +(y, z))
*(x, 0) -> 0
*(0, x) -> 0
*(s(x), s(y)) -> s(+(*(x, y), +(x, y)))
*(*(x, y), z) -> *(x, *(y, z))
app(nil, l) -> l
app(cons(x, l1), l2) -> cons(x, app(l1, l2))
sum(nil) -> 0
sum(cons(x, l)) -> +(x, sum(l))
sum(app(l1, l2)) -> +(sum(l1), sum(l2))
prod(nil) -> s(0)
prod(cons(x, l)) -> *(x, prod(l))
prod(app(l1, l2)) -> *(prod(l1), prod(l2))


Strategy:

innermost




The following dependency pairs can be strictly oriented:

*'(*(x, y), z) -> *'(y, z)
*'(*(x, y), z) -> *'(x, *(y, z))


There are no usable rules for innermost w.r.t. to the implicit AFS that need to be oriented.

Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(0)=  0  
  POL(*'(x1, x2))=  x1  
  POL(*(x1, x2))=  1 + x1 + x2  
  POL(s(x1))=  x1  
  POL(+(x1, x2))=  0  

resulting in one new DP problem.



   R
DPs
       →DP Problem 1
Polo
       →DP Problem 2
Polo
       →DP Problem 3
Polo
           →DP Problem 9
Polynomial Ordering
       →DP Problem 4
Polo
       →DP Problem 5
Polo


Dependency Pair:

*'(s(x), s(y)) -> *'(x, y)


Rules:


+(x, 0) -> x
+(0, x) -> x
+(s(x), s(y)) -> s(s(+(x, y)))
+(+(x, y), z) -> +(x, +(y, z))
*(x, 0) -> 0
*(0, x) -> 0
*(s(x), s(y)) -> s(+(*(x, y), +(x, y)))
*(*(x, y), z) -> *(x, *(y, z))
app(nil, l) -> l
app(cons(x, l1), l2) -> cons(x, app(l1, l2))
sum(nil) -> 0
sum(cons(x, l)) -> +(x, sum(l))
sum(app(l1, l2)) -> +(sum(l1), sum(l2))
prod(nil) -> s(0)
prod(cons(x, l)) -> *(x, prod(l))
prod(app(l1, l2)) -> *(prod(l1), prod(l2))


Strategy:

innermost




The following dependency pair can be strictly oriented:

*'(s(x), s(y)) -> *'(x, y)


There are no usable rules for innermost w.r.t. to the implicit AFS that need to be oriented.

Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(*'(x1, x2))=  x1  
  POL(s(x1))=  1 + x1  

resulting in one new DP problem.



   R
DPs
       →DP Problem 1
Polo
       →DP Problem 2
Polo
       →DP Problem 3
Polo
           →DP Problem 9
Polo
             ...
               →DP Problem 10
Dependency Graph
       →DP Problem 4
Polo
       →DP Problem 5
Polo


Dependency Pair:


Rules:


+(x, 0) -> x
+(0, x) -> x
+(s(x), s(y)) -> s(s(+(x, y)))
+(+(x, y), z) -> +(x, +(y, z))
*(x, 0) -> 0
*(0, x) -> 0
*(s(x), s(y)) -> s(+(*(x, y), +(x, y)))
*(*(x, y), z) -> *(x, *(y, z))
app(nil, l) -> l
app(cons(x, l1), l2) -> cons(x, app(l1, l2))
sum(nil) -> 0
sum(cons(x, l)) -> +(x, sum(l))
sum(app(l1, l2)) -> +(sum(l1), sum(l2))
prod(nil) -> s(0)
prod(cons(x, l)) -> *(x, prod(l))
prod(app(l1, l2)) -> *(prod(l1), prod(l2))


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.


   R
DPs
       →DP Problem 1
Polo
       →DP Problem 2
Polo
       →DP Problem 3
Polo
       →DP Problem 4
Polynomial Ordering
       →DP Problem 5
Polo


Dependency Pairs:

SUM(app(l1, l2)) -> SUM(l2)
SUM(app(l1, l2)) -> SUM(l1)
SUM(cons(x, l)) -> SUM(l)


Rules:


+(x, 0) -> x
+(0, x) -> x
+(s(x), s(y)) -> s(s(+(x, y)))
+(+(x, y), z) -> +(x, +(y, z))
*(x, 0) -> 0
*(0, x) -> 0
*(s(x), s(y)) -> s(+(*(x, y), +(x, y)))
*(*(x, y), z) -> *(x, *(y, z))
app(nil, l) -> l
app(cons(x, l1), l2) -> cons(x, app(l1, l2))
sum(nil) -> 0
sum(cons(x, l)) -> +(x, sum(l))
sum(app(l1, l2)) -> +(sum(l1), sum(l2))
prod(nil) -> s(0)
prod(cons(x, l)) -> *(x, prod(l))
prod(app(l1, l2)) -> *(prod(l1), prod(l2))


Strategy:

innermost




The following dependency pairs can be strictly oriented:

SUM(app(l1, l2)) -> SUM(l2)
SUM(app(l1, l2)) -> SUM(l1)


There are no usable rules for innermost w.r.t. to the implicit AFS that need to be oriented.

Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(SUM(x1))=  x1  
  POL(cons(x1, x2))=  x2  
  POL(app(x1, x2))=  1 + x1 + x2  

resulting in one new DP problem.



   R
DPs
       →DP Problem 1
Polo
       →DP Problem 2
Polo
       →DP Problem 3
Polo
       →DP Problem 4
Polo
           →DP Problem 11
Polynomial Ordering
       →DP Problem 5
Polo


Dependency Pair:

SUM(cons(x, l)) -> SUM(l)


Rules:


+(x, 0) -> x
+(0, x) -> x
+(s(x), s(y)) -> s(s(+(x, y)))
+(+(x, y), z) -> +(x, +(y, z))
*(x, 0) -> 0
*(0, x) -> 0
*(s(x), s(y)) -> s(+(*(x, y), +(x, y)))
*(*(x, y), z) -> *(x, *(y, z))
app(nil, l) -> l
app(cons(x, l1), l2) -> cons(x, app(l1, l2))
sum(nil) -> 0
sum(cons(x, l)) -> +(x, sum(l))
sum(app(l1, l2)) -> +(sum(l1), sum(l2))
prod(nil) -> s(0)
prod(cons(x, l)) -> *(x, prod(l))
prod(app(l1, l2)) -> *(prod(l1), prod(l2))


Strategy:

innermost




The following dependency pair can be strictly oriented:

SUM(cons(x, l)) -> SUM(l)


There are no usable rules for innermost w.r.t. to the implicit AFS that need to be oriented.

Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(SUM(x1))=  x1  
  POL(cons(x1, x2))=  1 + x2  

resulting in one new DP problem.



   R
DPs
       →DP Problem 1
Polo
       →DP Problem 2
Polo
       →DP Problem 3
Polo
       →DP Problem 4
Polo
           →DP Problem 11
Polo
             ...
               →DP Problem 12
Dependency Graph
       →DP Problem 5
Polo


Dependency Pair:


Rules:


+(x, 0) -> x
+(0, x) -> x
+(s(x), s(y)) -> s(s(+(x, y)))
+(+(x, y), z) -> +(x, +(y, z))
*(x, 0) -> 0
*(0, x) -> 0
*(s(x), s(y)) -> s(+(*(x, y), +(x, y)))
*(*(x, y), z) -> *(x, *(y, z))
app(nil, l) -> l
app(cons(x, l1), l2) -> cons(x, app(l1, l2))
sum(nil) -> 0
sum(cons(x, l)) -> +(x, sum(l))
sum(app(l1, l2)) -> +(sum(l1), sum(l2))
prod(nil) -> s(0)
prod(cons(x, l)) -> *(x, prod(l))
prod(app(l1, l2)) -> *(prod(l1), prod(l2))


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.


   R
DPs
       →DP Problem 1
Polo
       →DP Problem 2
Polo
       →DP Problem 3
Polo
       →DP Problem 4
Polo
       →DP Problem 5
Polynomial Ordering


Dependency Pairs:

PROD(app(l1, l2)) -> PROD(l2)
PROD(app(l1, l2)) -> PROD(l1)
PROD(cons(x, l)) -> PROD(l)


Rules:


+(x, 0) -> x
+(0, x) -> x
+(s(x), s(y)) -> s(s(+(x, y)))
+(+(x, y), z) -> +(x, +(y, z))
*(x, 0) -> 0
*(0, x) -> 0
*(s(x), s(y)) -> s(+(*(x, y), +(x, y)))
*(*(x, y), z) -> *(x, *(y, z))
app(nil, l) -> l
app(cons(x, l1), l2) -> cons(x, app(l1, l2))
sum(nil) -> 0
sum(cons(x, l)) -> +(x, sum(l))
sum(app(l1, l2)) -> +(sum(l1), sum(l2))
prod(nil) -> s(0)
prod(cons(x, l)) -> *(x, prod(l))
prod(app(l1, l2)) -> *(prod(l1), prod(l2))


Strategy:

innermost




The following dependency pairs can be strictly oriented:

PROD(app(l1, l2)) -> PROD(l2)
PROD(app(l1, l2)) -> PROD(l1)


There are no usable rules for innermost w.r.t. to the implicit AFS that need to be oriented.

Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(cons(x1, x2))=  x2  
  POL(app(x1, x2))=  1 + x1 + x2  
  POL(PROD(x1))=  x1  

resulting in one new DP problem.



   R
DPs
       →DP Problem 1
Polo
       →DP Problem 2
Polo
       →DP Problem 3
Polo
       →DP Problem 4
Polo
       →DP Problem 5
Polo
           →DP Problem 13
Polynomial Ordering


Dependency Pair:

PROD(cons(x, l)) -> PROD(l)


Rules:


+(x, 0) -> x
+(0, x) -> x
+(s(x), s(y)) -> s(s(+(x, y)))
+(+(x, y), z) -> +(x, +(y, z))
*(x, 0) -> 0
*(0, x) -> 0
*(s(x), s(y)) -> s(+(*(x, y), +(x, y)))
*(*(x, y), z) -> *(x, *(y, z))
app(nil, l) -> l
app(cons(x, l1), l2) -> cons(x, app(l1, l2))
sum(nil) -> 0
sum(cons(x, l)) -> +(x, sum(l))
sum(app(l1, l2)) -> +(sum(l1), sum(l2))
prod(nil) -> s(0)
prod(cons(x, l)) -> *(x, prod(l))
prod(app(l1, l2)) -> *(prod(l1), prod(l2))


Strategy:

innermost




The following dependency pair can be strictly oriented:

PROD(cons(x, l)) -> PROD(l)


There are no usable rules for innermost w.r.t. to the implicit AFS that need to be oriented.

Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(cons(x1, x2))=  1 + x2  
  POL(PROD(x1))=  x1  

resulting in one new DP problem.



   R
DPs
       →DP Problem 1
Polo
       →DP Problem 2
Polo
       →DP Problem 3
Polo
       →DP Problem 4
Polo
       →DP Problem 5
Polo
           →DP Problem 13
Polo
             ...
               →DP Problem 14
Dependency Graph


Dependency Pair:


Rules:


+(x, 0) -> x
+(0, x) -> x
+(s(x), s(y)) -> s(s(+(x, y)))
+(+(x, y), z) -> +(x, +(y, z))
*(x, 0) -> 0
*(0, x) -> 0
*(s(x), s(y)) -> s(+(*(x, y), +(x, y)))
*(*(x, y), z) -> *(x, *(y, z))
app(nil, l) -> l
app(cons(x, l1), l2) -> cons(x, app(l1, l2))
sum(nil) -> 0
sum(cons(x, l)) -> +(x, sum(l))
sum(app(l1, l2)) -> +(sum(l1), sum(l2))
prod(nil) -> s(0)
prod(cons(x, l)) -> *(x, prod(l))
prod(app(l1, l2)) -> *(prod(l1), prod(l2))


Strategy:

innermost




Using the Dependency Graph resulted in no new DP problems.

Innermost Termination of R successfully shown.
Duration:
0:01 minutes