(0) Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
f(f(X)) → c(n__f(n__g(n__f(X))))
c(X) → d(activate(X))
h(X) → c(n__d(X))
f(X) → n__f(X)
g(X) → n__g(X)
d(X) → n__d(X)
activate(n__f(X)) → f(activate(X))
activate(n__g(X)) → g(X)
activate(n__d(X)) → d(X)
activate(X) → 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:
F(f(X)) → C(n__f(n__g(n__f(X))))
C(X) → D(activate(X))
C(X) → ACTIVATE(X)
H(X) → C(n__d(X))
ACTIVATE(n__f(X)) → F(activate(X))
ACTIVATE(n__f(X)) → ACTIVATE(X)
ACTIVATE(n__g(X)) → G(X)
ACTIVATE(n__d(X)) → D(X)
The TRS R consists of the following rules:
f(f(X)) → c(n__f(n__g(n__f(X))))
c(X) → d(activate(X))
h(X) → c(n__d(X))
f(X) → n__f(X)
g(X) → n__g(X)
d(X) → n__d(X)
activate(n__f(X)) → f(activate(X))
activate(n__g(X)) → g(X)
activate(n__d(X)) → d(X)
activate(X) → 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 1 SCC with 4 less nodes.
(4) Obligation:
Q DP problem:
The TRS P consists of the following rules:
C(X) → ACTIVATE(X)
ACTIVATE(n__f(X)) → F(activate(X))
F(f(X)) → C(n__f(n__g(n__f(X))))
ACTIVATE(n__f(X)) → ACTIVATE(X)
The TRS R consists of the following rules:
f(f(X)) → c(n__f(n__g(n__f(X))))
c(X) → d(activate(X))
h(X) → c(n__d(X))
f(X) → n__f(X)
g(X) → n__g(X)
d(X) → n__d(X)
activate(n__f(X)) → f(activate(X))
activate(n__g(X)) → g(X)
activate(n__d(X)) → d(X)
activate(X) → X
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(5) QDPOrderProof (EQUIVALENT transformation)
We use the reduction pair processor [LPAR04].
The following pairs can be oriented strictly and are deleted.
ACTIVATE(n__f(X)) → ACTIVATE(X)
The remaining pairs can at least be oriented weakly.
Used ordering: SCNP Order with the following components:
Level mapping:
Top level AFS:
C(
x0,
x1) =
C(
x1)
ACTIVATE(
x0,
x1) =
ACTIVATE(
x1)
F(
x0,
x1) =
F(
x0)
Tags:
C has argument tags [0,0] and root tag 0
ACTIVATE has argument tags [0,0] and root tag 0
F has argument tags [0,4] and root tag 0
Comparison: MAX
Underlying order for the size change arcs and the rules of R:
Combined order from the following AFS and order.
C(
x1) =
C
ACTIVATE(
x1) =
x1
n__f(
x1) =
n__f(
x1)
F(
x1) =
x1
activate(
x1) =
activate(
x1)
f(
x1) =
f(
x1)
n__g(
x1) =
n__g
g(
x1) =
g
n__d(
x1) =
x1
d(
x1) =
x1
c(
x1) =
c(
x1)
Recursive path order with status [RPO].
Quasi-Precedence:
C > ng
[nf1, activate1, f1, c1] > g > ng
Status:
C: []
nf1: [1]
activate1: [1]
f1: [1]
ng: multiset
g: multiset
c1: [1]
The following usable rules [FROCOS05] were oriented:
activate(n__f(X)) → f(activate(X))
activate(n__g(X)) → g(X)
activate(n__d(X)) → d(X)
activate(X) → X
f(f(X)) → c(n__f(n__g(n__f(X))))
c(X) → d(activate(X))
d(X) → n__d(X)
f(X) → n__f(X)
g(X) → n__g(X)
(6) Obligation:
Q DP problem:
The TRS P consists of the following rules:
C(X) → ACTIVATE(X)
ACTIVATE(n__f(X)) → F(activate(X))
F(f(X)) → C(n__f(n__g(n__f(X))))
The TRS R consists of the following rules:
f(f(X)) → c(n__f(n__g(n__f(X))))
c(X) → d(activate(X))
h(X) → c(n__d(X))
f(X) → n__f(X)
g(X) → n__g(X)
d(X) → n__d(X)
activate(n__f(X)) → f(activate(X))
activate(n__g(X)) → g(X)
activate(n__d(X)) → d(X)
activate(X) → X
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(7) QDPOrderProof (EQUIVALENT transformation)
We use the reduction pair processor [LPAR04].
The following pairs can be oriented strictly and are deleted.
ACTIVATE(n__f(X)) → F(activate(X))
F(f(X)) → C(n__f(n__g(n__f(X))))
The remaining pairs can at least be oriented weakly.
Used ordering: SCNP Order with the following components:
Level mapping:
Top level AFS:
C(
x0,
x1) =
C(
x0,
x1)
ACTIVATE(
x0,
x1) =
ACTIVATE(
x0)
F(
x0,
x1) =
F(
x1)
Tags:
C has argument tags [4,2] and root tag 0
ACTIVATE has argument tags [4,3] and root tag 0
F has argument tags [4,4] and root tag 1
Comparison: MAX
Underlying order for the size change arcs and the rules of R:
Combined order from the following AFS and order.
C(
x1) =
x1
ACTIVATE(
x1) =
x1
n__f(
x1) =
n__f(
x1)
F(
x1) =
F
activate(
x1) =
x1
f(
x1) =
f(
x1)
n__g(
x1) =
n__g
g(
x1) =
g
n__d(
x1) =
x1
d(
x1) =
x1
c(
x1) =
c(
x1)
Recursive path order with status [RPO].
Quasi-Precedence:
[nf1, F, f1] > c1 > [ng, g]
Status:
nf1: multiset
F: []
f1: multiset
ng: []
g: []
c1: [1]
The following usable rules [FROCOS05] were oriented:
none
(8) Obligation:
Q DP problem:
The TRS P consists of the following rules:
C(X) → ACTIVATE(X)
The TRS R consists of the following rules:
f(f(X)) → c(n__f(n__g(n__f(X))))
c(X) → d(activate(X))
h(X) → c(n__d(X))
f(X) → n__f(X)
g(X) → n__g(X)
d(X) → n__d(X)
activate(n__f(X)) → f(activate(X))
activate(n__g(X)) → g(X)
activate(n__d(X)) → d(X)
activate(X) → X
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(9) DependencyGraphProof (EQUIVALENT transformation)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
(10) TRUE