Term Rewriting System R:
[x]
a(f, a(f, a(g, a(g, x)))) -> a(g, a(g, a(g, a(f, a(f, a(f, x))))))
Termination of R to be shown.
R
↳Overlay and local confluence Check
The TRS is overlay and locally confluent (all critical pairs are trivially joinable).Hence, we can switch to innermost.
R
↳OC
→TRS2
↳Dependency Pair Analysis
R contains the following Dependency Pairs:
A(f, a(f, a(g, a(g, x)))) -> A(g, a(g, a(g, a(f, a(f, a(f, x))))))
A(f, a(f, a(g, a(g, x)))) -> A(g, a(g, a(f, a(f, a(f, x)))))
A(f, a(f, a(g, a(g, x)))) -> A(g, a(f, a(f, a(f, x))))
A(f, a(f, a(g, a(g, x)))) -> A(f, a(f, a(f, x)))
A(f, a(f, a(g, a(g, x)))) -> A(f, a(f, x))
A(f, a(f, a(g, a(g, x)))) -> A(f, x)
Furthermore, R contains one SCC.
R
↳OC
→TRS2
↳DPs
→DP Problem 1
↳A-Transformation
Dependency Pairs:
A(f, a(f, a(g, a(g, x)))) -> A(f, x)
A(f, a(f, a(g, a(g, x)))) -> A(f, a(f, x))
A(f, a(f, a(g, a(g, x)))) -> A(f, a(f, a(f, x)))
Rule:
a(f, a(f, a(g, a(g, x)))) -> a(g, a(g, a(g, a(f, a(f, a(f, x))))))
Strategy:
innermost
We have an applicative DP problem with proper arity. Thus we can use the A-Transformation to obtain one new DP problem which consists of the A-transformed TRSs.
R
↳OC
→TRS2
↳DPs
→DP Problem 1
↳ATrans
...
→DP Problem 2
↳RFC Match Bounds
Dependency Pairs:
F(f(g(g(x)))) -> F(x)
F(f(g(g(x)))) -> F(f(x))
F(f(g(g(x)))) -> F(f(f(x)))
Rule:
f(f(g(g(x)))) -> g(g(g(f(f(f(x))))))
Strategy:
innermost
Using RFC Match Bounds, the DP problem could be solved. The Match Bound was 5.
The certificate found is represented by the following graph.
The certificate consists of the following enumerated nodes:
18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73
Node 18 is start node and node 19 is final node.
Those nodes are connect through the following edges:
- 19 to 19 labelled #(0)
- 18 to 20 labelled F(0)
- 20 to 21 labelled f(0)
- 21 to 19 labelled f(0)
- 18 to 21 labelled F(0)
- 18 to 19 labelled F(0)
- 18 to 22 labelled F(1)
- 22 to 19 labelled f(1)
- 19 to 19 labelled f(1)
- 18 to 19 labelled F(1)
- 21 to 23 labelled g(1)
- 23 to 24 labelled g(1)
- 24 to 25 labelled g(1)
- 25 to 26 labelled f(1)
- 26 to 27 labelled f(1)
- 27 to 19 labelled f(1)
- 20 to 23 labelled g(1)
- 27 to 23 labelled g(1)
- 19 to 23 labelled g(1)
- 22 to 23 labelled g(1)
- 26 to 23 labelled g(1)
- 19 to 24 labelled f(1)
- 18 to 24 labelled F(1)
- 26 to 28 labelled g(2)
- 28 to 29 labelled g(2)
- 29 to 30 labelled g(2)
- 30 to 31 labelled f(2)
- 31 to 32 labelled f(2)
- 32 to 24 labelled f(2)
- 27 to 24 labelled f(1)
- 27 to 28 labelled g(2)
- 22 to 28 labelled g(2)
- 18 to 31 labelled F(2)
- 18 to 32 labelled F(2)
- 18 to 24 labelled F(2)
- 19 to 28 labelled g(2)
- 25 to 28 labelled g(2)
- 32 to 28 labelled f(2)
- 18 to 28 labelled F(2)
- 31 to 28 labelled g(2)
- 27 to 28 labelled f(1)
- 18 to 26 labelled F(1)
- 18 to 27 labelled F(1)
- 18 to 28 labelled F(1)
- 32 to 29 labelled f(2)
- 19 to 29 labelled f(1)
- 18 to 29 labelled F(1)
- 27 to 29 labelled f(1)
- 18 to 29 labelled F(2)
- 18 to 33 labelled F(3)
- 33 to 34 labelled f(3)
- 34 to 30 labelled f(3)
- 18 to 34 labelled F(3)
- 18 to 30 labelled F(3)
- 31 to 35 labelled g(3)
- 35 to 36 labelled g(3)
- 36 to 37 labelled g(3)
- 37 to 38 labelled f(3)
- 38 to 39 labelled f(3)
- 39 to 30 labelled f(3)
- 32 to 30 labelled f(2)
- 18 to 30 labelled F(2)
- 32 to 40 labelled g(3)
- 40 to 41 labelled g(3)
- 41 to 42 labelled g(3)
- 42 to 43 labelled f(3)
- 43 to 44 labelled f(3)
- 44 to 29 labelled f(3)
- 34 to 40 labelled g(3)
- 18 to 43 labelled F(3)
- 18 to 44 labelled F(3)
- 18 to 29 labelled F(3)
- 39 to 40 labelled g(3)
- 44 to 36 labelled f(3)
- 18 to 36 labelled F(3)
- 18 to 45 labelled F(4)
- 45 to 46 labelled f(4)
- 46 to 41 labelled f(4)
- 18 to 46 labelled F(4)
- 18 to 41 labelled F(4)
- 34 to 41 labelled f(3)
- 18 to 41 labelled F(3)
- 30 to 47 labelled g(3)
- 47 to 48 labelled g(3)
- 48 to 49 labelled g(3)
- 49 to 50 labelled f(3)
- 50 to 51 labelled f(3)
- 51 to 41 labelled f(3)
- 37 to 52 labelled g(4)
- 52 to 53 labelled g(4)
- 53 to 54 labelled g(4)
- 54 to 55 labelled f(4)
- 55 to 56 labelled f(4)
- 56 to 41 labelled f(4)
- 39 to 48 labelled f(3)
- 18 to 38 labelled F(3)
- 18 to 39 labelled F(3)
- 18 to 48 labelled F(3)
- 46 to 48 labelled f(4)
- 18 to 48 labelled F(4)
- 33 to 57 labelled g(4)
- 57 to 58 labelled g(4)
- 58 to 59 labelled g(4)
- 59 to 60 labelled f(4)
- 60 to 61 labelled f(4)
- 61 to 48 labelled f(4)
- 38 to 57 labelled g(4)
- 39 to 47 labelled f(3)
- 18 to 47 labelled F(3)
- 19 to 47 labelled f(1)
- 18 to 47 labelled F(1)
- 27 to 47 labelled f(1)
- 32 to 47 labelled f(2)
- 18 to 47 labelled F(2)
- 43 to 35 labelled g(3)
- 46 to 52 labelled f(4)
- 18 to 52 labelled F(4)
- 43 to 62 labelled g(4)
- 62 to 63 labelled g(4)
- 63 to 64 labelled g(4)
- 64 to 65 labelled f(4)
- 65 to 66 labelled f(4)
- 66 to 52 labelled f(4)
- 18 to 67 labelled F(5)
- 67 to 68 labelled f(5)
- 68 to 54 labelled f(5)
- 18 to 68 labelled F(5)
- 18 to 54 labelled F(5)
- 45 to 69 labelled g(5)
- 69 to 70 labelled g(5)
- 70 to 71 labelled g(5)
- 71 to 72 labelled f(5)
- 72 to 73 labelled f(5)
- 73 to 54 labelled f(5)
- 65 to 69 labelled g(5)
- 19 to 49 labelled f(1)
- 18 to 49 labelled F(1)
- 27 to 49 labelled f(1)
- 32 to 49 labelled f(2)
- 18 to 49 labelled F(2)
- 39 to 49 labelled f(3)
- 18 to 49 labelled F(3)
- 46 to 49 labelled f(4)
- 18 to 49 labelled F(4)
- 61 to 49 labelled f(4)
Termination of R successfully shown.
Duration:
0:01 minutes