/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


YES
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


Termination of the given RelTRS could be proven:

(0) RelTRS
(1) RelTRSRRRProof [EQUIVALENT, 70 ms]
(2) RelTRS
(3) RelTRSRRRProof [EQUIVALENT, 55 ms]
(4) RelTRS
(5) RelTRSRRRProof [EQUIVALENT, 33 ms]
(6) RelTRS
(7) RelTRSSemanticLabellingPOLOProof [EQUIVALENT, 238 ms]
(8) RelTRS
(9) RelTRSRRRProof [EQUIVALENT, 34 ms]
(10) RelTRS
(11) RelTRSSemanticLabellingPOLOProof [EQUIVALENT, 88 ms]
(12) RelTRS
(13) RelTRSRRRProof [EQUIVALENT, 0 ms]
(14) RelTRS
(15) RelTRSSemanticLabellingPOLOProof [EQUIVALENT, 38 ms]
(16) RelTRS
(17) RelTRSRRRProof [EQUIVALENT, 0 ms]
(18) RelTRS
(19) RIsEmptyProof [EQUIVALENT, 0 ms]
(20) YES


----------------------------------------

(0)
Obligation:
Relative term rewrite system:
The relative TRS consists of the following R rules:

   Tl(O(x), y) -> Wr(check(x), y)
   Tl(O(x), y) -> Wr(x, check(y))
   Tl(N(x), y) -> Wr(check(x), y)
   Tl(N(x), y) -> Wr(x, check(y))
   Tr(x, O(y)) -> Wl(check(x), y)
   Tr(x, O(y)) -> Wl(x, check(y))
   Tr(x, N(y)) -> Wl(check(x), y)
   Tr(x, N(y)) -> Wl(x, check(y))
   Tl(B, y) -> Wr(check(B), y)
   Tl(B, y) -> Wr(B, check(y))
   Tr(x, B) -> Wl(check(x), B)
   Tr(x, B) -> Wl(x, check(B))

The relative TRS consists of the following S rules:

   Tl(O(x), y) -> Wl(check(x), y)
   Tl(O(x), y) -> Wl(x, check(y))
   Tl(N(x), y) -> Wl(check(x), y)
   Tl(N(x), y) -> Wl(x, check(y))
   Tr(x, O(y)) -> Wr(check(x), y)
   Tr(x, O(y)) -> Wr(x, check(y))
   Tr(x, N(y)) -> Wr(check(x), y)
   Tr(x, N(y)) -> Wr(x, check(y))
   B -> N(B)
   check(O(x)) -> ok(O(x))
   Wl(ok(x), y) -> Tl(x, y)
   Wl(x, ok(y)) -> Tl(x, y)
   Wr(ok(x), y) -> Tr(x, y)
   Wr(x, ok(y)) -> Tr(x, y)
   check(O(x)) -> O(check(x))
   check(N(x)) -> N(check(x))
   O(ok(x)) -> ok(O(x))
   N(ok(x)) -> ok(N(x))


----------------------------------------

(1) RelTRSRRRProof (EQUIVALENT)
We used the following monotonic ordering for rule removal:
Polynomial interpretation [POLO]:

   POL(B) = 0
   POL(N(x_1)) = x_1
   POL(O(x_1)) = 1 + x_1
   POL(Tl(x_1, x_2)) = x_1 + x_2
   POL(Tr(x_1, x_2)) = x_1 + x_2
   POL(Wl(x_1, x_2)) = x_1 + x_2
   POL(Wr(x_1, x_2)) = x_1 + x_2
   POL(check(x_1)) = x_1
   POL(ok(x_1)) = x_1
With this ordering the following rules can be removed [MATRO] because they are oriented strictly:
Rules from R:

   Tl(O(x), y) -> Wr(check(x), y)
   Tl(O(x), y) -> Wr(x, check(y))
   Tr(x, O(y)) -> Wl(check(x), y)
   Tr(x, O(y)) -> Wl(x, check(y))
Rules from S:

   Tl(O(x), y) -> Wl(check(x), y)
   Tl(O(x), y) -> Wl(x, check(y))
   Tr(x, O(y)) -> Wr(check(x), y)
   Tr(x, O(y)) -> Wr(x, check(y))




----------------------------------------

(2)
Obligation:
Relative term rewrite system:
The relative TRS consists of the following R rules:

   Tl(N(x), y) -> Wr(check(x), y)
   Tl(N(x), y) -> Wr(x, check(y))
   Tr(x, N(y)) -> Wl(check(x), y)
   Tr(x, N(y)) -> Wl(x, check(y))
   Tl(B, y) -> Wr(check(B), y)
   Tl(B, y) -> Wr(B, check(y))
   Tr(x, B) -> Wl(check(x), B)
   Tr(x, B) -> Wl(x, check(B))

The relative TRS consists of the following S rules:

   Tl(N(x), y) -> Wl(check(x), y)
   Tl(N(x), y) -> Wl(x, check(y))
   Tr(x, N(y)) -> Wr(check(x), y)
   Tr(x, N(y)) -> Wr(x, check(y))
   B -> N(B)
   check(O(x)) -> ok(O(x))
   Wl(ok(x), y) -> Tl(x, y)
   Wl(x, ok(y)) -> Tl(x, y)
   Wr(ok(x), y) -> Tr(x, y)
   Wr(x, ok(y)) -> Tr(x, y)
   check(O(x)) -> O(check(x))
   check(N(x)) -> N(check(x))
   O(ok(x)) -> ok(O(x))
   N(ok(x)) -> ok(N(x))


----------------------------------------

(3) RelTRSRRRProof (EQUIVALENT)
We used the following monotonic ordering for rule removal:
Matrix interpretation [MATRO] to (N^2, +, *, >=, >) :

   <<<
 POL(Tl(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 0]] 	* 	x_1 	 +  	[[1, 1], [0, 0]] 	* 	x_2
>>>

   <<<
 POL(N(x_1)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 1]] 	* 	x_1
>>>

   <<<
 POL(Wr(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 0]] 	* 	x_1 	 +  	[[1, 1], [0, 0]] 	* 	x_2
>>>

   <<<
 POL(check(x_1)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 0]] 	* 	x_1
