YES Termination w.r.t. Q proof of Transformed_CSR_04_Ex49_GM04_C.ari

Termination w.r.t. Q of the given QTRS could be proven:

0 QTRS
↳1 QTRSToCSRProof (⇔, 0 ms)
↳2 CSR
↳3 CSRRRRProof (⇔, 46 ms)
↳4 CSR
↳5 CSRRRRProof (⇔, 0 ms)
↳6 CSR
↳7 CSRRRRProof (⇔, 0 ms)
↳8 CSR
↳9 CSRRRRProof (⇔, 0 ms)
↳10 CSR
↳11 RisEmptyProof (⇔, 0 ms)
↳12 YES

(0) Obligation:

Q restricted rewrite system:
The TRS R consists of the following rules:

active(minus(0, Y)) → mark(0)
active(minus(s(X), s(Y))) → mark(minus(X, Y))
active(geq(X, 0)) → mark(true)
active(geq(0, s(Y))) → mark(false)
active(geq(s(X), s(Y))) → mark(geq(X, Y))
active(div(0, s(Y))) → mark(0)
active(div(s(X), s(Y))) → mark(if(geq(X, Y), s(div(minus(X, Y), s(Y))), 0))
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(s(X)) → s(active(X))
active(div(X1, X2)) → div(active(X1), X2)
active(if(X1, X2, X3)) → if(active(X1), X2, X3)
s(mark(X)) → mark(s(X))
div(mark(X1), X2) → mark(div(X1, X2))
if(mark(X1), X2, X3) → mark(if(X1, X2, X3))
proper(minus(X1, X2)) → minus(proper(X1), proper(X2))
proper(0) → ok(0)
proper(s(X)) → s(proper(X))
proper(geq(X1, X2)) → geq(proper(X1), proper(X2))
proper(true) → ok(true)
proper(false) → ok(false)
proper(div(X1, X2)) → div(proper(X1), proper(X2))
proper(if(X1, X2, X3)) → if(proper(X1), proper(X2), proper(X3))
minus(ok(X1), ok(X2)) → ok(minus(X1, X2))
s(ok(X)) → ok(s(X))
geq(ok(X1), ok(X2)) → ok(geq(X1, X2))
div(ok(X1), ok(X2)) → ok(div(X1, X2))
if(ok(X1), ok(X2), ok(X3)) → ok(if(X1, X2, X3))
top(mark(X)) → top(proper(X))
top(ok(X)) → top(active(X))

Q is empty.

(1) QTRSToCSRProof (EQUIVALENT transformation)

The following Q TRS is given: Q restricted rewrite system:
The TRS R consists of the following rules:

active(minus(0, Y)) → mark(0)
active(minus(s(X), s(Y))) → mark(minus(X, Y))
active(geq(X, 0)) → mark(true)
active(geq(0, s(Y))) → mark(false)
active(geq(s(X), s(Y))) → mark(geq(X, Y))
active(div(0, s(Y))) → mark(0)
active(div(s(X), s(Y))) → mark(if(geq(X, Y), s(div(minus(X, Y), s(Y))), 0))
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(s(X)) → s(active(X))
active(div(X1, X2)) → div(active(X1), X2)
active(if(X1, X2, X3)) → if(active(X1), X2, X3)
s(mark(X)) → mark(s(X))
div(mark(X1), X2) → mark(div(X1, X2))
if(mark(X1), X2, X3) → mark(if(X1, X2, X3))
proper(minus(X1, X2)) → minus(proper(X1), proper(X2))
proper(0) → ok(0)
proper(s(X)) → s(proper(X))
proper(geq(X1, X2)) → geq(proper(X1), proper(X2))
proper(true) → ok(true)
proper(false) → ok(false)
proper(div(X1, X2)) → div(proper(X1), proper(X2))
proper(if(X1, X2, X3)) → if(proper(X1), proper(X2), proper(X3))
minus(ok(X1), ok(X2)) → ok(minus(X1, X2))
s(ok(X)) → ok(s(X))
geq(ok(X1), ok(X2)) → ok(geq(X1, X2))
div(ok(X1), ok(X2)) → ok(div(X1, X2))
if(ok(X1), ok(X2), ok(X3)) → ok(if(X1, X2, X3))
top(mark(X)) → top(proper(X))
top(ok(X)) → top(active(X))

Q is empty.
Special symbols used for the transformation (see [GM04]):
top: top, active: active, mark: mark, ok: ok, proper: proper
The replacement map contains the following entries:

minus: empty set
0: empty set
s: {1}
geq: empty set
true: empty set
false: empty set
div: {1}
if: {1}
The QTRS contained all rules created by the complete Giesl-Middeldorp transformation. Therefore, the inverse transformation is complete (and sound).

(2) Obligation:

Context-sensitive rewrite system:
The TRS R consists of the following rules:

