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`
`         ↳Polynomial 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)

Additionally, 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(IFAPPEND(x1, x2, x3)) =  x3 POL(cons(x1, x2)) =  1 + x1 + x2 POL(false) =  0 POL(ifappend(x1, x2, x3)) =  x2 + x3 POL(hd(x1)) =  x1 POL(nil) =  0 POL(true) =  0 POL(append(x1, x2)) =  x1 + x2 POL(tl(x1)) =  x1 POL(APPEND(x1, x2)) =  x1 POL(is_empty(x1)) =  0

resulting in one new DP problem.

`   R`
`     ↳DPs`
`       →DP Problem 1`
`         ↳Polo`
`           →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