>>>

   <<<
 POL(Tr(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 0]] 	* 	x_1 	 +  	[[1, 1], [0, 0]] 	* 	x_2
>>>

   <<<
 POL(Wl(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 0]] 	* 	x_1 	 +  	[[1, 1], [0, 0]] 	* 	x_2
>>>

   <<<
 POL(B) =  	[[0], [1]]
>>>

   <<<
 POL(O(x_1)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 0]] 	* 	x_1
>>>

   <<<
 POL(ok(x_1)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 1]] 	* 	x_1
>>>

With this ordering the following rules can be removed [MATRO] because they are oriented strictly:
Rules from R:

   Tr(x, B) -> Wl(x, check(B))
Rules from S:
none




----------------------------------------

(4)
Obligation:
Relative term rewrite system:
The relative TRS consists of the following R rules:

   Tl(N(x), y) -> Wr(check(x), y)
   Tl(N(x), y) -> Wr(x, check(y))
   Tr(x, N(y)) -> Wl(check(x), y)
   Tr(x, N(y)) -> Wl(x, check(y))
   Tl(B, y) -> Wr(check(B), y)
   Tl(B, y) -> Wr(B, check(y))
   Tr(x, B) -> Wl(check(x), B)

The relative TRS consists of the following S rules:

   Tl(N(x), y) -> Wl(check(x), y)
   Tl(N(x), y) -> Wl(x, check(y))
   Tr(x, N(y)) -> Wr(check(x), y)
   Tr(x, N(y)) -> Wr(x, check(y))
   B -> N(B)
   check(O(x)) -> ok(O(x))
   Wl(ok(x), y) -> Tl(x, y)
   Wl(x, ok(y)) -> Tl(x, y)
   Wr(ok(x), y) -> Tr(x, y)
   Wr(x, ok(y)) -> Tr(x, y)
   check(O(x)) -> O(check(x))
   check(N(x)) -> N(check(x))
   O(ok(x)) -> ok(O(x))
   N(ok(x)) -> ok(N(x))


----------------------------------------

(5) RelTRSRRRProof (EQUIVALENT)
We used the following monotonic ordering for rule removal:
Matrix interpretation [MATRO] to (N^2, +, *, >=, >) :

   <<<
 POL(Tl(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 1], [0, 0]] 	* 	x_1 	 +  	[[1, 0], [0, 0]] 	* 	x_2
>>>

   <<<
 POL(N(x_1)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 1]] 	* 	x_1
>>>

   <<<
 POL(Wr(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 1], [0, 0]] 	* 	x_1 	 +  	[[1, 0], [0, 0]] 	* 	x_2
>>>

   <<<
 POL(check(x_1)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 0]] 	* 	x_1
>>>

   <<<
 POL(Tr(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 1], [0, 0]] 	* 	x_1 	 +  	[[1, 0], [0, 0]] 	* 	x_2
>>>

   <<<
 POL(Wl(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 1], [0, 0]] 	* 	x_1 	 +  	[[1, 0], [0, 0]] 	* 	x_2
>>>

   <<<
 POL(B) =  	[[0], [1]]
>>>

   <<<
 POL(O(x_1)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 0]] 	* 	x_1
>>>

   <<<
 POL(ok(x_1)) =  	[[0], [0]] 	 +  	[[1, 1], [0, 0]] 	* 	x_1
>>>

With this ordering the following rules can be removed [MATRO] because they are oriented strictly:
Rules from R:

   Tl(B, y) -> Wr(check(B), y)
Rules from S:
none




----------------------------------------

(6)
Obligation:
Relative term rewrite system:
The relative TRS consists of the following R rules:

   Tl(N(x), y) -> Wr(check(x), y)
   Tl(N(x), y) -> Wr(x, check(y))
   Tr(x, N(y)) -> Wl(check(x), y)
   Tr(x, N(y)) -> Wl(x, check(y))
   Tl(B, y) -> Wr(B, check(y))
   Tr(x, B) -> Wl(check(x), B)

The relative TRS consists of the following S rules:

   Tl(N(x), y) -> Wl(check(x), y)
   Tl(N(x), y) -> Wl(x, check(y))
   Tr(x, N(y)) -> Wr(check(x), y)
   Tr(x, N(y)) -> Wr(x, check(y))
   B -> N(B)
   check(O(x)) -> ok(O(x))
   Wl(ok(x), y) -> Tl(x, y)
   Wl(x, ok(y)) -> Tl(x, y)
   Wr(ok(x), y) -> Tr(x, y)
   Wr(x, ok(y)) -> Tr(x, y)
   check(O(x)) -> O(check(x))
   check(N(x)) -> N(check(x))
   O(ok(x)) -> ok(O(x))
   N(ok(x)) -> ok(N(x))


----------------------------------------

(7) RelTRSSemanticLabellingPOLOProof (EQUIVALENT)
We use Semantic Labelling over tuples of bools combined with a polynomial order [SEMLAB]



We use semantic labelling over boolean tuples of size 1.



We used the following model:

Tl_2: component 1: OR[]

N_1: component 1: OR[x_1^1]

Wl_2: component 1: OR[]

check_1: component 1: OR[x_1^1]

Tr_2: component 1: OR[]

Wr_2: component 1: OR[]

B_0: component 1: OR[]

O_1: component 1: AND[]

ok_1: component 1: OR[x_1^1]



Our labelling function was:

Tl_2:component 1: AND[x_1^1]

N_1:component 1: XOR[x_1^1]

Wl_2:component 1: XOR[-x_2^1]

check_1:component 1: XOR[]

Tr_2:component 1: OR[]

Wr_2:component 1: AND[-x_2^1]

B_0:component 1: AND[]

O_1:component 1: OR[]

ok_1:component 1: XOR[-x_1^1]





Our labelled system was:

^[f]Tl^[f](^[f]N^[f](^[f]x), ^[f]y) -> ^[f]Wl^[t](^[f]check^[f](^[f]x), ^[f]y)

^[f]Tl^[f](^[f]N^[f](^[f]x), ^[t]y) -> ^[f]Wl^[f](^[f]check^[f](^[f]x), ^[t]y)

^[f]Tl^[t](^[t]N^[t](^[t]x), ^[f]y) -> ^[f]Wl^[t](^[t]check^[f](^[t]x), ^[f]y)