minus(0, Y) → 0
minus(s(X), s(Y)) → minus(X, Y)
geq(X, 0) → true
geq(0, s(Y)) → false
geq(s(X), s(Y)) → geq(X, Y)
div(0, s(Y)) → 0
div(s(X), s(Y)) → if(geq(X, Y), s(div(minus(X, Y), s(Y))), 0)
if(true, X, Y) → X
if(false, X, Y) → Y

The replacement map contains the following entries:

minus: empty set
0: empty set
s: {1}
geq: empty set
true: empty set
false: empty set
div: {1}
if: {1}

(3) CSRRRRProof (EQUIVALENT transformation)

The following CSR is given: Context-sensitive rewrite system:
The TRS R consists of the following rules:

minus(0, Y) → 0
minus(s(X), s(Y)) → minus(X, Y)
geq(X, 0) → true
geq(0, s(Y)) → false
geq(s(X), s(Y)) → geq(X, Y)
div(0, s(Y)) → 0
div(s(X), s(Y)) → if(geq(X, Y), s(div(minus(X, Y), s(Y))), 0)
if(true, X, Y) → X
if(false, X, Y) → Y

The replacement map contains the following entries:

minus: empty set
0: empty set
s: {1}
geq: empty set
true: empty set
false: empty set
div: {1}
if: {1}
Used ordering:
Polynomial interpretation [POLO]:


POL(0) = 0   
POL(div(x1, x2)) = 2 + 2·x1 + x2   
POL(false) = 1   
POL(geq(x1, x2)) = 1 + 2·x1   
POL(if(x1, x2, x3)) = x1 + x2 + x3   
POL(minus(x1, x2)) = 0   
POL(s(x1)) = 2 + x1   
POL(true) = 1   
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

geq(s(X), s(Y)) → geq(X, Y)
div(0, s(Y)) → 0
div(s(X), s(Y)) → if(geq(X, Y), s(div(minus(X, Y), s(Y))), 0)
if(true, X, Y) → X
if(false, X, Y) → Y


(4) Obligation:

Context-sensitive rewrite system:
The TRS R consists of the following rules:

minus(0, Y) → 0
minus(s(X), s(Y)) → minus(X, Y)
geq(X, 0) → true
geq(0, s(Y)) → false

The replacement map contains the following entries:

minus: empty set
0: empty set
s: {1}
geq: empty set
true: empty set
false: empty set

(5) CSRRRRProof (EQUIVALENT transformation)

The following CSR is given: Context-sensitive rewrite system:
The TRS R consists of the following rules:

minus(0, Y) → 0
minus(s(X), s(Y)) → minus(X, Y)
geq(X, 0) → true
geq(0, s(Y)) → false

The replacement map contains the following entries:

minus: empty set
0: empty set
s: {1}
geq: empty set
true: empty set
false: empty set
Used ordering:
Polynomial interpretation [POLO]:


POL(0) = 1   
POL(false) = 0   
POL(geq(x1, x2)) = x2   
POL(minus(x1, x2)) = 1 + x1   
POL(s(x1)) = x1   
POL(true) = 0   
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

minus(0, Y) → 0
geq(X, 0) → true


(6) Obligation:

Context-sensitive rewrite system:
The TRS R consists of the following rules:

minus(s(X), s(Y)) → minus(X, Y)
geq(0, s(Y)) → false

The replacement map contains the following entries:

minus: empty set
0: empty set
s: {1}
geq: empty set
false: empty set

(7) CSRRRRProof (EQUIVALENT transformation)

The following CSR is given: Context-sensitive rewrite system:
The TRS R consists of the following rules:

minus(s(X), s(Y)) → minus(X, Y)
geq(0, s(Y)) → false

The replacement map contains the following entries:

minus: empty set
0: empty set
s: {1}
geq: empty set
false: empty set
Used ordering:
Polynomial interpretation [POLO]:


POL(0) = 0   
POL(false) = 0   
POL(geq(x1, x2)) = 0   
POL(minus(x1, x2)) = x1   
POL(s(x1)) = 1 + x1   
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

minus(s(X), s(Y)) → minus(X, Y)


(8) Obligation:

Context-sensitive rewrite system:
The TRS R consists of the following rules:

geq(0, s(Y)) → false

The replacement map contains the following entries:

0: empty set
s: {1}
geq: empty set
false: empty set

(9) CSRRRRProof (EQUIVALENT transformation)

The following CSR is given: Context-sensitive rewrite system:
The TRS R consists of the following rules:

geq(0, s(Y)) → false

The replacement map contains the following entries:

0: empty set
s: {1}
geq: empty set
false: empty set
Used ordering:
Polynomial interpretation [POLO]:


POL(0) = 0   
POL(false) = 0   
POL(geq(x1, x2)) = 1 + x1 + x2   
POL(s(x1)) = x1   
With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:

geq(0, s(Y)) → false


(10) Obligation:

Context-sensitive rewrite system:
R is empty.

(11) RisEmptyProof (EQUIVALENT transformation)

The CSR R is empty. Hence, termination is trivially proven.

(12) YES