Term Rewriting System R:
[x]
half(0) -> 0
half(s(0)) -> 0
half(s(s(x))) -> s(half(x))
lastbit(0) -> 0
lastbit(s(0)) -> s(0)
lastbit(s(s(x))) -> lastbit(x)
conv(0) -> cons(nil, 0)
conv(s(x)) -> cons(conv(half(s(x))), lastbit(s(x)))

Termination of R to be shown.

R
Dependency Pair Analysis

R contains the following Dependency Pairs:

HALF(s(s(x))) -> HALF(x)
LASTBIT(s(s(x))) -> LASTBIT(x)
CONV(s(x)) -> CONV(half(s(x)))
CONV(s(x)) -> HALF(s(x))
CONV(s(x)) -> LASTBIT(s(x))

Furthermore, R contains three SCCs.

R
DPs
→DP Problem 1
Argument Filtering and Ordering
→DP Problem 2
AFS
→DP Problem 3
Remaining

Dependency Pair:

HALF(s(s(x))) -> HALF(x)

Rules:

half(0) -> 0
half(s(0)) -> 0
half(s(s(x))) -> s(half(x))
lastbit(0) -> 0
lastbit(s(0)) -> s(0)
lastbit(s(s(x))) -> lastbit(x)
conv(0) -> cons(nil, 0)
conv(s(x)) -> cons(conv(half(s(x))), lastbit(s(x)))

The following dependency pair can be strictly oriented:

HALF(s(s(x))) -> HALF(x)

There are no usable rules w.r.t. to the AFS that need to be oriented.
Used ordering: Homeomorphic Embedding Order with EMB
resulting in one new DP problem.
Used Argument Filtering System:
HALF(x1) -> HALF(x1)
s(x1) -> s(x1)

R
DPs
→DP Problem 1
AFS
→DP Problem 4
Dependency Graph
→DP Problem 2
AFS
→DP Problem 3
Remaining

Dependency Pair:

Rules:

half(0) -> 0
half(s(0)) -> 0
half(s(s(x))) -> s(half(x))
lastbit(0) -> 0
lastbit(s(0)) -> s(0)
lastbit(s(s(x))) -> lastbit(x)
conv(0) -> cons(nil, 0)
conv(s(x)) -> cons(conv(half(s(x))), lastbit(s(x)))

Using the Dependency Graph resulted in no new DP problems.

R
DPs
→DP Problem 1
AFS
→DP Problem 2
Argument Filtering and Ordering
→DP Problem 3
Remaining

Dependency Pair:

LASTBIT(s(s(x))) -> LASTBIT(x)

Rules:

half(0) -> 0
half(s(0)) -> 0
half(s(s(x))) -> s(half(x))
lastbit(0) -> 0
lastbit(s(0)) -> s(0)
lastbit(s(s(x))) -> lastbit(x)
conv(0) -> cons(nil, 0)
conv(s(x)) -> cons(conv(half(s(x))), lastbit(s(x)))

The following dependency pair can be strictly oriented:

LASTBIT(s(s(x))) -> LASTBIT(x)

There are no usable rules w.r.t. to the AFS that need to be oriented.
Used ordering: Homeomorphic Embedding Order with EMB
resulting in one new DP problem.
Used Argument Filtering System:
LASTBIT(x1) -> LASTBIT(x1)
s(x1) -> s(x1)

R
DPs
→DP Problem 1
AFS
→DP Problem 2
AFS
→DP Problem 5
Dependency Graph
→DP Problem 3
Remaining

Dependency Pair:

Rules:

half(0) -> 0
half(s(0)) -> 0
half(s(s(x))) -> s(half(x))
lastbit(0) -> 0
lastbit(s(0)) -> s(0)
lastbit(s(s(x))) -> lastbit(x)
conv(0) -> cons(nil, 0)
conv(s(x)) -> cons(conv(half(s(x))), lastbit(s(x)))

Using the Dependency Graph resulted in no new DP problems.

R
DPs
→DP Problem 1
AFS
→DP Problem 2
AFS
→DP Problem 3
Remaining Obligation(s)

The following remains to be proven:
Dependency Pair:

CONV(s(x)) -> CONV(half(s(x)))

Rules:

half(0) -> 0
half(s(0)) -> 0
half(s(s(x))) -> s(half(x))
lastbit(0) -> 0
lastbit(s(0)) -> s(0)
lastbit(s(s(x))) -> lastbit(x)
conv(0) -> cons(nil, 0)
conv(s(x)) -> cons(conv(half(s(x))), lastbit(s(x)))

Termination of R could not be shown.
Duration:
0:00 minutes