^[f]Tl^[t](^[t]N^[t](^[t]x), ^[t]y) -> ^[f]Wl^[f](^[t]check^[f](^[t]x), ^[t]y)

^[f]Tl^[f](^[f]N^[f](^[f]x), ^[f]y) -> ^[f]Wl^[t](^[f]x, ^[f]check^[f](^[f]y))

^[f]Tl^[f](^[f]N^[f](^[f]x), ^[t]y) -> ^[f]Wl^[f](^[f]x, ^[t]check^[f](^[t]y))

^[f]Tl^[t](^[t]N^[t](^[t]x), ^[f]y) -> ^[f]Wl^[t](^[t]x, ^[f]check^[f](^[f]y))

^[f]Tl^[t](^[t]N^[t](^[t]x), ^[t]y) -> ^[f]Wl^[f](^[t]x, ^[t]check^[f](^[t]y))

^[f]Tr^[f](^[f]x, ^[f]N^[f](^[f]y)) -> ^[f]Wr^[t](^[f]check^[f](^[f]x), ^[f]y)

^[f]Tr^[f](^[f]x, ^[t]N^[t](^[t]y)) -> ^[f]Wr^[f](^[f]check^[f](^[f]x), ^[t]y)

^[f]Tr^[f](^[t]x, ^[f]N^[f](^[f]y)) -> ^[f]Wr^[t](^[t]check^[f](^[t]x), ^[f]y)

^[f]Tr^[f](^[t]x, ^[t]N^[t](^[t]y)) -> ^[f]Wr^[f](^[t]check^[f](^[t]x), ^[t]y)

^[f]Tr^[f](^[f]x, ^[f]N^[f](^[f]y)) -> ^[f]Wr^[t](^[f]x, ^[f]check^[f](^[f]y))

^[f]Tr^[f](^[f]x, ^[t]N^[t](^[t]y)) -> ^[f]Wr^[f](^[f]x, ^[t]check^[f](^[t]y))

^[f]B^[t] -> ^[f]N^[f](^[f]B^[t])

^[t]check^[f](^[t]O^[f](^[f]x)) -> ^[t]ok^[f](^[t]O^[f](^[f]x))

^[f]Wl^[t](^[f]ok^[t](^[f]x), ^[f]y) -> ^[f]Tl^[f](^[f]x, ^[f]y)

^[f]Wl^[f](^[f]ok^[t](^[f]x), ^[t]y) -> ^[f]Tl^[f](^[f]x, ^[t]y)

^[f]Wl^[t](^[t]ok^[f](^[t]x), ^[f]y) -> ^[f]Tl^[t](^[t]x, ^[f]y)

^[f]Wl^[f](^[t]ok^[f](^[t]x), ^[t]y) -> ^[f]Tl^[t](^[t]x, ^[t]y)

^[f]Wl^[t](^[f]x, ^[f]ok^[t](^[f]y)) -> ^[f]Tl^[f](^[f]x, ^[f]y)

^[f]Wl^[f](^[f]x, ^[t]ok^[f](^[t]y)) -> ^[f]Tl^[f](^[f]x, ^[t]y)

^[f]Wl^[t](^[t]x, ^[f]ok^[t](^[f]y)) -> ^[f]Tl^[t](^[t]x, ^[f]y)

^[f]Wl^[f](^[t]x, ^[t]ok^[f](^[t]y)) -> ^[f]Tl^[t](^[t]x, ^[t]y)

^[f]Wr^[t](^[f]ok^[t](^[f]x), ^[f]y) -> ^[f]Tr^[f](^[f]x, ^[f]y)

^[f]Wr^[f](^[f]ok^[t](^[f]x), ^[t]y) -> ^[f]Tr^[f](^[f]x, ^[t]y)

^[f]Wr^[t](^[t]ok^[f](^[t]x), ^[f]y) -> ^[f]Tr^[f](^[t]x, ^[f]y)

^[f]Wr^[f](^[t]ok^[f](^[t]x), ^[t]y) -> ^[f]Tr^[f](^[t]x, ^[t]y)

^[f]Wr^[t](^[f]x, ^[f]ok^[t](^[f]y)) -> ^[f]Tr^[f](^[f]x, ^[f]y)

^[f]Wr^[f](^[f]x, ^[t]ok^[f](^[t]y)) -> ^[f]Tr^[f](^[f]x, ^[t]y)

^[t]check^[f](^[t]O^[f](^[f]x)) -> ^[t]O^[f](^[f]check^[f](^[f]x))

^[t]check^[f](^[t]O^[f](^[t]x)) -> ^[t]O^[f](^[t]check^[f](^[t]x))

^[f]check^[f](^[f]N^[f](^[f]x)) -> ^[f]N^[f](^[f]check^[f](^[f]x))

^[t]check^[f](^[t]N^[t](^[t]x)) -> ^[t]N^[t](^[t]check^[f](^[t]x))

^[t]O^[f](^[f]ok^[t](^[f]x)) -> ^[t]ok^[f](^[t]O^[f](^[f]x))

^[t]O^[f](^[t]ok^[f](^[t]x)) -> ^[t]ok^[f](^[t]O^[f](^[t]x))

^[f]N^[f](^[f]ok^[t](^[f]x)) -> ^[f]ok^[t](^[f]N^[f](^[f]x))

^[t]N^[t](^[t]ok^[f](^[t]x)) -> ^[t]ok^[f](^[t]N^[t](^[t]x))

^[f]Tl^[f](^[f]N^[f](^[f]x), ^[f]y) -> ^[f]Wr^[t](^[f]check^[f](^[f]x), ^[f]y)

^[f]Tl^[f](^[f]N^[f](^[f]x), ^[t]y) -> ^[f]Wr^[f](^[f]check^[f](^[f]x), ^[t]y)

^[f]Tl^[t](^[t]N^[t](^[t]x), ^[f]y) -> ^[f]Wr^[t](^[t]check^[f](^[t]x), ^[f]y)

^[f]Tl^[t](^[t]N^[t](^[t]x), ^[t]y) -> ^[f]Wr^[f](^[t]check^[f](^[t]x), ^[t]y)

