14.65/4.58 YES 14.65/4.61 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 14.65/4.61 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 14.65/4.61 14.65/4.61 14.65/4.61 Termination of the given RelTRS could be proven: 14.65/4.61 14.65/4.61 (0) RelTRS 14.65/4.61 (1) RelTRSRRRProof [EQUIVALENT, 77 ms] 14.65/4.61 (2) RelTRS 14.65/4.61 (3) RelTRSRRRProof [EQUIVALENT, 53 ms] 14.65/4.61 (4) RelTRS 14.65/4.61 (5) RelTRSSemanticLabellingPOLOProof [EQUIVALENT, 213 ms] 14.65/4.61 (6) RelTRS 14.65/4.61 (7) RelTRSSemanticLabellingPOLOProof [EQUIVALENT, 159 ms] 14.65/4.61 (8) RelTRS 14.65/4.61 (9) RelTRSSemanticLabellingPOLOProof [EQUIVALENT, 71 ms] 14.65/4.61 (10) RelTRS 14.65/4.61 (11) RIsEmptyProof [EQUIVALENT, 0 ms] 14.65/4.61 (12) YES 14.65/4.61 14.65/4.61 14.65/4.61 ---------------------------------------- 14.65/4.61 14.65/4.61 (0) 14.65/4.61 Obligation: 14.65/4.61 Relative term rewrite system: 14.65/4.61 The relative TRS consists of the following R rules: 14.65/4.61 14.65/4.61 top(ok(queue(old(x), bot))) -> top(check(queue(x, bot))) 14.65/4.61 top(ok(queue(new(x), bot))) -> top(check(queue(x, bot))) 14.65/4.61 top(ok(queue(bot, old(x)))) -> top(check(queue(bot, x))) 14.65/4.61 top(ok(queue(bot, new(x)))) -> top(check(queue(bot, x))) 14.65/4.61 top(ok(queue(old(x), old(y)))) -> top(check(queue(x, y))) 14.65/4.61 top(ok(queue(old(x), new(y)))) -> top(check(queue(x, y))) 14.65/4.61 top(ok(queue(new(x), old(y)))) -> top(check(queue(x, y))) 14.65/4.61 top(ok(queue(new(x), new(y)))) -> top(check(queue(x, y))) 14.65/4.61 14.65/4.61 The relative TRS consists of the following S rules: 14.65/4.61 14.65/4.61 top(ok(queue(old(x), y))) -> top(check(queue(x, y))) 14.65/4.61 top(ok(queue(new(x), y))) -> top(check(queue(x, y))) 14.65/4.61 bot -> new(bot) 14.65/4.61 check(old(x)) -> ok(old(x)) 14.65/4.61 check(new(x)) -> new(check(x)) 14.65/4.61 check(queue(x, y)) -> queue(check(x), y) 14.65/4.61 check(queue(x, y)) -> queue(x, check(y)) 14.65/4.61 old(ok(x)) -> ok(old(x)) 14.65/4.61 new(ok(x)) -> ok(new(x)) 14.65/4.61 queue(ok(x), y) -> ok(queue(x, y)) 14.65/4.61 queue(x, ok(y)) -> ok(queue(x, y)) 14.65/4.61 14.65/4.61 14.65/4.61 ---------------------------------------- 14.65/4.61 14.65/4.61 (1) RelTRSRRRProof (EQUIVALENT) 14.65/4.61 We used the following monotonic ordering for rule removal: 14.65/4.61 Polynomial interpretation [POLO]: 14.65/4.61 14.65/4.61 POL(bot) = 0 14.65/4.61 POL(check(x_1)) = x_1 14.65/4.61 POL(new(x_1)) = x_1 14.65/4.61 POL(ok(x_1)) = x_1 14.65/4.61 POL(old(x_1)) = 1 + x_1 14.65/4.61 POL(queue(x_1, x_2)) = x_1 + x_2 14.65/4.61 POL(top(x_1)) = x_1 14.65/4.61 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 14.65/4.61 Rules from R: 14.65/4.61 14.65/4.61 top(ok(queue(old(x), bot))) -> top(check(queue(x, bot))) 14.65/4.61 top(ok(queue(bot, old(x)))) -> top(check(queue(bot, x))) 14.65/4.61 top(ok(queue(old(x), old(y)))) -> top(check(queue(x, y))) 14.65/4.61 top(ok(queue(old(x), new(y)))) -> top(check(queue(x, y))) 14.65/4.61 top(ok(queue(new(x), old(y)))) -> top(check(queue(x, y))) 14.65/4.61 Rules from S: 14.65/4.61 14.65/4.61 top(ok(queue(old(x), y))) -> top(check(queue(x, y))) 14.65/4.61 14.65/4.61 14.65/4.61 14.65/4.61 14.65/4.61 ---------------------------------------- 14.65/4.61 14.65/4.61 (2) 14.65/4.61 Obligation: 14.65/4.61 Relative term rewrite system: 14.65/4.61 The relative TRS consists of the following R rules: 14.65/4.61 14.65/4.61 top(ok(queue(new(x), bot))) -> top(check(queue(x, bot))) 14.65/4.61 top(ok(queue(bot, new(x)))) -> top(check(queue(bot, x))) 14.65/4.61 top(ok(queue(new(x), new(y)))) -> top(check(queue(x, y))) 14.65/4.61 14.65/4.61 The relative TRS consists of the following S rules: 14.65/4.61 14.65/4.61 top(ok(queue(new(x), y))) -> top(check(queue(x, y))) 14.65/4.61 bot -> new(bot) 14.65/4.61 check(old(x)) -> ok(old(x)) 14.65/4.61 check(new(x)) -> new(check(x)) 14.65/4.61 check(queue(x, y)) -> queue(check(x), y) 14.65/4.61 check(queue(x, y)) -> queue(x, check(y)) 14.65/4.61 old(ok(x)) -> ok(old(x)) 14.65/4.61 new(ok(x)) -> ok(new(x)) 14.65/4.61 queue(ok(x), y) -> ok(queue(x, y)) 14.65/4.61 queue(x, ok(y)) -> ok(queue(x, y)) 14.65/4.61 14.65/4.61 14.65/4.61 ---------------------------------------- 14.65/4.61 14.65/4.61 (3) RelTRSRRRProof (EQUIVALENT) 14.65/4.61 We used the following monotonic ordering for rule removal: 14.65/4.61 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 14.65/4.61 14.65/4.61 <<< 14.65/4.61 POL(top(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 14.65/4.61 >>> 14.65/4.61 14.65/4.61 <<< 14.65/4.61 POL(ok(x_1)) = [[0], [1]] + [[1, 0], [0, 1]] * x_1 14.65/4.61 >>> 14.65/4.61 14.65/4.61 <<< 14.65/4.61 POL(queue(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 14.65/4.61 >>> 14.65/4.61 14.65/4.61 <<< 14.65/4.61 POL(new(x_1)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 14.65/4.61 >>> 14.65/4.61 14.65/4.61 <<< 14.65/4.61 POL(bot) = [[0], [0]] 14.65/4.61 >>> 14.65/4.61 14.65/4.61 <<< 14.65/4.61 POL(check(x_1)) = [[0], [0]] + [[1, 0], [1, 1]] * x_1 14.65/4.61 >>> 14.65/4.61 14.65/4.61 <<< 14.65/4.61 POL(old(x_1)) = [[1], [1]] + [[1, 1], [0, 1]] * x_1 14.65/4.61 >>> 14.65/4.61 14.65/4.61 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 14.65/4.61 Rules from R: 14.65/4.61 none 14.65/4.61 Rules from S: 14.65/4.61 14.65/4.61 old(ok(x)) -> ok(old(x)) 14.65/4.61 14.65/4.61 14.65/4.61 14.65/4.61 14.65/4.61 ---------------------------------------- 14.65/4.61 14.65/4.61 (4) 14.65/4.61 Obligation: 14.65/4.61 Relative term rewrite system: 14.65/4.61 The relative TRS consists of the following R rules: 14.65/4.61 14.65/4.61 top(ok(queue(new(x), bot))) -> top(check(queue(x, bot))) 14.65/4.61 top(ok(queue(bot, new(x)))) -> top(check(queue(bot, x))) 14.65/4.61 top(ok(queue(new(x), new(y)))) -> top(check(queue(x, y))) 14.65/4.61 14.65/4.61 The relative TRS consists of the following S rules: 14.65/4.61 14.65/4.61 top(ok(queue(new(x), y))) -> top(check(queue(x, y))) 14.65/4.61 bot -> new(bot) 14.65/4.61 check(old(x)) -> ok(old(x)) 14.65/4.61 check(new(x)) -> new(check(x)) 14.65/4.61 check(queue(x, y)) -> queue(check(x), y) 14.65/4.61 check(queue(x, y)) -> queue(x, check(y)) 14.65/4.61 new(ok(x)) -> ok(new(x)) 14.65/4.61 queue(ok(x), y) -> ok(queue(x, y)) 14.65/4.61 queue(x, ok(y)) -> ok(queue(x, y)) 14.65/4.61 14.65/4.61 14.65/4.61 ---------------------------------------- 14.65/4.61 14.65/4.61 (5) RelTRSSemanticLabellingPOLOProof (EQUIVALENT) 14.65/4.61 We use Semantic Labelling over tuples of bools combined with a polynomial order [SEMLAB] 14.65/4.61 14.65/4.61 14.65/4.61 14.65/4.61 We use semantic labelling over boolean tuples of size 1. 14.65/4.61 14.65/4.61 14.65/4.61 14.65/4.61 We used the following model: 14.65/4.61 14.65/4.61 top_1: component 1: OR[] 14.65/4.61 14.65/4.61 ok_1: component 1: AND[] 14.65/4.61 14.65/4.61 queue_2: component 1: OR[x_1^1, x_2^1] 14.65/4.61 14.65/4.61 new_1: component 1: OR[x_1^1] 14.65/4.61 14.65/4.61 check_1: component 1: OR[x_1^1] 14.65/4.61 14.65/4.61 bot_0: component 1: OR[] 14.65/4.61 14.65/4.61 old_1: component 1: AND[] 14.65/4.61 14.65/4.61 14.65/4.61 14.65/4.61 Our labelling function was: 14.65/4.61 14.65/4.61 top_1:component 1: XOR[x_1^1] 14.65/4.61 14.65/4.61 ok_1:component 1: OR[] 14.65/4.61 14.65/4.61 queue_2:component 1: XOR[] 14.65/4.61 14.65/4.61 new_1:component 1: XOR[-x_1^1] 14.65/4.61 14.65/4.61 check_1:component 1: OR[x_1^1] 14.65/4.61 14.65/4.61 bot_0:component 1: AND[] 14.65/4.61 14.65/4.61 old_1:component 1: XOR[] 14.65/4.61 14.65/4.61 14.65/4.61 14.65/4.61 14.65/4.61 14.65/4.61 Our labelled system was: 14.65/4.61 14.65/4.61 ^[f]top^[t](^[t]ok^[f](^[f]queue^[f](^[f]new^[t](^[f]x), ^[f]y))) -> ^[f]top^[f](^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y))) 14.65/4.61 14.65/4.61 ^[f]top^[t](^[t]ok^[f](^[t]queue^[f](^[f]new^[t](^[f]x), ^[t]y))) -> ^[f]top^[t](^[t]check^[t](^[t]queue^[f](^[f]x, ^[t]y))) 14.65/4.61 14.65/4.61 ^[f]top^[t](^[t]ok^[f](^[t]queue^[f](^[t]new^[f](^[t]x), ^[f]y))) -> ^[f]top^[t](^[t]check^[t](^[t]queue^[f](^[t]x, ^[f]y))) 14.65/4.61 14.65/4.61 ^[f]bot^[t] -> ^[f]new^[t](^[f]bot^[t]) 14.65/4.61 14.65/4.61 ^[t]check^[t](^[t]old^[f](^[f]x)) -> ^[t]ok^[f](^[t]old^[f](^[f]x)) 14.65/4.61 14.65/4.61 ^[f]check^[f](^[f]new^[t](^[f]x)) -> ^[f]new^[t](^[f]check^[f](^[f]x)) 14.65/4.61 14.65/4.61 ^[t]check^[t](^[t]new^[f](^[t]x)) -> ^[t]new^[f](^[t]check^[t](^[t]x)) 14.65/4.62 14.65/4.62 ^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y)) -> ^[f]queue^[f](^[f]check^[f](^[f]x), ^[f]y) 14.65/4.62 14.65/4.62 ^[t]check^[t](^[t]queue^[f](^[f]x, ^[t]y)) -> ^[t]queue^[f](^[f]check^[f](^[f]x), ^[t]y) 14.65/4.62 14.65/4.62 ^[t]check^[t](^[t]queue^[f](^[t]x, ^[f]y)) -> ^[t]queue^[f](^[t]check^[t](^[t]x), ^[f]y) 14.65/4.62 14.65/4.62 ^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y)) -> ^[f]queue^[f](^[f]x, ^[f]check^[f](^[f]y)) 14.65/4.62 14.65/4.62 ^[t]check^[t](^[t]queue^[f](^[f]x, ^[t]y)) -> ^[t]queue^[f](^[f]x, ^[t]check^[t](^[t]y)) 14.65/4.62 14.65/4.62 ^[t]check^[t](^[t]queue^[f](^[t]x, ^[f]y)) -> ^[t]queue^[f](^[t]x, ^[f]check^[f](^[f]y)) 14.65/4.62 14.65/4.62 ^[t]new^[f](^[t]ok^[f](^[f]x)) -> ^[t]ok^[f](^[f]new^[t](^[f]x)) 14.65/4.62 14.65/4.62 ^[t]new^[f](^[t]ok^[f](^[t]x)) -> ^[t]ok^[f](^[t]new^[f](^[t]x)) 14.65/4.62 14.65/4.62 ^[t]queue^[f](^[t]ok^[f](^[f]x), ^[f]y) -> ^[t]ok^[f](^[f]queue^[f](^[f]x, ^[f]y)) 14.65/4.62 14.65/4.62 ^[t]queue^[f](^[t]ok^[f](^[f]x), ^[t]y) -> ^[t]ok^[f](^[t]queue^[f](^[f]x, ^[t]y)) 14.65/4.62 14.65/4.62 ^[t]queue^[f](^[f]x, ^[t]ok^[f](^[f]y)) -> ^[t]ok^[f](^[f]queue^[f](^[f]x, ^[f]y)) 14.65/4.62 14.65/4.62 ^[t]queue^[f](^[f]x, ^[t]ok^[f](^[t]y)) -> ^[t]ok^[f](^[t]queue^[f](^[f]x, ^[t]y)) 14.65/4.62 14.65/4.62 ^[f]top^[t](^[t]ok^[f](^[f]queue^[f](^[f]new^[t](^[f]x), ^[f]bot^[t]))) -> ^[f]top^[f](^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]bot^[t]))) 14.65/4.62 14.65/4.62 ^[f]top^[t](^[t]ok^[f](^[t]queue^[f](^[t]new^[f](^[t]x), ^[f]bot^[t]))) -> ^[f]top^[t](^[t]check^[t](^[t]queue^[f](^[t]x, ^[f]bot^[t]))) 14.65/4.62 14.65/4.62 ^[f]top^[t](^[t]ok^[f](^[f]queue^[f](^[f]bot^[t], ^[f]new^[t](^[f]x)))) -> ^[f]top^[f](^[f]check^[f](^[f]queue^[f](^[f]bot^[t], ^[f]x))) 14.65/4.62 14.65/4.62 ^[f]top^[t](^[t]ok^[f](^[t]queue^[f](^[f]bot^[t], ^[t]new^[f](^[t]x)))) -> ^[f]top^[t](^[t]check^[t](^[t]queue^[f](^[f]bot^[t], ^[t]x))) 14.65/4.62 14.65/4.62 ^[f]top^[t](^[t]ok^[f](^[f]queue^[f](^[f]new^[t](^[f]x), ^[f]new^[t](^[f]y)))) -> ^[f]top^[f](^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y))) 14.65/4.62 14.65/4.62 ^[f]top^[t](^[t]ok^[f](^[t]queue^[f](^[f]new^[t](^[f]x), ^[t]new^[f](^[t]y)))) -> ^[f]top^[t](^[t]check^[t](^[t]queue^[f](^[f]x, ^[t]y))) 14.65/4.62 14.65/4.62 ^[f]top^[t](^[t]ok^[f](^[t]queue^[f](^[t]new^[f](^[t]x), ^[f]new^[t](^[f]y)))) -> ^[f]top^[t](^[t]check^[t](^[t]queue^[f](^[t]x, ^[f]y))) 14.65/4.62 14.65/4.62 ^[f]top^[t](^[t]ok^[f](^[t]queue^[f](^[t]new^[f](^[t]x), ^[t]new^[f](^[t]y)))) -> ^[f]top^[t](^[t]check^[t](^[t]queue^[f](^[t]x, ^[t]y))) 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 Our polynomial interpretation was: 14.65/4.62 14.65/4.62 P(top^[false])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(top^[true])(x_1) = 1 + 1*x_1 14.65/4.62 14.65/4.62 P(ok^[false])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(ok^[true])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(queue^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 14.65/4.62 14.65/4.62 P(queue^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 14.65/4.62 14.65/4.62 P(new^[false])(x_1) = 1 + 1*x_1 14.65/4.62 14.65/4.62 P(new^[true])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(check^[false])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(check^[true])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(bot^[false])() = 0 14.65/4.62 14.65/4.62 P(bot^[true])() = 1 14.65/4.62 14.65/4.62 P(old^[false])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(old^[true])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 14.65/4.62 The following rules were deleted from R: 14.65/4.62 14.65/4.62 top(ok(queue(new(x), new(y)))) -> top(check(queue(x, y))) 14.65/4.62 14.65/4.62 The following rules were deleted from S: 14.65/4.62 none 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 ---------------------------------------- 14.65/4.62 14.65/4.62 (6) 14.65/4.62 Obligation: 14.65/4.62 Relative term rewrite system: 14.65/4.62 The relative TRS consists of the following R rules: 14.65/4.62 14.65/4.62 top(ok(queue(new(x), bot))) -> top(check(queue(x, bot))) 14.65/4.62 top(ok(queue(bot, new(x)))) -> top(check(queue(bot, x))) 14.65/4.62 14.65/4.62 The relative TRS consists of the following S rules: 14.65/4.62 14.65/4.62 top(ok(queue(new(x), y))) -> top(check(queue(x, y))) 14.65/4.62 bot -> new(bot) 14.65/4.62 check(old(x)) -> ok(old(x)) 14.65/4.62 check(new(x)) -> new(check(x)) 14.65/4.62 check(queue(x, y)) -> queue(check(x), y) 14.65/4.62 check(queue(x, y)) -> queue(x, check(y)) 14.65/4.62 new(ok(x)) -> ok(new(x)) 14.65/4.62 queue(ok(x), y) -> ok(queue(x, y)) 14.65/4.62 queue(x, ok(y)) -> ok(queue(x, y)) 14.65/4.62 14.65/4.62 14.65/4.62 ---------------------------------------- 14.65/4.62 14.65/4.62 (7) RelTRSSemanticLabellingPOLOProof (EQUIVALENT) 14.65/4.62 We use Semantic Labelling over tuples of bools combined with a polynomial order [SEMLAB] 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 We use semantic labelling over boolean tuples of size 1. 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 We used the following model: 14.65/4.62 14.65/4.62 top_1: component 1: AND[] 14.65/4.62 14.65/4.62 ok_1: component 1: OR[] 14.65/4.62 14.65/4.62 queue_2: component 1: AND[x_1^1, x_2^1] 14.65/4.62 14.65/4.62 new_1: component 1: OR[x_1^1] 14.65/4.62 14.65/4.62 check_1: component 1: OR[x_1^1] 14.65/4.62 14.65/4.62 bot_0: component 1: AND[] 14.65/4.62 14.65/4.62 old_1: component 1: OR[] 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 Our labelling function was: 14.65/4.62 14.65/4.62 top_1:component 1: XOR[-x_1^1] 14.65/4.62 14.65/4.62 ok_1:component 1: OR[x_1^1] 14.65/4.62 14.65/4.62 queue_2:component 1: AND[x_1^1, x_2^1] 14.65/4.62 14.65/4.62 new_1:component 1: OR[-x_1^1] 14.65/4.62 14.65/4.62 check_1:component 1: OR[x_1^1] 14.65/4.62 14.65/4.62 bot_0:component 1: OR[] 14.65/4.62 14.65/4.62 old_1:component 1: OR[] 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 Our labelled system was: 14.65/4.62 14.65/4.62 ^[t]top^[t](^[f]ok^[f](^[f]queue^[f](^[f]new^[t](^[f]x), ^[f]y))) -> ^[t]top^[t](^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y))) 14.65/4.62 14.65/4.62 ^[t]top^[t](^[f]ok^[f](^[f]queue^[f](^[t]new^[f](^[t]x), ^[f]y))) -> ^[t]top^[t](^[f]check^[f](^[f]queue^[f](^[t]x, ^[f]y))) 14.65/4.62 14.65/4.62 ^[t]top^[t](^[f]ok^[t](^[t]queue^[t](^[t]new^[f](^[t]x), ^[t]y))) -> ^[t]top^[f](^[t]check^[t](^[t]queue^[t](^[t]x, ^[t]y))) 14.65/4.62 14.65/4.62 ^[t]bot^[f] -> ^[t]new^[f](^[t]bot^[f]) 14.65/4.62 14.65/4.62 ^[f]check^[f](^[f]old^[f](^[f]x)) -> ^[f]ok^[f](^[f]old^[f](^[f]x)) 14.65/4.62 14.65/4.62 ^[f]check^[f](^[f]new^[t](^[f]x)) -> ^[f]new^[t](^[f]check^[f](^[f]x)) 14.65/4.62 14.65/4.62 ^[t]check^[t](^[t]new^[f](^[t]x)) -> ^[t]new^[f](^[t]check^[t](^[t]x)) 14.65/4.62 14.65/4.62 ^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y)) -> ^[f]queue^[f](^[f]check^[f](^[f]x), ^[f]y) 14.65/4.62 14.65/4.62 ^[f]check^[f](^[f]queue^[f](^[t]x, ^[f]y)) -> ^[f]queue^[f](^[t]check^[t](^[t]x), ^[f]y) 14.65/4.62 14.65/4.62 ^[t]check^[t](^[t]queue^[t](^[t]x, ^[t]y)) -> ^[t]queue^[t](^[t]check^[t](^[t]x), ^[t]y) 14.65/4.62 14.65/4.62 ^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y)) -> ^[f]queue^[f](^[f]x, ^[f]check^[f](^[f]y)) 14.65/4.62 14.65/4.62 ^[f]check^[f](^[f]queue^[f](^[f]x, ^[t]y)) -> ^[f]queue^[f](^[f]x, ^[t]check^[t](^[t]y)) 14.65/4.62 14.65/4.62 ^[t]check^[t](^[t]queue^[t](^[t]x, ^[t]y)) -> ^[t]queue^[t](^[t]x, ^[t]check^[t](^[t]y)) 14.65/4.62 14.65/4.62 ^[f]new^[t](^[f]ok^[f](^[f]x)) -> ^[f]ok^[f](^[f]new^[t](^[f]x)) 14.65/4.62 14.65/4.62 ^[f]new^[t](^[f]ok^[t](^[t]x)) -> ^[f]ok^[t](^[t]new^[f](^[t]x)) 14.65/4.62 14.65/4.62 ^[f]queue^[f](^[f]ok^[f](^[f]x), ^[f]y) -> ^[f]ok^[f](^[f]queue^[f](^[f]x, ^[f]y)) 14.65/4.62 14.65/4.62 ^[f]queue^[f](^[f]ok^[t](^[t]x), ^[f]y) -> ^[f]ok^[f](^[f]queue^[f](^[t]x, ^[f]y)) 14.65/4.62 14.65/4.62 ^[f]queue^[f](^[f]ok^[t](^[t]x), ^[t]y) -> ^[f]ok^[t](^[t]queue^[t](^[t]x, ^[t]y)) 14.65/4.62 14.65/4.62 ^[f]queue^[f](^[f]x, ^[f]ok^[f](^[f]y)) -> ^[f]ok^[f](^[f]queue^[f](^[f]x, ^[f]y)) 14.65/4.62 14.65/4.62 ^[f]queue^[f](^[f]x, ^[f]ok^[t](^[t]y)) -> ^[f]ok^[f](^[f]queue^[f](^[f]x, ^[t]y)) 14.65/4.62 14.65/4.62 ^[f]queue^[f](^[t]x, ^[f]ok^[t](^[t]y)) -> ^[f]ok^[t](^[t]queue^[t](^[t]x, ^[t]y)) 14.65/4.62 14.65/4.62 ^[t]top^[t](^[f]ok^[f](^[f]queue^[f](^[f]new^[t](^[f]x), ^[t]bot^[f]))) -> ^[t]top^[t](^[f]check^[f](^[f]queue^[f](^[f]x, ^[t]bot^[f]))) 14.65/4.62 14.65/4.62 ^[t]top^[t](^[f]ok^[t](^[t]queue^[t](^[t]new^[f](^[t]x), ^[t]bot^[f]))) -> ^[t]top^[f](^[t]check^[t](^[t]queue^[t](^[t]x, ^[t]bot^[f]))) 14.65/4.62 14.65/4.62 ^[t]top^[t](^[f]ok^[f](^[f]queue^[f](^[t]bot^[f], ^[f]new^[t](^[f]x)))) -> ^[t]top^[t](^[f]check^[f](^[f]queue^[f](^[t]bot^[f], ^[f]x))) 14.65/4.62 14.65/4.62 ^[t]top^[t](^[f]ok^[t](^[t]queue^[t](^[t]bot^[f], ^[t]new^[f](^[t]x)))) -> ^[t]top^[f](^[t]check^[t](^[t]queue^[t](^[t]bot^[f], ^[t]x))) 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 Our polynomial interpretation was: 14.65/4.62 14.65/4.62 P(top^[false])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(top^[true])(x_1) = 1 + 1*x_1 14.65/4.62 14.65/4.62 P(ok^[false])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(ok^[true])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(queue^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 14.65/4.62 14.65/4.62 P(queue^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 14.65/4.62 14.65/4.62 P(new^[false])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(new^[true])(x_1) = 1 + 1*x_1 14.65/4.62 14.65/4.62 P(check^[false])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(check^[true])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(bot^[false])() = 0 14.65/4.62 14.65/4.62 P(bot^[true])() = 0 14.65/4.62 14.65/4.62 P(old^[false])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(old^[true])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 14.65/4.62 The following rules were deleted from R: 14.65/4.62 14.65/4.62 top(ok(queue(bot, new(x)))) -> top(check(queue(bot, x))) 14.65/4.62 14.65/4.62 The following rules were deleted from S: 14.65/4.62 none 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 ---------------------------------------- 14.65/4.62 14.65/4.62 (8) 14.65/4.62 Obligation: 14.65/4.62 Relative term rewrite system: 14.65/4.62 The relative TRS consists of the following R rules: 14.65/4.62 14.65/4.62 top(ok(queue(new(x), bot))) -> top(check(queue(x, bot))) 14.65/4.62 14.65/4.62 The relative TRS consists of the following S rules: 14.65/4.62 14.65/4.62 top(ok(queue(new(x), y))) -> top(check(queue(x, y))) 14.65/4.62 bot -> new(bot) 14.65/4.62 check(old(x)) -> ok(old(x)) 14.65/4.62 check(new(x)) -> new(check(x)) 14.65/4.62 check(queue(x, y)) -> queue(check(x), y) 14.65/4.62 check(queue(x, y)) -> queue(x, check(y)) 14.65/4.62 new(ok(x)) -> ok(new(x)) 14.65/4.62 queue(ok(x), y) -> ok(queue(x, y)) 14.65/4.62 queue(x, ok(y)) -> ok(queue(x, y)) 14.65/4.62 14.65/4.62 14.65/4.62 ---------------------------------------- 14.65/4.62 14.65/4.62 (9) RelTRSSemanticLabellingPOLOProof (EQUIVALENT) 14.65/4.62 We use Semantic Labelling over tuples of bools combined with a polynomial order [SEMLAB] 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 We use semantic labelling over boolean tuples of size 1. 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 We used the following model: 14.65/4.62 14.65/4.62 top_1: component 1: AND[] 14.65/4.62 14.65/4.62 ok_1: component 1: OR[] 14.65/4.62 14.65/4.62 queue_2: component 1: AND[x_1^1, x_2^1] 14.65/4.62 14.65/4.62 new_1: component 1: OR[x_1^1] 14.65/4.62 14.65/4.62 check_1: component 1: OR[x_1^1] 14.65/4.62 14.65/4.62 bot_0: component 1: AND[] 14.65/4.62 14.65/4.62 old_1: component 1: OR[] 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 Our labelling function was: 14.65/4.62 14.65/4.62 top_1:component 1: XOR[x_1^1] 14.65/4.62 14.65/4.62 ok_1:component 1: OR[-x_1^1] 14.65/4.62 14.65/4.62 queue_2:component 1: OR[] 14.65/4.62 14.65/4.62 new_1:component 1: OR[-x_1^1] 14.65/4.62 14.65/4.62 check_1:component 1: OR[] 14.65/4.62 14.65/4.62 bot_0:component 1: AND[] 14.65/4.62 14.65/4.62 old_1:component 1: OR[x_1^1] 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 Our labelled system was: 14.65/4.62 14.65/4.62 ^[t]top^[f](^[f]ok^[t](^[f]queue^[f](^[f]new^[t](^[f]x), ^[f]y))) -> ^[t]top^[f](^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y))) 14.65/4.62 14.65/4.62 ^[t]top^[f](^[f]ok^[t](^[f]queue^[f](^[t]new^[f](^[t]x), ^[f]y))) -> ^[t]top^[f](^[f]check^[f](^[f]queue^[f](^[t]x, ^[f]y))) 14.65/4.62 14.65/4.62 ^[t]top^[f](^[f]ok^[f](^[t]queue^[f](^[t]new^[f](^[t]x), ^[t]y))) -> ^[t]top^[t](^[t]check^[f](^[t]queue^[f](^[t]x, ^[t]y))) 14.65/4.62 14.65/4.62 ^[t]bot^[t] -> ^[t]new^[f](^[t]bot^[t]) 14.65/4.62 14.65/4.62 ^[f]check^[f](^[f]old^[f](^[f]x)) -> ^[f]ok^[t](^[f]old^[f](^[f]x)) 14.65/4.62 14.65/4.62 ^[f]check^[f](^[f]old^[t](^[t]x)) -> ^[f]ok^[t](^[f]old^[t](^[t]x)) 14.65/4.62 14.65/4.62 ^[f]check^[f](^[f]new^[t](^[f]x)) -> ^[f]new^[t](^[f]check^[f](^[f]x)) 14.65/4.62 14.65/4.62 ^[t]check^[f](^[t]new^[f](^[t]x)) -> ^[t]new^[f](^[t]check^[f](^[t]x)) 14.65/4.62 14.65/4.62 ^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y)) -> ^[f]queue^[f](^[f]check^[f](^[f]x), ^[f]y) 14.65/4.62 14.65/4.62 ^[f]check^[f](^[f]queue^[f](^[t]x, ^[f]y)) -> ^[f]queue^[f](^[t]check^[f](^[t]x), ^[f]y) 14.65/4.62 14.65/4.62 ^[t]check^[f](^[t]queue^[f](^[t]x, ^[t]y)) -> ^[t]queue^[f](^[t]check^[f](^[t]x), ^[t]y) 14.65/4.62 14.65/4.62 ^[f]check^[f](^[f]queue^[f](^[f]x, ^[f]y)) -> ^[f]queue^[f](^[f]x, ^[f]check^[f](^[f]y)) 14.65/4.62 14.65/4.62 ^[f]check^[f](^[f]queue^[f](^[f]x, ^[t]y)) -> ^[f]queue^[f](^[f]x, ^[t]check^[f](^[t]y)) 14.65/4.62 14.65/4.62 ^[t]check^[f](^[t]queue^[f](^[t]x, ^[t]y)) -> ^[t]queue^[f](^[t]x, ^[t]check^[f](^[t]y)) 14.65/4.62 14.65/4.62 ^[f]new^[t](^[f]ok^[t](^[f]x)) -> ^[f]ok^[t](^[f]new^[t](^[f]x)) 14.65/4.62 14.65/4.62 ^[f]new^[t](^[f]ok^[f](^[t]x)) -> ^[f]ok^[f](^[t]new^[f](^[t]x)) 14.65/4.62 14.65/4.62 ^[f]queue^[f](^[f]ok^[t](^[f]x), ^[f]y) -> ^[f]ok^[t](^[f]queue^[f](^[f]x, ^[f]y)) 14.65/4.62 14.65/4.62 ^[f]queue^[f](^[f]ok^[f](^[t]x), ^[f]y) -> ^[f]ok^[t](^[f]queue^[f](^[t]x, ^[f]y)) 14.65/4.62 14.65/4.62 ^[f]queue^[f](^[f]ok^[f](^[t]x), ^[t]y) -> ^[f]ok^[f](^[t]queue^[f](^[t]x, ^[t]y)) 14.65/4.62 14.65/4.62 ^[f]queue^[f](^[f]x, ^[f]ok^[t](^[f]y)) -> ^[f]ok^[t](^[f]queue^[f](^[f]x, ^[f]y)) 14.65/4.62 14.65/4.62 ^[f]queue^[f](^[f]x, ^[f]ok^[f](^[t]y)) -> ^[f]ok^[t](^[f]queue^[f](^[f]x, ^[t]y)) 14.65/4.62 14.65/4.62 ^[f]queue^[f](^[t]x, ^[f]ok^[f](^[t]y)) -> ^[f]ok^[f](^[t]queue^[f](^[t]x, ^[t]y)) 14.65/4.62 14.65/4.62 ^[t]top^[f](^[f]ok^[t](^[f]queue^[f](^[f]new^[t](^[f]x), ^[t]bot^[t]))) -> ^[t]top^[f](^[f]check^[f](^[f]queue^[f](^[f]x, ^[t]bot^[t]))) 14.65/4.62 14.65/4.62 ^[t]top^[f](^[f]ok^[f](^[t]queue^[f](^[t]new^[f](^[t]x), ^[t]bot^[t]))) -> ^[t]top^[t](^[t]check^[f](^[t]queue^[f](^[t]x, ^[t]bot^[t]))) 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 Our polynomial interpretation was: 14.65/4.62 14.65/4.62 P(top^[false])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(top^[true])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(ok^[false])(x_1) = 1 + 1*x_1 14.65/4.62 14.65/4.62 P(ok^[true])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(queue^[false])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 14.65/4.62 14.65/4.62 P(queue^[true])(x_1,x_2) = 0 + 1*x_1 + 1*x_2 14.65/4.62 14.65/4.62 P(new^[false])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(new^[true])(x_1) = 1 + 1*x_1 14.65/4.62 14.65/4.62 P(check^[false])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(check^[true])(x_1) = 0 + 1*x_1 14.65/4.62 14.65/4.62 P(bot^[false])() = 0 14.65/4.62 14.65/4.62 P(bot^[true])() = 0 14.65/4.62 14.65/4.62 P(old^[false])(x_1) = 1 + 1*x_1 14.65/4.62 14.65/4.62 P(old^[true])(x_1) = 1 + 1*x_1 14.65/4.62 14.65/4.62 14.65/4.62 The following rules were deleted from R: 14.65/4.62 14.65/4.62 top(ok(queue(new(x), bot))) -> top(check(queue(x, bot))) 14.65/4.62 14.65/4.62 The following rules were deleted from S: 14.65/4.62 none 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 14.65/4.62 ---------------------------------------- 14.65/4.62 14.65/4.62 (10) 14.65/4.62 Obligation: 14.65/4.62 Relative term rewrite system: 14.65/4.62 R is empty. 14.65/4.62 The relative TRS consists of the following S rules: 14.65/4.62 14.65/4.62 top(ok(queue(new(x), y))) -> top(check(queue(x, y))) 14.65/4.62 bot -> new(bot) 14.65/4.62 check(old(x)) -> ok(old(x)) 14.65/4.62 check(new(x)) -> new(check(x)) 14.65/4.62 check(queue(x, y)) -> queue(check(x), y) 14.65/4.62 check(queue(x, y)) -> queue(x, check(y)) 14.65/4.62 new(ok(x)) -> ok(new(x)) 14.65/4.62 queue(ok(x), y) -> ok(queue(x, y)) 14.65/4.62 queue(x, ok(y)) -> ok(queue(x, y)) 14.65/4.62 14.65/4.62 14.65/4.62 ---------------------------------------- 14.65/4.62 14.65/4.62 (11) RIsEmptyProof (EQUIVALENT) 14.65/4.62 The TRS R is empty. Hence, termination is trivially proven. 14.65/4.62 ---------------------------------------- 14.65/4.62 14.65/4.62 (12) 14.65/4.62 YES 14.97/4.65 EOF