Term Rewriting System R:
[x, l, l1, l2]
isempty(nil) -> true
isempty(cons(x, l)) -> false
hd(cons(x, l)) -> x
tl(cons(x, l)) -> l
append(l1, l2) -> ifappend(l1, l2, l1)
ifappend(l1, l2, nil) -> l2
ifappend(l1, l2, cons(x, l)) -> cons(x, append(l, l2))

Termination of R to be shown. 



   R
     ↳Dependency Pair Analysis



R contains the following Dependency Pairs:

APPEND(l1, l2) -> IFAPPEND(l1, l2, l1)
IFAPPEND(l1, l2, cons(x, l)) -> APPEND(l, l2)

Furthermore, R contains one SCC. 


   R
     ↳DPs
       →DP Problem 1
         ↳Argument Filtering and Ordering


Dependency Pairs:

IFAPPEND(l1, l2, cons(x, l)) -> APPEND(l, l2)
APPEND(l1, l2) -> IFAPPEND(l1, l2, l1)


Rules:


isempty(nil) -> true
isempty(cons(x, l)) -> false
hd(cons(x, l)) -> x
tl(cons(x, l)) -> l
append(l1, l2) -> ifappend(l1, l2, l1)
ifappend(l1, l2, nil) -> l2
ifappend(l1, l2, cons(x, l)) -> cons(x, append(l, l2))





The following dependency pair can be strictly oriented:

IFAPPEND(l1, l2, cons(x, l)) -> APPEND(l, l2)


The following rules can be oriented:

isempty(nil) -> true
isempty(cons(x, l)) -> false
hd(cons(x, l)) -> x
tl(cons(x, l)) -> l
append(l1, l2) -> ifappend(l1, l2, l1)
ifappend(l1, l2, nil) -> l2
ifappend(l1, l2, cons(x, l)) -> cons(x, append(l, l2))


Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(cons(x1, x2))=  1 + x1 + x2  
  POL(false)=  0  
  POL(ifappend(x1, x2))=  x1 + x2  
  POL(hd(x1))=  x1  
  POL(nil)=  0  
  POL(true)=  0  
  POL(append(x1, x2))=  x1 + x2  
  POL(tl(x1))=  x1  
  POL(is_empty(x1))=  x1  

resulting in one new DP problem.
Used Argument Filtering System:
IFAPPEND(x1, x2, x3) -> x3
cons(x1, x2) -> cons(x1, x2)
APPEND(x1, x2) -> x1
isempty(x1) -> isempty(x1)
hd(x1) -> hd(x1)
tl(x1) -> tl(x1)
append(x1, x2) -> append(x1, x2)
ifappend(x1, x2, x3) -> ifappend(x2, x3)


   R
     ↳DPs
       →DP Problem 1
         ↳AFS
           →DP Problem 2
             ↳Dependency Graph


Dependency Pair:

APPEND(l1, l2) -> IFAPPEND(l1, l2, l1)


Rules:


isempty(nil) -> true
isempty(cons(x, l)) -> false
hd(cons(x, l)) -> x
tl(cons(x, l)) -> l
append(l1, l2) -> ifappend(l1, l2, l1)
ifappend(l1, l2, nil) -> l2
ifappend(l1, l2, cons(x, l)) -> cons(x, append(l, l2))





Using the Dependency Graph resulted in no new DP problems.

Termination of R successfully shown.
Duration:
0:00 minutes