^[f]Tl^[f](^[f]N^[f](^[f]x), ^[f]y) -> ^[f]Wr^[t](^[f]x, ^[f]check^[f](^[f]y))

^[f]Tl^[f](^[f]N^[f](^[f]x), ^[t]y) -> ^[f]Wr^[f](^[f]x, ^[t]check^[f](^[t]y))

^[f]Tl^[t](^[t]N^[t](^[t]x), ^[f]y) -> ^[f]Wr^[t](^[t]x, ^[f]check^[f](^[f]y))

^[f]Tl^[t](^[t]N^[t](^[t]x), ^[t]y) -> ^[f]Wr^[f](^[t]x, ^[t]check^[f](^[t]y))

^[f]Tr^[f](^[f]x, ^[f]N^[f](^[f]y)) -> ^[f]Wl^[t](^[f]check^[f](^[f]x), ^[f]y)

^[f]Tr^[f](^[f]x, ^[t]N^[t](^[t]y)) -> ^[f]Wl^[f](^[f]check^[f](^[f]x), ^[t]y)

^[f]Tr^[f](^[t]x, ^[f]N^[f](^[f]y)) -> ^[f]Wl^[t](^[t]check^[f](^[t]x), ^[f]y)

^[f]Tr^[f](^[t]x, ^[t]N^[t](^[t]y)) -> ^[f]Wl^[f](^[t]check^[f](^[t]x), ^[t]y)

^[f]Tr^[f](^[f]x, ^[f]N^[f](^[f]y)) -> ^[f]Wl^[t](^[f]x, ^[f]check^[f](^[f]y))

^[f]Tr^[f](^[f]x, ^[t]N^[t](^[t]y)) -> ^[f]Wl^[f](^[f]x, ^[t]check^[f](^[t]y))

^[f]Tl^[f](^[f]B^[t], ^[f]y) -> ^[f]Wr^[t](^[f]B^[t], ^[f]check^[f](^[f]y))

^[f]Tl^[f](^[f]B^[t], ^[t]y) -> ^[f]Wr^[f](^[f]B^[t], ^[t]check^[f](^[t]y))

^[f]Tr^[f](^[f]x, ^[f]B^[t]) -> ^[f]Wl^[t](^[f]check^[f](^[f]x), ^[f]B^[t])

^[f]Tr^[f](^[t]x, ^[f]B^[t]) -> ^[f]Wl^[t](^[t]check^[f](^[t]x), ^[f]B^[t])





Our polynomial interpretation was:

P(Tl^[false])(x_1,x_2) = 1 + 1*x_1 + 1*x_2

