YES Confluence Proof

Confluence Proof

by csi

Input

The rewrite relation of the following TRS is considered.

P(x) → Q(Q(p(x)))
p(p(x)) → q(q(x))
p(Q(Q(x))) → Q(Q(p(x)))
Q(p(q(x))) → q(p(Q(x)))
q(q(p(x))) → p(q(q(x)))
q(Q(x)) → x
Q(q(x)) → x
p(P(x)) → x
P(p(x)) → x

Proof

1 Redundant Rules Transformation

To prove that the TRS is (non-)confluent, we show (non-)confluence of the following modified system:

P(p(x)) → x
p(P(x)) → x
Q(q(x)) → x
q(Q(x)) → x
q(q(p(x))) → p(q(q(x)))
Q(p(q(x))) → q(p(Q(x)))
p(Q(Q(x))) → Q(Q(p(x)))
p(p(x)) → q(q(x))
P(x) → Q(Q(p(x)))

All redundant rules that were added or removed can be simulated in 2 steps .

1.1 Locally confluent and terminating

Confluence is proven by showing local confluence and termination.

1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[p(x1)] = 1 · x1 + 2
[q(x1)] = 1 · x1 + 1
[P(x1)] = 1 · x1 + 7
[Q(x1)] = 1 · x1 + 0
the rules
q(q(p(x))) → p(q(q(x)))
Q(p(q(x))) → q(p(Q(x)))
p(Q(Q(x))) → Q(Q(p(x)))
remain.

1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[p(x1)] = 1 · x1 + 0
[q(x1)] = 2 · x1 + 1
[Q(x1)] = 2 · x1 + 0
the rules
q(q(p(x))) → p(q(q(x)))
p(Q(Q(x))) → Q(Q(p(x)))
remain.

1.1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[p(x1)] = 4 · x1 + 3
[q(x1)] = 2 · x1 + 1
[Q(x1)] = 2 · x1 + 2
the rule
q(q(p(x))) → p(q(q(x)))
remains.

1.1.1.1.1.1 Rule Removal

Using the linear polynomial interpretation over the naturals
[p(x1)] = 2 · x1 + 2
[q(x1)] = 2 · x1 + 1
all rules could be removed.

1.1.1.1.1.1.1 R is empty

There are no rules in the TRS. Hence, it is terminating.

1.1.2 Local Confluence Proof

All critical pairs are joinable which can be seen by computing normal forms of all critical pairs.

Tool configuration

csi