Term Rewriting System R:
[x]
a(c(d(x))) -> c(x)
u(b(d(d(x)))) -> b(x)
v(a(a(x))) -> u(v(x))
v(a(c(x))) -> u(b(d(x)))
v(c(x)) -> b(x)
w(a(a(x))) -> u(w(x))
w(a(c(x))) -> u(b(d(x)))
w(c(x)) -> b(x)

Termination of R to be shown.



   R
Dependency Pair Analysis



R contains the following Dependency Pairs:

V(a(a(x))) -> U(v(x))
V(a(a(x))) -> V(x)
V(a(c(x))) -> U(b(d(x)))
W(a(a(x))) -> U(w(x))
W(a(a(x))) -> W(x)
W(a(c(x))) -> U(b(d(x)))

Furthermore, R contains two SCCs.


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


Dependency Pair:

V(a(a(x))) -> V(x)


Rules:


a(c(d(x))) -> c(x)
u(b(d(d(x)))) -> b(x)
v(a(a(x))) -> u(v(x))
v(a(c(x))) -> u(b(d(x)))
v(c(x)) -> b(x)
w(a(a(x))) -> u(w(x))
w(a(c(x))) -> u(b(d(x)))
w(c(x)) -> b(x)





The following dependency pair can be strictly oriented:

V(a(a(x))) -> V(x)


The following rules can be oriented:

a(c(d(x))) -> c(x)
u(b(d(d(x)))) -> b(x)
v(a(a(x))) -> u(v(x))
v(a(c(x))) -> u(b(d(x)))
v(c(x)) -> b(x)
w(a(a(x))) -> u(w(x))
w(a(c(x))) -> u(b(d(x)))
w(c(x)) -> b(x)


Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(c(x1))=  x1  
  POL(v(x1))=  x1  
  POL(V(x1))=  1 + x1  
  POL(b(x1))=  x1  
  POL(d(x1))=  x1  
  POL(a(x1))=  1 + x1  
  POL(w(x1))=  x1  
  POL(u(x1))=  x1  

resulting in one new DP problem.
Used Argument Filtering System:
V(x1) -> V(x1)
a(x1) -> a(x1)
c(x1) -> c(x1)
d(x1) -> d(x1)
u(x1) -> u(x1)
b(x1) -> b(x1)
v(x1) -> v(x1)
w(x1) -> w(x1)


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


Dependency Pair:


Rules:


a(c(d(x))) -> c(x)
u(b(d(d(x)))) -> b(x)
v(a(a(x))) -> u(v(x))
v(a(c(x))) -> u(b(d(x)))
v(c(x)) -> b(x)
w(a(a(x))) -> u(w(x))
w(a(c(x))) -> u(b(d(x)))
w(c(x)) -> b(x)





Using the Dependency Graph resulted in no new DP problems.


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


Dependency Pair:

W(a(a(x))) -> W(x)


Rules:


a(c(d(x))) -> c(x)
u(b(d(d(x)))) -> b(x)
v(a(a(x))) -> u(v(x))
v(a(c(x))) -> u(b(d(x)))
v(c(x)) -> b(x)
w(a(a(x))) -> u(w(x))
w(a(c(x))) -> u(b(d(x)))
w(c(x)) -> b(x)





The following dependency pair can be strictly oriented:

W(a(a(x))) -> W(x)


The following rules can be oriented:

a(c(d(x))) -> c(x)
u(b(d(d(x)))) -> b(x)
v(a(a(x))) -> u(v(x))
v(a(c(x))) -> u(b(d(x)))
v(c(x)) -> b(x)
w(a(a(x))) -> u(w(x))
w(a(c(x))) -> u(b(d(x)))
w(c(x)) -> b(x)


Used ordering: Polynomial ordering with Polynomial interpretation:
  POL(c(x1))=  x1  
  POL(v(x1))=  x1  
  POL(b(x1))=  x1  
  POL(d(x1))=  x1  
  POL(W(x1))=  1 + x1  
  POL(a(x1))=  1 + x1  
  POL(w(x1))=  x1  
  POL(u(x1))=  x1  

resulting in one new DP problem.
Used Argument Filtering System:
W(x1) -> W(x1)
a(x1) -> a(x1)
c(x1) -> c(x1)
d(x1) -> d(x1)
u(x1) -> u(x1)
b(x1) -> b(x1)
v(x1) -> v(x1)
w(x1) -> w(x1)


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


Dependency Pair:


Rules:


a(c(d(x))) -> c(x)
u(b(d(d(x)))) -> b(x)
v(a(a(x))) -> u(v(x))
v(a(c(x))) -> u(b(d(x)))
v(c(x)) -> b(x)
w(a(a(x))) -> u(w(x))
w(a(c(x))) -> u(b(d(x)))
w(c(x)) -> b(x)





Using the Dependency Graph resulted in no new DP problems.

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