P(Tl^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2

P(N^[false])(x_1) = 0 + 1*x_1

P(N^[true])(x_1) = 1 + 1*x_1

P(Wl^[false])(x_1,x_2) = 1 + 1*x_1 + 1*x_2

P(Wl^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2

P(check^[false])(x_1) = 0 + 1*x_1

P(check^[true])(x_1) = 0 + 1*x_1

P(Tr^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2

P(Tr^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2

P(Wr^[false])(x_1,x_2) = 1 + 1*x_1 + 1*x_2

P(Wr^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2

P(B^[false])() = 0

P(B^[true])() = 0

P(O^[false])(x_1) = 0 + 1*x_1

P(O^[true])(x_1) = 0 + 1*x_1

P(ok^[false])(x_1) = 0 + 1*x_1

P(ok^[true])(x_1) = 1 + 1*x_1


The following rules were deleted from R:
none

The following rules were deleted from S:

   Wr(x, ok(y)) -> Tr(x, y)




----------------------------------------

(8)
Obligation:
Relative term rewrite system:
The relative TRS consists of the following R rules:

   Tl(N(x), y) -> Wr(check(x), y)
   Tl(N(x), y) -> Wr(x, check(y))
   Tr(x, N(y)) -> Wl(check(x), y)
   Tr(x, N(y)) -> Wl(x, check(y))
   Tl(B, y) -> Wr(B, check(y))
   Tr(x, B) -> Wl(check(x), B)

The relative TRS consists of the following S rules:

   Tl(N(x), y) -> Wl(check(x), y)
   Tl(N(x), y) -> Wl(x, check(y))
   Tr(x, N(y)) -> Wr(check(x), y)
   Tr(x, N(y)) -> Wr(x, check(y))
   B -> N(B)
   check(O(x)) -> ok(O(x))
   Wl(ok(x), y) -> Tl(x, y)
   Wl(x, ok(y)) -> Tl(x, y)
   Wr(ok(x), y) -> Tr(x, y)
   check(O(x)) -> O(check(x))
   check(N(x)) -> N(check(x))
   O(ok(x)) -> ok(O(x))
   N(ok(x)) -> ok(N(x))


----------------------------------------

(9) RelTRSRRRProof (EQUIVALENT)
We used the following monotonic ordering for rule removal:
Matrix interpretation [MATRO] to (N^2, +, *, >=, >) :

   <<<
 POL(Tl(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 1], [0, 0]] 	* 	x_1 	 +  	[[1, 0], [0, 0]] 	* 	x_2
>>>

   <<<
 POL(N(x_1)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 1]] 	* 	x_1
>>>

   <<<
 POL(Wr(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 0]] 	* 	x_1 	 +  	[[1, 0], [0, 0]] 	* 	x_2
>>>

   <<<
 POL(check(x_1)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 0]] 	* 	x_1
>>>

   <<<
 POL(Tr(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 1], [0, 0]] 	* 	x_1 	 +  	[[1, 0], [0, 0]] 	* 	x_2
>>>

   <<<
 POL(Wl(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 1], [0, 0]] 	* 	x_1 	 +  	[[1, 0], [0, 0]] 	* 	x_2
>>>

   <<<
 POL(B) =  	[[0], [1]]
>>>

   <<<
 POL(O(x_1)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 0]] 	* 	x_1
>>>

   <<<
 POL(ok(x_1)) =  	[[0], [0]] 	 +  	[[1, 1], [0, 0]] 	* 	x_1
>>>

With this ordering the following rules can be removed [MATRO] because they are oriented strictly:
Rules from R:

   Tl(B, y) -> Wr(B, check(y))
Rules from S:
none




----------------------------------------

(10)
Obligation:
Relative term rewrite system:
The relative TRS consists of the following R rules:

   Tl(N(x), y) -> Wr(check(x), y)
   Tl(N(x), y) -> Wr(x, check(y))
   Tr(x, N(y)) -> Wl(check(x), y)
   Tr(x, N(y)) -> Wl(x, check(y))
   Tr(x, B) -> Wl(check(x), B)

The relative TRS consists of the following S rules:

   Tl(N(x), y) -> Wl(check(x), y)
   Tl(N(x), y) -> Wl(x, check(y))
   Tr(x, N(y)) -> Wr(check(x), y)
   Tr(x, N(y)) -> Wr(x, check(y))
   B -> N(B)
   check(O(x)) -> ok(O(x))
   Wl(ok(x), y) -> Tl(x, y)
   Wl(x, ok(y)) -> Tl(x, y)
   Wr(ok(x), y) -> Tr(x, y)
   check(O(x)) -> O(check(x))
   check(N(x)) -> N(check(x))
   O(ok(x)) -> ok(O(x))
   N(ok(x)) -> ok(N(x))


----------------------------------------

(11) RelTRSSemanticLabellingPOLOProof (EQUIVALENT)
We use Semantic Labelling over tuples of bools combined with a polynomial order [SEMLAB]



We use semantic labelling over boolean tuples of size 1.



We used the following model:

Tl_2: component 1: AND[]

N_1: component 1: OR[x_1^1]

Wl_2: component 1: AND[]

check_1: component 1: OR[x_1^1]

Tr_2: component 1: AND[]

Wr_2: component 1: AND[]

B_0: component 1: AND[]

O_1: component 1: OR[]

ok_1: component 1: OR[]



Our labelling function was:

Tl_2:component 1: XOR[-x_2^1]

N_1:component 1: XOR[-x_1^1]

Wl_2:component 1: AND[x_1^1]

check_1:component 1: OR[]

Tr_2:component 1: XOR[x_2^1]

Wr_2:component 1: AND[-x_1^1, x_2^1]

B_0:component 1: XOR[]

O_1:component 1: OR[]

ok_1:component 1: XOR[]





Our labelled system was:

^[t]Tl^[t](^[f]N^[t](^[f]x), ^[f]y) -> ^[t]Wl^[f](^[f]check^[f](^[f]x), ^[f]y)

^[t]Tl^[f](^[f]N^[t](^[f]x), ^[t]y) -> ^[t]Wl^[f](^[f]check^[f](^[f]x), ^[t]y)

^[t]Tl^[t](^[t]N^[f](^[t]x), ^[f]y) -> ^[t]Wl^[t](^[t]check^[f](^[t]x), ^[f]y)

^[t]Tl^[f](^[t]N^[f](^[t]x), ^[t]y) -> ^[t]Wl^[t](^[t]check^[f](^[t]x), ^[t]y)

^[t]Tl^[t](^[f]N^[t](^[f]x), ^[f]y) -> ^[t]Wl^[f](^[f]x, ^[f]check^[f](^[f]y))

^[t]Tl^[f](^[f]N^[t](^[f]x), ^[t]y) -> ^[t]Wl^[f](^[f]x, ^[t]check^[f](^[t]y))

^[t]Tl^[t](^[t]N^[f](^[t]x), ^[f]y) -> ^[t]Wl^[t](^[t]x, ^[f]check^[f](^[f]y))

^[t]Tl^[f](^[t]N^[f](^[t]x), ^[t]y) -> ^[t]Wl^[t](^[t]x, ^[t]check^[f](^[t]y))

^[t]Tr^[f](^[f]x, ^[f]N^[t](^[f]y)) -> ^[t]Wr^[f](^[f]check^[f](^[f]x), ^[f]y)

^[t]Tr^[t](^[f]x, ^[t]N^[f](^[t]y)) -> ^[t]Wr^[t](^[f]check^[f](^[f]x), ^[t]y)

^[t]Tr^[f](^[t]x, ^[f]N^[t](^[f]y)) -> ^[t]Wr^[f](^[t]check^[f](^[t]x), ^[f]y)

^[t]Tr^[t](^[t]x, ^[t]N^[f](^[t]y)) -> ^[t]Wr^[f](^[t]check^[f](^[t]x), ^[t]y)

^[t]Tr^[f](^[f]x, ^[f]N^[t](^[f]y)) -> ^[t]Wr^[f](^[f]x, ^[f]check^[f](^[f]y))

^[t]Tr^[t](^[f]x, ^[t]N^[f](^[t]y)) -> ^[t]Wr^[t](^[f]x, ^[t]check^[f](^[t]y))

^[t]Tr^[t](^[t]x, ^[t]N^[f](^[t]y)) -> ^[t]Wr^[f](^[t]x, ^[t]check^[f](^[t]y))

^[t]B^[f] -> ^[t]N^[f](^[t]B^[f])

^[f]check^[f](^[f]O^[f](^[f]x)) -> ^[f]ok^[f](^[f]O^[f](^[f]x))

^[t]Wl^[f](^[f]ok^[f](^[f]x), ^[f]y) -> ^[t]Tl^[t](^[f]x, ^[f]y)

^[t]Wl^[f](^[f]ok^[f](^[f]x), ^[t]y) -> ^[t]Tl^[f](^[f]x, ^[t]y)

^[t]Wl^[f](^[f]x, ^[f]ok^[f](^[f]y)) -> ^[t]Tl^[t](^[f]x, ^[f]y)

^[t]Wl^[f](^[f]x, ^[f]ok^[f](^[t]y)) -> ^[t]Tl^[f](^[f]x, ^[t]y)

^[t]Wl^[t](^[t]x, ^[f]ok^[f](^[f]y)) -> ^[t]Tl^[t](^[t]x, ^[f]y)

^[t]Wl^[t](^[t]x, ^[f]ok^[f](^[t]y)) -> ^[t]Tl^[f](^[t]x, ^[t]y)

^[t]Wr^[f](^[f]ok^[f](^[f]x), ^[f]y) -> ^[t]Tr^[f](^[f]x, ^[f]y)

^[t]Wr^[t](^[f]ok^[f](^[f]x), ^[t]y) -> ^[t]Tr^[t](^[f]x, ^[t]y)

^[f]check^[f](^[f]O^[f](^[f]x)) -> ^[f]O^[f](^[f]check^[f](^[f]x))

^[f]check^[f](^[f]O^[f](^[t]x)) -> ^[f]O^[f](^[t]check^[f](^[t]x))

^[f]check^[f](^[f]N^[t](^[f]x)) -> ^[f]N^[t](^[f]check^[f](^[f]x))

^[t]check^[f](^[t]N^[f](^[t]x)) -> ^[t]N^[f](^[t]check^[f](^[t]x))

^[f]O^[f](^[f]ok^[f](^[f]x)) -> ^[f]ok^[f](^[f]O^[f](^[f]x))

^[f]N^[t](^[f]ok^[f](^[f]x)) -> ^[f]ok^[f](^[f]N^[t](^[f]x))

^[f]N^[t](^[f]ok^[f](^[t]x)) -> ^[f]ok^[f](^[t]N^[f](^[t]x))

^[t]Tl^[t](^[f]N^[t](^[f]x), ^[f]y) -> ^[t]Wr^[f](^[f]check^[f](^[f]x), ^[f]y)

^[t]Tl^[f](^[f]N^[t](^[f]x), ^[t]y) -> ^[t]Wr^[t](^[f]check^[f](^[f]x), ^[t]y)

^[t]Tl^[t](^[t]N^[f](^[t]x), ^[f]y) -> ^[t]Wr^[f](^[t]check^[f](^[t]x), ^[f]y)

^[t]Tl^[f](^[t]N^[f](^[t]x), ^[t]y) -> ^[t]Wr^[f](^[t]check^[f](^[t]x), ^[t]y)

^[t]Tl^[t](^[f]N^[t](^[f]x), ^[f]y) -> ^[t]Wr^[f](^[f]x, ^[f]check^[f](^[f]y))

^[t]Tl^[f](^[f]N^[t](^[f]x), ^[t]y) -> ^[t]Wr^[t](^[f]x, ^[t]check^[f](^[t]y))

^[t]Tl^[t](^[t]N^[f](^[t]x), ^[f]y) -> ^[t]Wr^[f](^[t]x, ^[f]check^[f](^[f]y))

^[t]Tl^[f](^[t]N^[f](^[t]x), ^[t]y) -> ^[t]Wr^[f](^[t]x, ^[t]check^[f](^[t]y))

^[t]Tr^[f](^[f]x, ^[f]N^[t](^[f]y)) -> ^[t]Wl^[f](^[f]check^[f](^[f]x), ^[f]y)

^[t]Tr^[t](^[f]x, ^[t]N^[f](^[t]y)) -> ^[t]Wl^[f](^[f]check^[f](^[f]x), ^[t]y)

^[t]Tr^[f](^[t]x, ^[f]N^[t](^[f]y)) -> ^[t]Wl^[t](^[t]check^[f](^[t]x), ^[f]y)

^[t]Tr^[t](^[t]x, ^[t]N^[f](^[t]y)) -> ^[t]Wl^[t](^[t]check^[f](^[t]x), ^[t]y)

^[t]Tr^[f](^[f]x, ^[f]N^[t](^[f]y)) -> ^[t]Wl^[f](^[f]x, ^[f]check^[f](^[f]y))

^[t]Tr^[t](^[f]x, ^[t]N^[f](^[t]y)) -> ^[t]Wl^[f](^[f]x, ^[t]check^[f](^[t]y))

^[t]Tr^[f](^[t]x, ^[f]N^[t](^[f]y)) -> ^[t]Wl^[t](^[t]x, ^[f]check^[f](^[f]y))

^[t]Tr^[t](^[t]x, ^[t]N^[f](^[t]y)) -> ^[t]Wl^[t](^[t]x, ^[t]check^[f](^[t]y))

^[t]Tr^[t](^[f]x, ^[t]B^[f]) -> ^[t]Wl^[f](^[f]check^[f](^[f]x), ^[t]B^[f])

^[t]Tr^[t](^[t]x, ^[t]B^[f]) -> ^[t]Wl^[t](^[t]check^[f](^[t]x), ^[t]B^[f])





Our polynomial interpretation was:

P(Tl^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2

P(Tl^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2

P(N^[false])(x_1) = 0 + 1*x_1

P(N^[true])(x_1) = 1 + 1*x_1

P(Wl^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2

P(Wl^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2

P(check^[false])(x_1) = 0 + 1*x_1

P(check^[true])(x_1) = 0 + 1*x_1

P(Tr^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2

P(Tr^[true])(x_1,x_2) = 1 + 1*x_1 + 1*x_2

P(Wr^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2

P(Wr^[true])(x_1,x_2) = 1 + 1*x_1 + 1*x_2

P(B^[false])() = 0

P(B^[true])() = 0

P(O^[false])(x_1) = 0 + 1*x_1

P(O^[true])(x_1) = 0 + 1*x_1

P(ok^[false])(x_1) = 0 + 1*x_1

P(ok^[true])(x_1) = 0 + 1*x_1


The following rules were deleted from R:

   Tr(x, N(y)) -> Wl(check(x), y)
   Tr(x, N(y)) -> Wl(x, check(y))

The following rules were deleted from S:
none




----------------------------------------

(12)
Obligation:
Relative term rewrite system:
The relative TRS consists of the following R rules:

   Tl(N(x), y) -> Wr(check(x), y)
   Tl(N(x), y) -> Wr(x, check(y))
   Tr(x, B) -> Wl(check(x), B)

The relative TRS consists of the following S rules:

   Tl(N(x), y) -> Wl(check(x), y)
   Tl(N(x), y) -> Wl(x, check(y))
   Tr(x, N(y)) -> Wr(check(x), y)
   Tr(x, N(y)) -> Wr(x, check(y))
   B -> N(B)
   check(O(x)) -> ok(O(x))
   Wl(ok(x), y) -> Tl(x, y)
   Wl(x, ok(y)) -> Tl(x, y)
   Wr(ok(x), y) -> Tr(x, y)
   check(O(x)) -> O(check(x))
   check(N(x)) -> N(check(x))
   O(ok(x)) -> ok(O(x))
   N(ok(x)) -> ok(N(x))


----------------------------------------

(13) RelTRSRRRProof (EQUIVALENT)
We used the following monotonic ordering for rule removal:
Matrix interpretation [MATRO] to (N^2, +, *, >=, >) :

   <<<
 POL(Tl(x_1, x_2)) =  	[[1], [0]] 	 +  	[[1, 1], [0, 0]] 	* 	x_1 	 +  	[[1, 1], [0, 0]] 	* 	x_2
>>>

   <<<
 POL(N(x_1)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 1]] 	* 	x_1
>>>

   <<<
 POL(Wr(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 1], [0, 0]] 	* 	x_1 	 +  	[[1, 0], [0, 0]] 	* 	x_2
>>>

   <<<
 POL(check(x_1)) =  	[[0], [1]] 	 +  	[[1, 0], [0, 1]] 	* 	x_1
>>>

   <<<
 POL(Tr(x_1, x_2)) =  	[[1], [0]] 	 +  	[[1, 1], [0, 0]] 	* 	x_1 	 +  	[[1, 0], [0, 0]] 	* 	x_2
>>>

   <<<
 POL(B) =  	[[0], [0]]
>>>

   <<<
 POL(Wl(x_1, x_2)) =  	[[0], [0]] 	 +  	[[1, 1], [0, 0]] 	* 	x_1 	 +  	[[1, 1], [0, 0]] 	* 	x_2
>>>

   <<<
 POL(O(x_1)) =  	[[0], [0]] 	 +  	[[1, 0], [0, 1]] 	* 	x_1
>>>

   <<<
 POL(ok(x_1)) =  	[[0], [1]] 	 +  	[[1, 0], [0, 1]] 	* 	x_1
>>>

With this ordering the following rules can be removed [MATRO] because they are oriented strictly:
Rules from R:

   Tl(N(x), y) -> Wr(x, check(y))
Rules from S:

   Tr(x, N(y)) -> Wr(x, check(y))




----------------------------------------

(14)
Obligation:
Relative term rewrite system:
The relative TRS consists of the following R rules:

   Tl(N(x), y) -> Wr(check(x), y)
   Tr(x, B) -> Wl(check(x), B)

The relative TRS consists of the following S rules:

   Tl(N(x), y) -> Wl(check(x), y)
   Tl(N(x), y) -> Wl(x, check(y))
   Tr(x, N(y)) -> Wr(check(x), y)
   B -> N(B)
   check(O(x)) -> ok(O(x))
   Wl(ok(x), y) -> Tl(x, y)
   Wl(x, ok(y)) -> Tl(x, y)
   Wr(ok(x), y) -> Tr(x, y)
   check(O(x)) -> O(check(x))
   check(N(x)) -> N(check(x))
   O(ok(x)) -> ok(O(x))
   N(ok(x)) -> ok(N(x))


----------------------------------------

(15) RelTRSSemanticLabellingPOLOProof (EQUIVALENT)
We use Semantic Labelling over tuples of bools combined with a polynomial order [SEMLAB]



We use semantic labelling over boolean tuples of size 1.



We used the following model:

Tl_2: component 1: AND[]

N_1: component 1: OR[x_1^1]

Wl_2: component 1: AND[]

check_1: component 1: OR[x_1^1]

Tr_2: component 1: AND[]

Wr_2: component 1: AND[]

B_0: component 1: AND[]

O_1: component 1: OR[]

ok_1: component 1: OR[]



Our labelling function was:

Tl_2:component 1: XOR[x_1^1]

N_1:component 1: OR[-x_1^1]

Wl_2:component 1: XOR[-x_1^1]

check_1:component 1: OR[]

Tr_2:component 1: XOR[x_1^1]

Wr_2:component 1: XOR[]

B_0:component 1: AND[]

O_1:component 1: OR[]

ok_1:component 1: XOR[x_1^1]





Our labelled system was:

^[t]Tl^[f](^[f]N^[t](^[f]x), ^[f]y) -> ^[t]Wl^[t](^[f]check^[f](^[f]x), ^[f]y)

^[t]Tl^[t](^[t]N^[f](^[t]x), ^[f]y) -> ^[t]Wl^[f](^[t]check^[f](^[t]x), ^[f]y)

^[t]Tl^[f](^[f]N^[t](^[f]x), ^[f]y) -> ^[t]Wl^[t](^[f]x, ^[f]check^[f](^[f]y))

^[t]Tl^[f](^[f]N^[t](^[f]x), ^[t]y) -> ^[t]Wl^[t](^[f]x, ^[t]check^[f](^[t]y))

^[t]Tl^[t](^[t]N^[f](^[t]x), ^[f]y) -> ^[t]Wl^[f](^[t]x, ^[f]check^[f](^[f]y))

^[t]Tl^[t](^[t]N^[f](^[t]x), ^[t]y) -> ^[t]Wl^[f](^[t]x, ^[t]check^[f](^[t]y))

^[t]Tr^[f](^[f]x, ^[f]N^[t](^[f]y)) -> ^[t]Wr^[f](^[f]check^[f](^[f]x), ^[f]y)

^[t]Tr^[f](^[f]x, ^[t]N^[f](^[t]y)) -> ^[t]Wr^[f](^[f]check^[f](^[f]x), ^[t]y)

^[t]Tr^[t](^[t]x, ^[f]N^[t](^[f]y)) -> ^[t]Wr^[f](^[t]check^[f](^[t]x), ^[f]y)

^[t]Tr^[t](^[t]x, ^[t]N^[f](^[t]y)) -> ^[t]Wr^[f](^[t]check^[f](^[t]x), ^[t]y)

^[t]B^[t] -> ^[t]N^[f](^[t]B^[t])

^[f]check^[f](^[f]O^[f](^[f]x)) -> ^[f]ok^[f](^[f]O^[f](^[f]x))

^[t]Wl^[t](^[f]ok^[f](^[f]x), ^[f]y) -> ^[t]Tl^[f](^[f]x, ^[f]y)

^[t]Wl^[t](^[f]ok^[t](^[t]x), ^[f]y) -> ^[t]Tl^[t](^[t]x, ^[f]y)

^[t]Wl^[t](^[f]x, ^[f]ok^[f](^[f]y)) -> ^[t]Tl^[f](^[f]x, ^[f]y)

^[t]Wl^[t](^[f]x, ^[f]ok^[t](^[t]y)) -> ^[t]Tl^[f](^[f]x, ^[t]y)

^[t]Wl^[f](^[t]x, ^[f]ok^[f](^[f]y)) -> ^[t]Tl^[t](^[t]x, ^[f]y)

^[t]Wl^[f](^[t]x, ^[f]ok^[t](^[t]y)) -> ^[t]Tl^[t](^[t]x, ^[t]y)

^[t]Wr^[f](^[f]ok^[f](^[f]x), ^[f]y) -> ^[t]Tr^[f](^[f]x, ^[f]y)

^[t]Wr^[f](^[f]ok^[t](^[t]x), ^[f]y) -> ^[t]Tr^[t](^[t]x, ^[f]y)

^[f]check^[f](^[f]O^[f](^[f]x)) -> ^[f]O^[f](^[f]check^[f](^[f]x))

^[f]check^[f](^[f]O^[f](^[t]x)) -> ^[f]O^[f](^[t]check^[f](^[t]x))

^[f]check^[f](^[f]N^[t](^[f]x)) -> ^[f]N^[t](^[f]check^[f](^[f]x))

^[t]check^[f](^[t]N^[f](^[t]x)) -> ^[t]N^[f](^[t]check^[f](^[t]x))

^[f]O^[f](^[f]ok^[f](^[f]x)) -> ^[f]ok^[f](^[f]O^[f](^[f]x))

^[f]O^[f](^[f]ok^[t](^[t]x)) -> ^[f]ok^[f](^[f]O^[f](^[t]x))

^[f]N^[t](^[f]ok^[f](^[f]x)) -> ^[f]ok^[f](^[f]N^[t](^[f]x))

^[f]N^[t](^[f]ok^[t](^[t]x)) -> ^[f]ok^[t](^[t]N^[f](^[t]x))

^[t]Tl^[f](^[f]N^[t](^[f]x), ^[f]y) -> ^[t]Wr^[f](^[f]check^[f](^[f]x), ^[f]y)

^[t]Tl^[t](^[t]N^[f](^[t]x), ^[f]y) -> ^[t]Wr^[f](^[t]check^[f](^[t]x), ^[f]y)

^[t]Tr^[f](^[f]x, ^[t]B^[t]) -> ^[t]Wl^[t](^[f]check^[f](^[f]x), ^[t]B^[t])

^[t]Tr^[t](^[t]x, ^[t]B^[t]) -> ^[t]Wl^[f](^[t]check^[f](^[t]x), ^[t]B^[t])





Our polynomial interpretation was:

P(Tl^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2

P(Tl^[true])(x_1,x_2) = 1 + 1*x_1 + 1*x_2

P(N^[false])(x_1) = 0 + 1*x_1

P(N^[true])(x_1) = 1 + 1*x_1

P(Wl^[false])(x_1,x_2) = 1 + 1*x_1 + 1*x_2

P(Wl^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2

P(check^[false])(x_1) = 0 + 1*x_1

P(check^[true])(x_1) = 0 + 1*x_1

P(Tr^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2

P(Tr^[true])(x_1,x_2) = 1 + 1*x_1 + 1*x_2

P(Wr^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2

P(Wr^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2

P(B^[false])() = 0

P(B^[true])() = 0

P(O^[false])(x_1) = 0 + 1*x_1

P(O^[true])(x_1) = 0 + 1*x_1

P(ok^[false])(x_1) = 0 + 1*x_1

P(ok^[true])(x_1) = 1 + 1*x_1


The following rules were deleted from R:

   Tl(N(x), y) -> Wr(check(x), y)

The following rules were deleted from S:
none




----------------------------------------

(16)
Obligation:
Relative term rewrite system:
The relative TRS consists of the following R rules:

   Tr(x, B) -> Wl(check(x), B)

The relative TRS consists of the following S rules:

   Tl(N(x), y) -> Wl(check(x), y)
   Tl(N(x), y) -> Wl(x, check(y))
   Tr(x, N(y)) -> Wr(check(x), y)
   B -> N(B)
   check(O(x)) -> ok(O(x))
   Wl(ok(x), y) -> Tl(x, y)
   Wl(x, ok(y)) -> Tl(x, y)
   Wr(ok(x), y) -> Tr(x, y)
   check(O(x)) -> O(check(x))
   check(N(x)) -> N(check(x))
   O(ok(x)) -> ok(O(x))
   N(ok(x)) -> ok(N(x))


----------------------------------------

(17) RelTRSRRRProof (EQUIVALENT)
We used the following monotonic ordering for rule removal:
Polynomial interpretation [POLO]:

   POL(B) = 0
   POL(N(x_1)) = x_1
   POL(O(x_1)) = x_1
   POL(Tl(x_1, x_2)) = x_1 + x_2
   POL(Tr(x_1, x_2)) = 1 + x_1 + x_2
   POL(Wl(x_1, x_2)) = x_1 + x_2
   POL(Wr(x_1, x_2)) = 1 + x_1 + x_2
   POL(check(x_1)) = x_1
   POL(ok(x_1)) = x_1
With this ordering the following rules can be removed [MATRO] because they are oriented strictly:
Rules from R:

   Tr(x, B) -> Wl(check(x), B)
Rules from S:
none




----------------------------------------

(18)
Obligation:
Relative term rewrite system:
R is empty.
The relative TRS consists of the following S rules:

   Tl(N(x), y) -> Wl(check(x), y)
   Tl(N(x), y) -> Wl(x, check(y))
   Tr(x, N(y)) -> Wr(check(x), y)
   B -> N(B)
   check(O(x)) -> ok(O(x))
   Wl(ok(x), y) -> Tl(x, y)
   Wl(x, ok(y)) -> Tl(x, y)
   Wr(ok(x), y) -> Tr(x, y)
   check(O(x)) -> O(check(x))
   check(N(x)) -> N(check(x))
   O(ok(x)) -> ok(O(x))
   N(ok(x)) -> ok(N(x))


----------------------------------------

(19) RIsEmptyProof (EQUIVALENT)
The TRS R is empty. Hence, termination is trivially proven.
----------------------------------------

(20)
YES