Certification Problem
Input (COPS 1079)
We consider two TRSs R and S where R contains the rules
|
f(g(f(x))) |
→ |
g(f(g(x))) |
(1) |
|
f(c) |
→ |
c |
(2) |
|
g(c) |
→ |
c |
(3) |
and S contains the following rules:
|
f(f(f(x))) |
→ |
a |
(4) |
|
f(f(a)) |
→ |
a |
(5) |
|
f(a) |
→ |
a |
(6) |
|
f(f(g(g(x)))) |
→ |
f(a) |
(7) |
|
g(f(a)) |
→ |
a |
(8) |
|
g(a) |
→ |
a |
(9) |
The underlying signature is as follows:
{a/0, c/0, f/1, g/1}Property / Task
Prove or disprove commutation.Answer / Result
No.Proof (by ACP @ CoCo 2023)
1 Non-Joinable Fork
The systems are not commuting due to the following forking derivations.
| t0
|
= |
f(g(f(f(f(x))))) |
|
→S
|
f(g(a)) |
|
= |
s1
|
and
| t0
|
= |
f(g(f(f(f(x))))) |
|
→R
|
g(f(g(f(f(x))))) |
|
= |
t1
|
There is no possibility to join
s1→R*·←S*
t1
for the following reason:
- We take the usable rules of the first term (w.r.t. the TRS for the first term)
and the usable rules of the second term (w.r.t. the TRS for the second term).
Then the terms are not joinable w.r.t. the resulting TRSs.
- We filter all terms and rules w.r.t. the following argument filter.
| π(a) |
= |
[] |
| π(f) |
= |
[] |
| π(g) |
= |
[] |
Then the resulting terms are not joinable w.r.t. the resulting TRSs.
- We take the usable rules of the first term (w.r.t. the TRS for the first term)
and the usable rules of the second term (w.r.t. the TRS for the second term).
Then the terms are not joinable w.r.t. the resulting TRSs.
- The first mentioned term is strictly larger than the second one (or vice versa). Here, the following discrimination pair has
been used w.r.t. the following interpretation.
Moreover, the (reversed) rules are weakly decreasing.
The discrimination pair is given by a