Certification Problem
Input (TPDB TRS_Standard/Transformed_CSR_04/Ex9_Luc04_L)
The rewrite relation of the following TRS is considered.
|
f(a,X) |
→ |
f(X,X) |
(1) |
| c |
→ |
a |
(2) |
| c |
→ |
b |
(3) |
Property / Task
Prove or disprove termination.Answer / Result
No.Proof (by AProVE @ termCOMP 2023)
1 Uncurrying
We uncurry the binary symbol
f
in combination with the following symbol map which also determines the applicative arities of these symbols.
| a |
is mapped to |
a, |
a1(x1) |
| c |
is mapped to |
c |
| b |
is mapped to |
b |
There are no uncurry rules.
No rules have to be added for the eta-expansion.
Uncurrying the rules and adding the uncurrying rules yields the new set of rules
|
a1(X) |
→ |
f(X,X) |
(5) |
| c |
→ |
a |
(2) |
| c |
→ |
b |
(3) |
|
f(a,y1) |
→ |
a1(y1) |
(4) |
1.1 Dependency Pair Transformation
The following set of initial dependency pairs has been identified.
|
a1#(X) |
→ |
f#(X,X) |
(6) |
|
f#(a,y1) |
→ |
a1#(y1) |
(7) |
It remains to prove infiniteness of the resulting DP problem.
1.1.1 Loop
The following loop proves infiniteness of the DP problem.
| t0
|
= |
f#(a,a) |
|
→P
|
a1#(a) |
|
→P
|
f#(a,a) |
|
= |
t2
|
where t2 =
t0