(0) Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
half(0) → 0
half(s(s(x))) → s(half(x))
log(s(0)) → 0
log(s(s(x))) → s(log(s(half(x))))
Q is empty.
(1) DependencyPairsProof (EQUIVALENT transformation)
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:
HALF(s(s(x))) → HALF(x)
LOG(s(s(x))) → LOG(s(half(x)))
LOG(s(s(x))) → HALF(x)
The TRS R consists of the following rules:
half(0) → 0
half(s(s(x))) → s(half(x))
log(s(0)) → 0
log(s(s(x))) → s(log(s(half(x))))
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(3) DependencyGraphProof (EQUIVALENT transformation)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node.
(4) Complex Obligation (AND)
(5) Obligation:
Q DP problem:
The TRS P consists of the following rules:
HALF(s(s(x))) → HALF(x)
The TRS R consists of the following rules:
half(0) → 0
half(s(s(x))) → s(half(x))
log(s(0)) → 0
log(s(s(x))) → s(log(s(half(x))))
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(6) QDPSizeChangeProof (EQUIVALENT transformation)
We used the following order and afs together with the size-change analysis [AAECC05] to show that there are no infinite chains for this DP problem.
Order:Homeomorphic Embedding Order
AFS:
s(x1) = s(x1)
From the DPs we obtained the following set of size-change graphs:
- HALF(s(s(x))) → HALF(x) (allowed arguments on rhs = {1})
The graph contains the following edges 1 > 1
We oriented the following set of usable rules [AAECC05,FROCOS05].
none
(7) TRUE
(8) Obligation:
Q DP problem:
The TRS P consists of the following rules:
LOG(s(s(x))) → LOG(s(half(x)))
The TRS R consists of the following rules:
half(0) → 0
half(s(s(x))) → s(half(x))
log(s(0)) → 0
log(s(s(x))) → s(log(s(half(x))))
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(9) QDPSizeChangeProof (EQUIVALENT transformation)
We used the following order and afs together with the size-change analysis [AAECC05] to show that there are no infinite chains for this DP problem.
Order:Combined order from the following AFS and order.
half(x1) = x1
s(x1) = s(x1)
0 = 0
Lexicographic path order with status [LPO].
Quasi-Precedence:
trivial
Status:
s1: [1]
0: []
AFS:
half(x1) = x1
s(x1) = s(x1)
0 = 0
From the DPs we obtained the following set of size-change graphs:
- LOG(s(s(x))) → LOG(s(half(x))) (allowed arguments on rhs = {1})
The graph contains the following edges 1 > 1
We oriented the following set of usable rules [AAECC05,FROCOS05].
half(s(s(x))) → s(half(x))
half(0) → 0
(10) TRUE